将最后一个结点的空指针改为指向头结点,从任一结点出发均可找到其它结点 (3)双向链表P55 在每个结点中设置两个指针,一个指向后继,一个指向前驱。可直接确定一个结点的前驱和后继结点 可提高效率。一插入和删除 作业2:对以下单链表分别执行下列各程序段并画出结果示意图 L→D十[5十1 Rs↑ (1)LFP->link; (4)P->link->link->link->data=P->data hile(tl=NUll) T->data=( T=T->link while(T->linkI=NULL T->data=(T->data)2 T=T->link ()P=(JD*)malloc(sizeof(JD)); R->linker: P->link=s TL T->linkep->link. (9)S->link 习题:2。10逆转线性单链表 扫描单链表将第一个节点的next设置为NULL将第二个节点的next指向第一个节点,将第三个节点的 next指向第二个节点 Invert(head) Node *head i node*p, *.*r P=head; q=p->next; While(q=null) head->nextENULL: 33栈
6 将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。 （3） 双向链表 P55 在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。 可提高效率。—插入和删除 作业 2： 对以下单链表分别执行下列各程序段,并画出结果示意图. (1) L=P->link; (2) R->data=P->data; (3) R->data=P->link->data; (4) P->link->link->link->data=P->data; (5) T=P; while(T!=NULL) { T->data=(T->data)*2; T=T->link; } (6) T=P; while(T->link!=NULL) { T->data=(T->data)*2; T=T->link; } (7) P=(JD*)malloc(sizeof(JD)); P->data=10; R->link=P; P->link=S; (8) T=L; T->link=P->link; free(P); (9) S->link=L; 习题：2。10 逆转线性单链表 扫描单链表,将第一个节点的 next 设置为 NULL,将第二个节点的 next 指向第一个节点, 将第三个节点的 next 指向第二个节点,… Invert(head) Node *head; { node *p,*q,*r; P=head; q=p—>next; While (q!=NULL) { r=q—>next; q—>next=p; p=q; q=r; } head—>next=NULL; head=p;} 3.3 栈 L S 2 5 7 3 8 ^ P R
1.栈 stack的定义 栈是特殊的线性表,仅在表的一端进行插入或删除操作 特点:(1)对栈内数据的操作总在栈顶进行 (2)数据进栈称为“压入”push (3)数据出栈称为“弹出”pop (4)遵循“后进先出”的原则LIFO 例题:输入顺序ABC,输出顺序有几种? ABC,ACB,BAC,BCA,CBA,不可能产生CAB 2.栈的顺序存储结构及运算 用数组实现栈, 为栈底,top为栈顶 (1)定义 typedef struct stack type elemtype data MAXNUM; Astack type (2)进栈push 当新元素进栈时,栈顶上移,新元素放在栈顶。 stack top=stack top+l: stack.datalstack top]= new one (3)出栈pop:从栈顶移出一个数据 栈顶元素拷贝出栈,栈顶下移 elemptype pop(stack type *stack) i elemtype out; f(stack->top <0)error(3); el out=stack->data[stack->top; stack->top= stack->top-1 return out (4)栈空判断 stack top==0(stack top<0) 栈满判断: stack top>= MAXNUM-1
7 1. 栈 stack 的定义 栈是特殊的线性表，仅在表的一端进行插入或删除操作 特点：（1）对栈内数据的操作总在栈顶进行 （2）数据进栈称为“压入”push （3）数据出栈称为“弹出”pop （4）遵循“后进先出”的原则 LIFO 例题：输入顺序 A,B,C，输出顺序有几种？ ABC,ACB,BAC,BCA,CBA, 不可能产生 CAB 2.栈的顺序存储结构及运算 用数组实现栈, a[0]为栈底，top 为栈顶 （1）定义 typedef struct stack_type{ elemtype data[MAXNUM]; int top; }stack_type; （2）进栈 push 当新元素进栈时，栈顶上移，新元素放在栈顶。 stack.top = stack.top + 1; stack.data[stack.top] = new_one; （3）出栈 pop: 从栈顶移出一个数据。 栈顶元素拷贝出栈，栈顶下移 elemptype pop(stack_type *stack) { elemtype out; if(stack->top < 0) error(3); else{ out = stack->data[stack->top]; stack->top = stack->top -1; } return out; } （4）栈空判断 stack.top = = 0 (stack.top < 0) 栈满判断：stack.top >= MAXNUM - 1;
(5)置栈空 stack top=-1 (6)栈的应用 例程序的嵌套,中断的嵌套 见书P35 3.栈的链式存储结构及运算 用链表实现栈 (1)定义 typedef struct stack typet node type* top int length; 3 stack type: (2)压入psh void push(stack, new node)i new_ node->next= stack->top: stack->top= new node ck->length ++ (3)弹出pop node type* pop(stack) node type *out; out=stack->top; stack->top= stack->top->next; stack->length -- return out; (4)栈空判断 stack top= NULL (5)置栈空 能否简单的使用 stack top=NULL? 如果栈中还有链点,必须逐个将链点占用的空间释放 1、逐个将链点弹出 2、释放链点空间 void clean(stack R node type* temp while(! empty(stack))t temp= pop(stack); free(temp);)
8 （5）置栈空 stack.top = -1; （6）栈的应用 例 程序的嵌套，中断的嵌套 见书 P35 3.栈的链式存储结构及运算 用链表实现栈 （1）定义 typedef struct lstack_type{ node_type * top; int length; }lstack_type; （2）压入 push void push(stack, new_node){ new_node->next = stack->top; stack->top = new_node; stack->length ++;} （3）弹出 pop node_type * pop(stack){ node_type* out; out = stack->top; stack->top = stack->top->next; stack->length --; return out;} （4）栈空判断 stack.top == NULL; （5）置栈空 能否简单的使用 stack.top = NULL ? 如果栈中还有链点，必须逐个将链点占用的空间释放 1、逐个将链点弹出 2、释放链点空间 void clean(stack){ node_type * temp; while( ! empty(stack)){ temp = pop(stack); free(temp); }
34队列 1队列定义 类似于排队机制的结构,队列是特殊的线性表, 节点的插入仅限于在表尾进行,节点的删除仅限于在表头进行 队列特点 特点 (1)对队列的操作在表的两端进行 (2)仅在队尾加入节点——入队 enqueue (3)仅在队首移出节点——出队 dequeue ◆(4)遵循“先进先出”的原则—FIFO 队列的顺序存储结构及运算 2.用数组实现队列 (1)定义 typedef struct queue type i elemtype data MAXNUMI int front: int rear: queue type; (2)入队与出队 用循环数组实现队列 void enqueue(queue, new one) i if((queue->rear+1)%MAXNUM== queue->front)error(1) else queue->data queue->rear new one queue->rear=(queue->rear +1)% MAXNUM elemtype dequeue(queue) i elemtype out; queue->front) error(2); else out =queue->datalqueue->front queue->front=(queue->front +1)% MAXNUM; return out; 思考:数组Q0,41 front=l, rear=3
9 } 3.4 队列 1.队列定义 类似于排队机制的结构, 队列是特殊的线性表， 节点的插入仅限于在表尾进行，节点的删除仅限于在表头进行. 队列特点 ◼ 特点： ◆ （1）对队列的操作在表的两端进行 ◆ （2）仅在队尾加入节点——入队 enqueue ◆ （3）仅在队首移出节点——出队 dequeue ◆ （4）遵循“先进先出”的原则——FIFO 队列的顺序存储结构及运算 2. 用数组实现队列 （1）定义 typedef struct queue_type { elemtype data[MAXNUM]; int front; int rear; }queue_type; （2）入队与出队 用循环数组实现队列 void enqueue(queue, new_one) { if( (queue->rear + 1) % MAXNUM = = queue->front ) error(1); else{ queue->data[queue->rear] = new_one; queue->rear = (queue->rear +1) % MAXNUM; } } elemtype dequeue(queue) { elemtype out； if( queue->rear = = queue->front ) error(2); else{ out ＝queue->data[queue->front]; queue->front = (queue->front +1) % MAXNUM; } return out； } 思考：数组 Q[0,4] 1. front=1， rear=3 2. front=3， rear=1
3.用链表实现队列 (一)定义 typedef struct Iqueue type i node type* front node type 云rear int length (二)入队 新链点插入到队尾 注意:队列为空时,rear和 front都要指向新元素 new node ->next= NUlL: list->rear ->next new node (三)出队 删除队首链点 注意:当队列被删空时,rear指针要置空 temp= list->front; list->front list->front->next 习题: 例1若进栈序列为3,5,7,9,进栈过程中可以出栈,则不可能的一个出栈次序是(d)。 (a)7,5,3,9(b)9,7,5,3(c)7,5,9,3d)9.5,7,3 例3对于下面的程序调用过程,请问入栈序列是(1,2,3),出栈次序是(2,1,→ 例2用一维数组设计栈,初态是栈空,top=。现有输入序列是a、b、c、d,经过push、push、pop、 push、pop、push操作后,输出序列是(b,c ),栈顶指针是 程序A程序B程序C程序D Call d return 例4设栈S为空,队Q的状态是abcd,其中a为队首元素,d为队尾元素,经过下面两个操作后,队Q 的状态是(c)。 (1)删除队Q中的元素,将删除的元素插入栈S,直到队Q为空。 (2)依次将栈S中的元素插入队Q,直到栈S为空。 (a)abcd(b)acbd (c) (d) bacd 例5 Josephus问题 n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局:然后从出局的下一 个人重新开始报数,数到第m个人,再让他出局,。。,如此反复直到所有的人都出局为止。下面要解决的 Josephus问题是:对于任意给定的n,s和m,求出这n个人的出局序列。请以n=9,s=3,m=4为例,模拟 Josephus 的求解过程求问题的解 用顺序表结构和循环单链表结构求解 Josephus问题的一般步骤为 1)首先利用线性表的一些运算如创建空线性表、插入元素等构造 Josephus表
10 3．用链表实现队列 （一）定义 typedef struct lqueue_type { node_type * front; node_type * rear; int length; } （二） 入队 ◆ 新链点插入到队尾 ◆ 注意：队列为空时，rear 和 front 都要指向新元素 new_node->next = NULL; list->rear ->next = new_node; （三） 出队 ◆ 删除队首链点 ◆ 注意：当队列被删空时，rear 指针要置空 temp = list->front; list->front = list->front->next; 习题: 例 1 若进栈序列为 3，5，7，9，进栈过程中可以出栈，则不可能的一个出栈次序是（ d ）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3 例 2 用一维数组设计栈，初态是栈空，top=0。现有输入序列是 a、b、c、d，经过 push、push、pop、 push、pop、push 操作后，输出序列是（ b, c ），栈顶指针是（ 2 ） 例 3 对于下面的程序调用过程，请问入栈序列是（1, 2, 3 ），出栈次序是（ 2, 1, 3）。 程序A Call B 1: . . Call D 3: 程序B Call C 2: . . return 程序C Begin return 程序D Begin return 例 4 设栈 S 为空，队 Q 的状态是 abcd，其中 a 为队首元素，d 为队尾元素，经过下面两个操作后，队 Q 的状态是（ c ）。 （1）删除队 Q 中的元素，将删除的元素插入栈 S，直到队 Q 为空。 （2）依次将栈 S 中的元素插入队 Q，直到栈 S 为空。 (a) abcd (b) acbd (c) dcba (d) bacd 例 5 Josephus 问题 设 n 个人围坐在一个圆桌周围，现在从第 s 个人开始报数，数到第 m 个人，让他出局；然后从出局的下一 个人重新开始报数，数到第 m 个人，再让他出局，。。。，如此反复直到所有的人都出局为止。下面要解决的 Josephus 问题是：对于任意给定的 n,s 和 m，求出这 n 个人的出局序列。请以 n=9,s=3,m=4 为例，模拟 Josephus 的求解过程求问题的解。 用顺序表结构和循环单链表结构求解 Josephus 问题的一般步骤为： 1）首先利用线性表的一些运算如创建空线性表、插入元素等构造 Josephus 表；