stack数据结构课件.pptVIP

例1 递归的执行情况分析 void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i=w;++i) printf(“%3d ”,w); printf(“/n”); } } 运行结果： 1 2 2 3 3 3 栈的应用：递归过程及其实现 递归调用执行情况如下： 主程序 print(w-1) w=3; print(w-1); 2 w print(w-1); 1 w 0 w 输出：1 (2) 2 (1) 3 top (3) 1 (2) 2 (1) 3 top 输出:2 2 (1 ) 3 top 返回 (3) 1 (2) 2 (1) 3 top i=1~3, print(w) i=1~2,print(w) i=1~1, print(w) 输出:3 3 3 void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i=w;++i) printf(“%3d ”,w); printf(“/n”); } } 汉诺塔问题 现有命名为A，B，C的塔座，A塔座上从下到上按金字塔状叠放着n个不同大小的圆盘，编号为1,2,3……n。现在把所有盘子一个一个移动到塔座C上，并且每次移动同一根塔座上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n）。移动时可以用塔座B做辅助塔座。 首先我们肯定是把上面n-1个盘子移动到柱子B上，然后把最大的一块放在C上，最后把B上的所有盘子移动到C上。　　 void hanoi(int n,char A,char C,char B) { // 将塔座A上按直径由小到大且自上而下编号为1至n的n个圆盘 // 按规则搬到塔座B上。C可用作辅助塔座 if(n==1) // (出口) move(A,1,B); // 将编号为的圆盘从A移到B else { hanoi(n-1,A,B,C); // 将A上编号为1至n-1的圆盘移到C，B作辅助塔(降阶递归调用) move(A,n,B); // 将编号为n的圆盘从A移到B hanoi(n-1,C,A,B); // 将C上编号1为至n-1的圆盘移到B，A作辅助塔(降阶递归调用) } } Hanoi(4,A,C,B) n=4 Hanoi(4,A,B,C) Move(A,4,B) 4从A-----?B (8) Hanoi(3,C,A,B) n=3 Hanoi(2,A,C,B) Move(A,3,C) 3从A--?C (4) Hanoi(2,B,A,C) n=2 Hanoi(1,A,B,C) 1从A---?C (1) Move(A,2,B) 2从A----?B (2) Hanoi(1,C,A,B) 1从C-----?B (3) n=2 Hanoi(1,B,C,A) 1从B---?A (5) Move(B,2,C) 2从B----?C (6) Hanoi(1,A,B,C) 1从A-----?C (7) n=3 Hanoi(2,C,B,A) Move(C,3,B) 3从A--?C (12) Hanoi(2,A,C,B) n=2 Hanoi(1,C,A,B) 1从C---?B (9) Move(C,2,A) 2从C----?A (10) Hanoi(1,B,C,A) 1从B-----?A (11) n=2 Hanoi(1,A,B,C) 1从A---?C (13) Move(A,2,B) 2从A----?B (14) Hanoi(1,C,A,B) 1从C-----?B (15) ---Reverse Polish Notation ---Reverse Polish Notation 例如考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2