第三章栈和队列 栈和队列是两种特殊的线性表。是操作受限的线性 表,称限定性DS §3.1栈( stack) ★栈的定义和特点 ☆定义:限定仅在表尾进行插入或删除操作的线性表, 表尾一栈顶,表头—栈底,不含元素的空表称空栈 心特点:先进后出(Fo)或后进先出(LFO) 进栈 出栈 栈顶 栈s=(a1,a2,an a2 栈底 al
第三章 栈和队列 栈和队列是两种特殊的线性表，是操作受限的线性 表，称限定性DS §3.1 栈（stack） 栈的定义和特点 ❖定义：限定仅在表尾进行插入或删除操作的线性表， 表尾—栈顶，表头—栈底，不含元素的空表称空栈 ❖特点：先进后出（FILO）或后进先出（LIFO） an a1 a2……... 栈底 栈顶 进栈 ... 出栈 栈s=(a1,a2,……,an)
★栈的存储结构 今顺序栈 栈满 栈空 ●实现:一维数组S[M top top to top F p 4 top E 4 top top top D 3 top C to top P B top A 0 top=0 栈空 进栈 出栈 设数组维数为M 栈顶指针top,指向实际栈顶 后的空位置,初值为0 top=0,栈空,此时出栈,则下溢( underflow) top=M栈满,此时入栈,则上溢( overflow)
栈的存储结构 ❖顺序栈 ⚫实现：一维数组s[M] 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 A 0 B C D E top F top top top top top 栈空
●入栈算法 Ch3 txt ●出栈算法 Ch3 2.txt ●在一个程序中同时使用两个栈 多袭会 栈1底 栈1顶 栈2顶栈2底
⚫入栈算法 0 M-1 栈1底 栈1顶 栈2顶 栈2底 ⚫出栈算法 ⚫在一个程序中同时使用两个栈
今链栈 栈顶 栈底 topdata link ●结点定义 typedef struct node i int data struct node *link D 入栈算法 Ch33 txt top 栈底 ●出栈算法 Ch3 txt op 栈底 top
❖链栈 栈顶 top data link …... ^ 栈底 ⚫结点定义 ⚫入栈算法 ⚫出栈算法 typedef struct node { int data; struct node *link; }JD; …... ^ 栈底 top top x p top …... ^ 栈底 top q
★栈的应用 今过程的嵌套调用 子过程一 子过程 子过程 主程序 r」3
栈的应用 ❖过程的嵌套调用 r 主 程 序 s r r r s 子 过 程 1 r s t 子 过 程 2 r s t 子 过 程 3
今递归过程及其实现 递归:函数直接或间接的调用自身叫 ●实现:建立递归工作栈 例递归的执行情况分析<A void print(int w) int 1; if(w!=0) 运行结果: print(w-1) for(i=l; i<=w;++i) printf(%3d,”,w); 3,3,3, printi/n”); Ch3 10.c
例 递归的执行情况分析 ❖递归过程及其实现 ⚫递归：函数直接或间接的调用自身叫~ ⚫实现：建立递归工作栈 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
递归调用执行情况如下: print(0); 主程序 (4)输出:1 返回 print(1) print(2); (3)输出:2,2 w=3; print(w) (2)输出:3,3,3 结束 P top op (3)1 m(as-(3{留3 (2)2 (1)3 Back
递归调用执行情况如下： 主程序 (1) print(w) w=3; 3 print(2); （1）w=3 top (2) 输出：3, 3, 3 w 2 print(1) ; （2）w=2 （1）w=3 top (3) 输出：2, 2 w 1 print(0); （3）w=1 （2）w=2 （1）w=3 top (4)输出：1 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)
今 Tower of hano问题 ●问题描述:有A,B,C三个塔座,A上套有个直径不同的圆盘,按 直径从小到大叠放,形如宝塔,编号1,2,3.n。要求将n个圆盘 从A移到C.叠放顺序不变,移动过程中遵循下列原则 ◆每次只能移一个圆盘 ◆圆盘可在三个塔座上任意移动 ◆任何时刻,每个塔座上不能将大盘压到小盘上 解决方法 ◆n=1时,直接把圆盘从A移到C ◆n>1时,先把上面n-1个圆盘从A移到B,然后将n号盘从A 移到C,再将n1个盘从B移到C。即把求解n个圆盘的 Hano问题转化为求解∩-1个圆盘的Hano问题,依次类 推,直至转化成只有一个圆盘的Hano问题 ●算法: Hanoi. txt 执行情况 ◆递归工作栈保存内容:形参nXyz和返回地址 ◆返回地址用行编号表示nxy z返回地址
❖Tower of Hanoi问题 ⚫问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按 直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘 从A移到C，叠放顺序不变，移动过程中遵循下列原则： ◆每次只能移一个圆盘 ◆圆盘可在三个塔座上任意移动 ◆任何时刻，每个塔座上不能将大盘压到小盘上 ⚫解决方法： ◆n=1时，直接把圆盘从A移到C ◆n>1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A 移到C,再将n-1个盘从B移到C。即把求解n个圆盘的 Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类 推，直至转化成只有一个圆盘的Hanoi问题 ⚫算法： ⚫执行情况： ◆递归工作栈保存内容：形参n,x,y,z和返回地址 ◆返回地址用行编号表示 n x y z 返回地址
main( int m printf("Input number of disks"):I B scanf(%od",&m); printf( Steps: %03d disks, m); 3 ABC O hanoi(m'A,B C) 2ACB 6 void hanoi(int n, char x, char y, char z) 3ABIC O ABC6 (2)if(n==1) move(1, x, z). 2ACBI 6 4) else 3ABICO hanoi(n-1,x, Z,y). 6) move(n, x, z) hanoi(n-l,y, x, z) B (8)} 2ACB6 (9)} 3ABICO
main() { int m; printf("Input number of disks”); scanf("%d",&m); printf(”Steps : %3d disks”,m); hanoi(m,'A','B','C'); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) } A B C 1 2 3 3 A B C 0 3 A B C 0 2 A C B 6 3 A B C 0 2 A C B 6 1 A B C 6 A B C 3 A B C 0 2 A C B 6
mall IC 6 i int m 3ABIC O printf("Input the number of disks B scanf(" %od", &m) printf("The steps to moving %/03d 1C|A|B|8 hanoi(m,A, B,C) 2ACBI 6 (0)} 3ABCO void hanoi(int n, char x, char y, char z (2)if(n=1) move(l,xz). B (4) else& (5 hanoi(n-1,x, z,y); 2ACB6 move(n, x, z); 3ABCO hanoi(n-1y, z) 3ABCI O (9)}
main() { int m; printf("Input the number of disks scanf("%d",&m); printf("The steps to moving %3d hanoi(m,'A','B','C'); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) } A B C 3 A B C 0 2 A C B 6 1 C A B 8 A B C 3 A B C 0 2 A C B 6 3 A B C 0 3 A B C 0 2 A C B 6