删除操作的一端称为栈顶Top-Read.PPT

2）递归结构 例 求n的阶乘 ＃include stdio.h lang fac(int n) 1: { lang L; 2: if(!n) L=1; 3: else L=n*fac(n-1); 4: return L; 5: } int main() a: { int n; b: lang L; c: scanf(“%d”,n); d: L=fac(n); e: printf(“%ld”,L); f: } (1) 若栈顶运算符的优先级低于刚读入的运算符， 则让刚读入的运算符进operator栈；  (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、 b进行θ运算后， 将运算结果作为中间结果推入operand栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。 3.3 栈与递归的实现 栈非常重要的一个应用是在程序设计语言中用来实现递归。 递归是指在定义自身的同时又出现了对自身的调用。 如果一个函数在其定义体内直接调用自己，则称其为直接递归函数；如果一个函数经过一系列的中间调用语句， 通过其它函数间接调用自己，则称其为间接递归函数。 1. 递归特性问题 1) 递归函数 例如， 很多数学函数是递归定义的， 如二阶Fibonacci数列： 递归过程的实现 一个函数调用另一个函数时，在运行被调用函数之前，系统做的工作有：  (1) 保留本层参数与返回地址（将所有的实在参数、 返回地址等信息传递给被调用函数保存）；  (2) 给下层参数赋值（为被调用函数的局部变量分配存储区）； (3) 将程序转移到被调函数的入口。  而从被调用函数返回调用函数之前，系统也应完成三件工作：  (1) 保存被调函数的计算结果；  (2) 恢复上层参数（释放被调函数的数据区）；  (3) 依照被调函数保存的返回地址， 将控制转移回调用函数。 当多个函数调用时按后调用先返回的原则。 系统将整个程序运行时所需的数据空间安排在一个栈中， 每次调用一个函数时就为它在栈顶分配一个存储区，当一个 函数返回时就释放它的存储区，当前正在运行的函数所有数 据必在栈顶。 void first(int,int); void first(int s,int t) void second(int); { void main() int i; { …… int m,n; sencond(i); …… 2: first(m,n); …… 1: } …… void second(int d) { } int x,y; …… } 例：n阶Hanoi塔问题：假设有三个分别命名为X、Y和Z的塔座， 在塔座X上插有n个直径大小各不相同、依小到大编号为1， 2, …， n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列原则： (1) 每次只能移动一个圆盘；  (2) 圆盘可以插在X、 Y和Z中的任何一个塔座上；  (3) 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 如何实现移动圆盘的操作呢？当n=1时，问题比较简单，只要将编号为1的圆盘从塔座X直接移动到塔座Z上即可；当n1时， 需利用塔座Y作辅助塔座， 若能设法将压在编号为n的圆盘上的n-1个圆盘从塔座X(依照上述原则)移至塔座Y上， 则可先将编号为n的圆盘从塔座X 移至塔座Z上，然后再将塔座Y上的n-1个圆盘(依照上述原则)移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座问题是一个和原问题具有相同特征属性的问题，只是问题的规模小个1，因此可以用同样方法求解。 由此可得如下算法所示的求解n阶Hanoi塔问题的函数。 void hanoi(int n,char x,char y,char z) /*将塔座X上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座Z上， Y可用作辅助塔座 */ 1 { 2 if(n==1) 3 move(x,1,z); /*