数据结构栈与队列详解.ppt

数据结构---第三章 栈和队列 * 例2. Hanoi塔问题 P55-3.5 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); //将n-1个圆盘从x移到y上，z为辅助塔座 move (x，n，z); //将编号n的圆盘从x移到z hanoi (n-1, y, x, z); //将n-1个圆盘从y移到z上，x为辅助塔座 } }//hanoi x y z 源 辅助 目标 数据结构---第三章 栈和队列 * void hanoi(3,a,b,c) { if 3==1 move(a,1,c) else { hanoi(2,a,c,b); move(a,3,c); hanoi(2,b,a,c); } } void hanoi(2,a,c,b) { if 2==1 move(a,1,b) else { hanoi(1,a,b,c); move(a,2,b); hanoi(1,c,a,b) } } void hanoi(1,a,b,c) { if 1==1 move(a,1,c) ; else {……} } void hanoi(1,c,a,b) { if 1==1 move(c,1,b) ; else {…… } } void hanoi(2,b,a,c) { if 2==1 move(b,1,c) else { hanoi(1,b,c,a); move(b,2,c); hanoi(1,a,b,c); } } void hanoi(1,b,c,a) { if 1==1 move(b,1,a) ; else {…… } } void hanoi(1,a,b,c) { if 1==1 move(a,1,c) ; else {…… } } a b c 数据结构---第三章 栈和队列 * [递归算法的实现原理] 1 2 3 s 1 2 3 - 利用栈，栈中每个元素称为工作记录，分成三个部分： 返回地址 实在参数表(变参和值参) 局部变量 - 发生调用时，保护现场，即当前的工作记录入栈，然后 转入被调用的过程 - 一个调用结束时，恢复现场，即若栈不空，则退栈，从 退出的返回地址处继续执行下去 代码区 静态数据区 动态数据区 数据结构---第三章 栈和队列 * [递归时系统工作原理示例] int Factorial( int n) { L1: if ( n==0 ) L2: return 1; L3: else return n*Factorial(n-1); L4: } //Factorial void main(void) { …… L0: N=Factorial(3); …… } //main 返回地址 n Factorial N L0 3 / / L3 3 / L3 2 / L3 1 / 1 1 2 6 数据结构---第三章 栈和队列 * [递归算法的用途] 求解递归定义的数学函数 在以递归方式定义的数据结构上的运算/操作 可用递归方式描述的解决过程 [递归算法的特点] 递归算法简单明了，直观易懂 时间效率低，空间开销大，算法不易优化 数据结构---第三章 栈和队列 * [递归转换为非递归的方法] 1）采用迭代算法 递归—从顶到底 迭代—从底到顶