第10章-栈和队列.ppt

栈 和 队 列 (2) 判断栈是否为空：在进行出栈操作时，首先必须判断栈不为空，否则会出错。 int EmptyS(struct Stack *s) { if (S－Top=0) return (0)； else return (1)； } /* EmptyS */ 例：若进栈序列为a,b,c,d，进栈过程中可以出栈，则（ ）不可能是一个出栈序列。 1）a,d,c,b 2) b,c,d,a 3) c,a,d,b 4) c,d,b,a 链栈 栈的链式存储结构称为链栈。它是运算限制的单链表，其插入和删除操作仅限制在表头位置上进行。 链栈的存储结构的描述 栈 的 应 用 栈在递归中的应用 一个递归函数类似于多个函数嵌套，只是调用函数和被调用函数是同一个。因此，这里涉及递归调用的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用该递归函数为进入第一层；从第i层递归调用本函数为进入第i+1层；反之，退出第i层递归返回到上一层,即第i-1层 Hanoi塔问题 (1)每次只能移一个圆盘 (2)盘可插在任意塔座 (3)任何时刻不能较大圆盘压在较小圆盘上 算法 Void hanoi(int n,char x,char y,char z) {if (n==1) move(x,1,z); //将编号为1的圆盘x-z Else {hanoi(n-1,x,z,y);//编号为1到n-1的圆盘x-y,z做辅助塔 move(x,n,z);//编号为n的圆盘x-z hanoi(n-1,y,x,z)；//编号为1到n-1的圆盘y-z,x做辅助塔 } } 迷宫求解问题 从入口出发，顺某一方向向前有哪些信誉好的足球投注网站，若能走通，则继续否则按原路退回，换个方向再有哪些信誉好的足球投注网站，直至所用可能通路探索到为止。 为保证在任何位置 都能按原路退回， 显然要用一个后进先出的结构保存走 过的路径。因此，用“栈” 假设以栈S记录“当前路径”，则栈顶中 存放的是“当前路径上最后一个通道块”。 由此，“纳入路径的操作即为”当前位置 入栈“，”从路径上删除前一通道块“的操作即为”出栈“ 下列关于栈的叙述正确的是 　　A)栈是非线性结构　 　 B)栈是一种树状结构　　　　C)栈具有先进先出的特征　 　 D)栈具有后进先出的特征 设有一个顺序栈S，元素s1，?s2，?s3，?s4，?s5，?s6依次进栈， 如果6个元素的出栈顺序为s2，?s3，?s4，?s6，?s5，?s1，则顺 序栈的容量至少应为多少？ 队 列 顺序队列运算时的头、尾指针变化情况 当前队列的状态，sq?rear+1naxsize–1，故此时不能做入队操作，但当前队列并不满，我们把这种现象称为“假上溢”。 入队前测试尾指针在循环意义下加1后是否等于头指针，若相等则认为是队满，即判别队满的条件是： (sq－rear+1)％maxsize==sq－front 队空的判别条件: sq?rear==sq?front 链队列 队列的链式存储结构称为链队列。它是限制在表头删除和表尾插入的单链表。 链队列的存储描述 typedef int dataype; typedef struct node {datatype data; struct node *next; }linklist; typedef struct { LinkList *front,*rear; }LinkQueue; 链队列示意图 实验二　单链表的合并 实验目的： １．深入了解单链表表的存储结构。 ２．熟练掌握在链式存储结构上进行查找、插入、删除等操作的算法。 实验内容： 假设有两个按元素值递增有序排列的单链表，试编写算法将A表和B表归并成一个按元素值非递减有序排列的单链表C，并用原表的结点空间存放表C。 写出完整的程序，执行并分析运行结果。 实验要求： 在上机前交预习报告，写出全部源程序。 实验报告格式规范，内容完整。 包括程序流程图，程序清单，实验数据及调试分析，和实验总结  上机(选做题) 若循环队列用数组A(0：m-1)存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（