《栈和队列B【重要课资】》由会员分享，可在线阅读，更多相关《栈和队列B【重要课资】（18页珍藏版）》请在金锄头文库上搜索。
1、问：为什么要设计堆栈？它有什么独特用途？问：为什么要设计堆栈？它有什么独特用途？1.简化了程序设计的问题简化了程序设计的问题；2.递归运算的有力工具；递归运算的有力工具；3.用于保护现场和恢复现场；用于保护现场和恢复现场；4.调用函数或子程序非它莫属调用函数或子程序非它莫属 。答：答：第三章第三章 栈和队列栈和队列1课堂使用 括号匹配的检验括号匹配的检验 P49 设计思路：用栈暂存左括号设计思路：用栈暂存左括号例例3：行编辑程序行编辑程序 P49 设计思路：用栈存放输入的字符设计思路：用栈存放输入的字符例例4：表达式求值表达式求值 P52 设计思路：用栈暂存运算符设计思路：用栈暂存运算符例例5
2、：汉诺仪（汉诺仪（Hanoi）塔）塔-P55 设计思路：用栈实现递归调用设计思路：用栈实现递归调用例例2：3.2 栈的应用举例栈的应用举例 2课堂使用例例2：括号匹配的检验：括号匹配的检验3课堂使用void LineEdit( ) 算法3.2 InitStack(s); ch=getchar(); while(ch!=EOF) while(ch!=EOF&ch!=/n) switch(ch) case #: Pop(S,c); break; case : ClearStack(S); break; default: Push(S,ch); break; ch=getchar(); 将从栈底到栈
3、顶的字符传送到调用过程的数据区；将从栈底到栈顶的字符传送到调用过程的数据区；ClearStack(S); if (ch!=EOF) ch=getchar(); DestroyStack(S); /LineEdit4课堂使用例例4 4 表达式求值表达式求值问题的提出：问题的提出： 设计一个小计算器设计一个小计算器: : 对键入的表达式进行求值。对键入的表达式进行求值。 高级语言中的赋值语句：变量=表达式；Y=2;Y=2;Z=3;Z=3;X=y+z*2;X=y+z*2;如何对表达式求值呢？5课堂使用表达式求值的算法是表达式求值的算法是 “算符优先法算符优先法”。例如：例如：3*（7 2 ） （1）
4、要正确求值，首先了解算术四则运算的规则：）要正确求值，首先了解算术四则运算的规则： a. 从左算到右从左算到右 b. 先乘除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为： 3*（7 2 ）= 3 * 5 = 156课堂使用（2 2）比较优先权关系）比较优先权关系 根据上述三条运算规则，在运算的每一步中，对任根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符意相继出现的算符 1 1和和 2 2 ，都要比较优先权关系。，都要比较优先权关系。算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见教
5、材见教材P53P53表表3.13.1 （是提供给计算机用的表！）（是提供给计算机用的表！）栈的应用（表达式求值）栈的应用（表达式求值）7课堂使用算符优先关系表算符优先关系表 表达式中任何相邻运算符表达式中任何相邻运算符c1、c2的优先关系有：的优先关系有： c1c2：c1的优先级高于的优先级高于c2+ c2 c1 -*/()#+ - * / ( ) # = 算符间的优先关系表算符间的优先关系表注：注： c1 c2是相邻算符，是相邻算符， c1在左，在左， c2在右在右由表可看出，右括号由表可看出，右括号 ) 和井号和井号 # 作为作为 2时时级别最低；级别最低；由由c 规则得出：规则得出： *
6、 ，/， + ，-为为 1时时的优先权低于的优先权低于（，高于，高于）由由a规则得出：规则得出：（=） 表明括号内运算已算完。表明括号内运算已算完。 # = # 表明表达式求值完毕。表明表达式求值完毕。8课堂使用（3）算法思想：）算法思想：设定两栈：设定两栈：操作符栈操作符栈 OPTR ，操作数栈，操作数栈 OPND栈初始化栈初始化：设操作数栈：设操作数栈 OPND 为空；操作符栈为空；操作符栈 OPTR 的栈的栈底元素为表达式起始符底元素为表达式起始符 #；依次读入字符依次读入字符：是操作数则入：是操作数则入OPND栈，是操作符则要判断：栈，是操作符则要判断： if 操作符操作符 栈顶元素，
7、压入栈顶元素，压入OPTR栈。栈。栈的应用（表达式求值）栈的应用（表达式求值）9课堂使用栈的应用（表达式求值）栈的应用（表达式求值）OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd
8、)10课堂使用Status EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR);Push(OPTR ,#);c=getchar(); while(c!=#)|(GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c); c=getchar(); else switch(precede(GetTop(OPTR),c) case : Pop(OPTR,theta); Pop(opnd,b); Pop(opnd,a); result= Operate(a,theta,b);P
9、ush(OPND,result);result= Operate(a,theta,b);Push(OPND,result); break; /switch /while return(GetTop(OPND); /EvaluateExpression11课堂使用例例5 5 汉诺仪（汉诺仪（ HanoiHanoi）塔）塔传说在创世纪时，在一个叫传说在创世纪时，在一个叫BrahmaBrahma的寺庙里，有三个柱子，其中的寺庙里，有三个柱子，其中一柱上有一柱上有6464个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这6464个盘个盘子从一根柱子移到另一个柱子上。子从一
10、根柱子移到另一个柱子上。 移动时的规则：移动时的规则： 每次只能移动一个盘子；每次只能移动一个盘子； 只能小盘子在大盘子上面；只能小盘子在大盘子上面； 可以使用任一柱子。可以使用任一柱子。当工作做完之后，就标志着世界末日到来。当工作做完之后，就标志着世界末日到来。分析：分析： 设三根柱子分别为设三根柱子分别为 x，y, z , 盘子在盘子在 x 柱上，要移到柱上，要移到 z 柱上。柱上。1、当、当 n=1 时，盘子直接从时，盘子直接从 x 柱移到柱移到 z 柱上；柱上；2、当、当 n1 时时, 则则设法将设法将 前前 n 1 个盘子个盘子 借助借助 z ，从，从 x 移移到到 y 柱上，把柱上
11、，把 盘子盘子 n 从从 x 移到移到 z 柱上；柱上； 把把n 1 个盘子个盘子 从从 y 移到移到 z 柱上。柱上。x y zx y znn 112课堂使用Void Hanoi ( int n, char x, char y, char z ) /将将 n 个个 编号从上到下为编号从上到下为 1n 的盘子从的盘子从 x 柱，借助柱，借助 y 柱移到柱移到 z 柱柱 if ( n = = 1 ) move ( x , 1 , z ) ; /将编号为将编号为 1 的的盘子盘子从从 x 柱移到柱移到 z 柱柱 else Hanoi ( n-1 , x , z , y ) ; /将将 n -1个个
12、 编号从上到下为编号从上到下为1n-1的盘的盘子从子从 x 柱，借助柱，借助 Z柱移到柱移到 Y柱柱 move ( x , n, z) ; /将编号为将编号为 n 的的盘子盘子从从 x 柱移到柱移到 z 柱柱 Hanoi ( n-1 , y , x , z ); /将将 n -1个个 编号从上到下为编号从上到下为 1n-1的盘子从的盘子从 y 柱，借助柱，借助 x 柱移到柱移到 z 柱柱 /Hanoi13课堂使用3.3 3.3 栈与递归栈与递归一般函数的调用机制一般函数的调用机制 A( )B( );C( )B( )C( );调用调用返回返回函数调用顺序 A B C函数返回顺序 C B A后调用
13、的函数先返回 函数调用机制可通过栈来实现函数调用机制可通过栈来实现计算机正是利用栈来存储函数的计算机正是利用栈来存储函数的返回地址及所有实参返回地址及所有实参14课堂使用3.3 3.3 栈与递归栈与递归当一个函数调用另一个函数时，在调用之前系统要做3件事：1.将所有的实在参数、返回地址等信息传递给被调用函数保存；2.为被调用函数的局部变量分配存储空间；（入栈）3.将控制转移到被调用函数的入口。1.保存被调用函数的计算结果；2.释放被调用函数的数据区；（出栈）3.依照被调用函数保存的地址将控制转移到调用函数。返回时，系统要做3件事：15课堂使用3.3 3.3 栈与递归栈与递归 1 1什么是递归什
14、么是递归 递递归归是是一一个个很很有有用用的的工工具具，在在数数学学和和程程序序设设计计等许多领域中都用到了递归。等许多领域中都用到了递归。递递归归定定义义：简简单单地地说说，一一个个用用自自己己定定义义自自己己的的概概念念, ,称称为递归定义。为递归定义。例例 n!= 1* 2* 3* 4 * (n-1)* n n!= 1* 2* 3* 4 * (n-1)* n n! n!递归定义递归定义 n!= 1 n!= 1 当当 n=0 n=0 时时 n!= n (n-1)! n!= n (n-1)! 当当n 0 n 0 时时用用(n-1)!(n-1)!定义定义n!n!16课堂使用2.2.递递归归函函数数：一一个个直直接接调调用用自自己己或或通通过过一一系系列列调调用用间接调用自己的函数称为递归函数。间接调用自己的函数称为递归函数。 A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接调用自己直接调用自己B间接调用自己间接调用自己17课堂使用小结小结简化了程序设计的问题；简化了程序设计的问题；递归运算的有力工具；递归运算的有力工具；用于保护现场和恢复现场；用于保护现场和恢复现场；调用函数或子程序非它莫属调用函数或子程序非它莫属 。作业：递归预习作业：递归预习3.318课堂使用
