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 表；