栈和队列Bppt课件

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+zX=y+z* *2;2;如何对表达式求值呢？5;.表达式求值的算法是表达式求值的算法是 “算符优先法算符优先法”。例如：例如：3*（7 2 ） （1）要正确求值

4、，首先了解算术四则运算的规则：）要正确求值，首先了解算术四则运算的规则： a. 从左算到右从左算到右 b. 先乘除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为： 3*（7 2 ）= 3 * 5 = 156;.（2 2）比较优先权关系）比较优先权关系 根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符 1 1和和 2 2 ，都要比较优先，都要比较优先权关系。权关系。算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见教材见教材P53

5、P53表表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 操作符操作符 栈顶元素，压入栈顶元素，压入OP

7、TR栈。栈。栈的应用（表达式求值）栈的应用（表达式求值）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)10;.Status E

8、valuateExpression( 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); break; /switch /while return(GetTop(OPN

9、D); /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 柱上，把柱上，把 盘子盘子 n 从从 x 移移到到 z 柱上；柱上； 把把n 1 个盘子个盘子 从从 y 移到移到 z 柱上。柱上。x y zx y znn 112;.Void Hanoi ( int n, char x

11、, 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个个 编号从上到下为编号从上到下为1n-1的盘子从的盘子从 x 柱，借助柱，借助 Z柱移到柱移到 Y柱柱 move ( x , n, z) ; /将编号为将编号为 n 的盘子从的盘子从 x 柱移到柱移到 z 柱柱 H

12、anoi ( 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后调用的函数先返回 函数调用机制可通过栈来实现函数调用机制可通过栈来实现计算机正是利用栈来存储函数的返回地计算机正是利用栈来存储函数的返回地址及所有实参址及所有实参14;.3.3 3.3 栈与递归栈与递归当一个函数调用另一

13、个函数时，在调用之前系统要做3件事：1.将所有的实在参数、返回地址等信息传递给被调用函数保存；2.为被调用函数的局部变量分配存储空间；（入栈）3.将控制转移到被调用函数的入口。1.保存被调用函数的计算结果；2.释放被调用函数的数据区；（出栈）3.依照被调用函数保存的地址将控制转移到调用函数。返回时，系统要做3件事：15;.3.3 3.3 栈与递归栈与递归 1 1什么是递归什么是递归 递归是一个很有用的工具，在数学和程序设计等许多领域中都用到了递归。递归是一个很有用的工具，在数学和程序设计等许多领域中都用到了递归。递归定义：简单地说，一个用自己定义自己的概念递归定义：简单地说，一个用自己定义自己的概念, ,称为递归定义。称为递归定义。例例 n!= 1n!= 1* * 2 2* * 3 3* * 4 4 * * (n-1) (n-1)* * n 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.递归函数：一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。递归函