第三章 数据结构—— 栈和队列.ppt

栈和队列 栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS 2.4 栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） 栈的存储结构 顺序栈 实现：一维数组s[M] 创建栈 判断栈空 链栈 Tower of Hanoi问题 问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上 2.5 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) 链队列 结点定义 队列的顺序存储结构 实现：用一维数组实现sq[M] 存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出 当front?-1,rear=M-1时，再有元素入队发生溢出——假溢出 解决方案 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0; * an a1 a2 ……... 栈底 栈顶 ... 出栈 进栈 栈s=(a1,a2,……,an) top=0 1 2 3 4 5 0 栈空 栈顶指针top,指向实际栈顶 后的空位置，初值为0 top 1 2 3 4 5 0 进栈 A top 出栈 栈满 B C D E F 设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow) top top top top top 1 2 3 4 5 0 A B C D E F top top top top top top 栈空 0 M-1 栈1底 栈1顶 栈2底 栈2顶 入栈算法 出栈算法 在一个程序中同时使用两个栈 定义顺序栈 栈顶 ^ …... top data link 栈底 结点定义 入栈算法 出栈算法 typedef struct node { int data; struct node *link; }JD; ^ …... 栈底 top top x p top ^ …... 栈底 top q 栈的应用 过程的嵌套调用 r 主程序 s r r r s 子过程1 r s t 子过程2 r s t 子过程3 实现递归 将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务： 保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。 从被调用函数返回调用函数之前，应该完成下列三项任务： 例 递归的执行情况分析 void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i=w;++i) printf(“%3d,”,w); printf(“/n”); } } Ch3_10.c 运行结果： 1， 2，2， 3，3，3， 递归调用执行情况如下： 主程序 (1) print(w) w=3; 3 print(2); （1）w=3 top w 2 print(1); （2）w=2 （1）w=3 top w 1 print(0); （3）w=1 （2）w=2 （1）w=3 top w 0 （4）w=0 （3）w=1 （2）w=2 （1）w=3 top w (3) 输出：2, 2 (2) 2 (1) 3 top (4)输出：1 (3) 1 (2) 2 (1) 3 top (2) 输出：3, 3, 3 (1 ) 3 top 返回 (3) 1 (2) 2 (1) 3 top (4) 0 结束 (1) 解决方法