第七讲栈的应用要点分析.ppt

滨州学院计算机科学技术系 第三章 栈和队列 栈的应用 1.函数调用与返回的过程 （1）函数调用 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务： 将返回地址、所有实参等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 1.函数调用与返回的过程 （2）函数返回从被调用函数返回调用函数之前，应该完成下列三项任务： 保存被调函数的计算结果； 释放被调函数保存局部变量的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。 函数嵌套调用时，后调用的函数先返回。 int main() { int n = 10; int sn; sn = sum(n); cout sn endl; } int sum ( int n ) { int i, s = 0; for( i=1; in; i++) s += i; return s; } int main() { int n = 10; int sn; sn = sum(n); cout sn endl; } int sum ( int n ) { int i, s = 0; for( i=1; in; i++) s += i; return s; } 2. 递归函数 函数直接或间接调用自身，称为递归(Recursion)。 何时应用递归？ 问题具有递归的数学定义 使用了递归的数据结构 问题存在递归的解决方法 void PrintLinkList ( LinkList L ) { if(L!=NULL){ printf (L-data); if ( L-next != NULL ) { PrintLinkList (L-next); } } } 问题存在递归的解决方法 Hanoi (n, a, b, c)表示解决n个盘子的汉诺塔问题 （从a搬到c，可以借助b）。 解决方法： 若n=1，直接将盘子从a搬到c即可； 否则，可以分解为如下步骤： Hanoi ( n-1, a, c, b ) move ( n, a, c ) Hanoi ( n-1, b, a, c ) void Hanoi ( int n, char a, char b, char c ) { if ( n==1 ) move ( n, a, c ); else { Hanoi ( n-1, a, c, b ); move ( n, a, c ); Hanoi ( n-1, b, a, c ); } } 3.递归的设计原则 如果递归设计不当… 容易造成无穷递归，最终会耗尽应用程序的栈空间，导致栈溢出错误，使程序失败。 // 无穷递归的例子 // 讲不完的故事 void Story (){ print ( “从前有座山，山上有个庙，庙里有个和尚在讲故事：” ); Story(); } 3.递归的设计原则 （1）基准情形 必须存在不用继续递归即可解决的情况。 （2）不断推进 对于需要递归解决的情况，每一次递归都要使得求解朝着基准情况的方向推进。 （3）递归可行性 假设所有的递归调用都能运行。 （4）合成效益 解决一个问题时，切勿在不同的递归调用中做重复的工作。 一个不符合合成效益法则的例子： 4.递归的优点和缺点 优点： 递归函数结构清晰，程序易读，正确性容易证明。 缺点： 反复的递归函数调用使得执行效率较低。 5.消除递归 为什么消除递归？ 某些语言不支持函数的递归调用。 在某些关键部分，递归算法影响了执行的效率。 如何消除递归？ （1）转化为递推（循环）。 （2）自己管理一个递归工作栈。 （1）递归和递推 使用递推可以有效减少函数递归调用的次数，节省了时间和空间。 （1）递归和递推 long Fib ( int n ) { if ( n==1 ) return 0; if ( n==2 ) return 1; long f1,f2,f3; f1 = 0, f2 = 1; for (int i=3; i=n; i++) { f3 = f2+f1; f1 = f2; f2 = f3; } return f3; } （1）递归和递推 如果只在函数结尾处进行递归调用，称为尾递归。 一般地，尾递归都可以转化为简单的循环。 消除尾递归 void PrintLinkList ( LinkList L ){ if