第七讲 栈的应用

1、数据结构数据结构信息工程系信息工程系2022-4-23滨州学院计算机科学技术系1第三章第三章 栈和队列栈和队列栈的应用栈的应用信息工程系信息工程系22022-4-23滨州学院计算机科学技术系2复习与回顾复习与回顾v栈的特点栈的特点v栈的基本术语栈的基本术语v链栈链栈v顺序栈顺序栈信息工程系信息工程系32022-4-23滨州学院计算机科学技术系3 栈的应用举例栈的应用举例一、一、 数制转换数制转换二、二、 括号匹配的检验括号匹配的检验三、三、 表达式求值表达式求值四、四、 实现递归实现递归 本讲内容本讲内容信息工程系信息工程系42022-4-23滨州学院计算机科学技术系4 算法基于原理算法基于原

2、理：“除基取余法除基取余法” 即：除以基数取余数，逆序排列。即：除以基数取余数，逆序排列。 一、一、 数制转换数制转换信息工程系信息工程系52022-4-23滨州学院计算机科学技术系5例如：（例如：（1348)10 = (2504)8 ，其运算，其运算过程如下：过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序信息工程系信息工程系62022-4-23滨州学院计算机科学技术系6void conversion () InitStack(S); scanf (%d,N); while (N) Push(S,

3、 N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion信息工程系信息工程系72022-4-23滨州学院计算机科学技术系7二二. 括号匹配的检验括号匹配的检验v括号匹配问题括号匹配问题 括号匹配 ( ) ， ( ( ) )， ( ) 括号不匹配 ( ( )，( ) ， ( ) 检验括号匹配的方法：“期待的急迫程度”v检查括号匹配的算法检查括号匹配的算法 设一栈 遇到左括号则入栈， 遇到右括号时，若栈空，则不匹配(右括号太多)；否则，如果栈顶元素与该右括号匹配，则出栈；否则不匹配(括号不配对)

4、。 输入结束后，若栈为空，则匹配，否则不匹配(左括号太多)。信息工程系信息工程系82022-4-23滨州学院计算机科学技术系81.算术表达式的组成算术表达式的组成操作数（运算对象或运算量）操作数（运算对象或运算量）运算符运算符界限符（如圆括号，作用是改变运算次序）界限符（如圆括号，作用是改变运算次序） 其中操作数可以是常量、变量、函数、表达式其中操作数可以是常量、变量、函数、表达式运算符有单目、双目，运算符有单目、双目， 我们仅以我们仅以+、-、*、/四种运算为例四种运算为例三三. （算术）表达式的求值（算术）表达式的求值信息工程系信息工程系92022-4-23滨州学院计算机科学技术系9 2.

5、常见表达式有几种常见表达式有几种: (根据运算符在表达式中的不同位置根据运算符在表达式中的不同位置) 3 * ( 5 2 )v中缀表达式中缀表达式 3 * ( 5 2) v后缀表达式后缀表达式 v前缀表达式前缀表达式 3 5 2 - * 3 - 5 2信息工程系信息工程系102022-4-23滨州学院计算机科学技术系10三种表达式的特点三种表达式的特点v操作数之间的相对次序不变操作数之间的相对次序不变v运算符的相对次序可能不同运算符的相对次序可能不同v中缀式：中缀式：必须有括号信息，否则运算顺序改变必须有括号信息，否则运算顺序改变v前缀式：前缀式：无括号；连续出现的两个操作数和在无括号；连续出

6、现的两个操作数和在它们之前出现且紧靠它们的运算符构成了一个它们之前出现且紧靠它们的运算符构成了一个最小表达式最小表达式v后缀式：后缀式：无括号；无括号；运算符的排列顺序就是计算运算符的排列顺序就是计算顺序顺序，每个运算符加上在它之前且紧靠它的两，每个运算符加上在它之前且紧靠它的两个操作数构成了一个最小表达式。个操作数构成了一个最小表达式。信息工程系信息工程系112022-4-23滨州学院计算机科学技术系113.后缀表达式的计算后缀表达式的计算（仅讨论个位数运算）（仅讨论个位数运算） 算法算法自左至右读取表达式中的字符自左至右读取表达式中的字符设一栈存放操作数设一栈存放操作数当读到运算符时，则取

7、出栈顶的两个当读到运算符时，则取出栈顶的两个数进行运算，将结果入栈数进行运算，将结果入栈最终结果保存在栈中。最终结果保存在栈中。信息工程系信息工程系122022-4-23滨州学院计算机科学技术系12int Postfix ( )InitStack(S);read(c);while ( c != = ) if( isdigit(c) ) read(v); Push(S,v); else Pop(S,b); Pop(S,a);Push(S, Operate(a,c,b);read(c);Pop ( S, result );return result;信息工程系信息工程系132022-4-23滨州学

8、院计算机科学技术系13后缀表达式求值后缀表达式求值 用用实型数栈实型数栈S存放计算后缀式的存放计算后缀式的中间及最终结果中间及最终结果，求值算，求值算法可描述如下法可描述如下: n 栈初始化。栈初始化。 n 从左到右扫描从左到右扫描后缀表达式后缀表达式，重复下述两步操作，直到，重复下述两步操作，直到表达式尾。表达式尾。 w 从表达式中取出下个从表达式中取出下个TOKEN(操作数、运算符操作数、运算符) w CASE TOKEN OF w 操作数操作数：将操作数直接：将操作数直接入栈入栈S; w 运算符运算符：出栈两个操作数出栈两个操作数，对其，对其进行进行TOKEN操作操作，结果压入栈结果压入

9、栈Sn 当遇到后缀表达式结束，栈顶的值就是结果当遇到后缀表达式结束，栈顶的值就是结果(应是栈中应是栈中唯一元素唯一元素)。信息工程系信息工程系142022-4-23滨州学院计算机科学技术系148 3 5 +5 6 2 / - *- # 求值求值883835+83+5=8888562/6/2=38853-885-3=22*88*2=1616-8-16=-8-8信息工程系信息工程系152022-4-23滨州学院计算机科学技术系154.中缀表达式转化为后缀表达式中缀表达式转化为后缀表达式v分析分析 中缀表达式中缀表达式 1+2*3+(4*5+6)*7 后缀表达式后缀表达式 1 2 3 *+4 5 *

10、6 +7 *+v算法算法 读到操作数时立即输出读到操作数时立即输出 运算符存放在栈中，遇到运算符时，弹运算符存放在栈中，遇到运算符时，弹出当前栈顶运算符直到遇到优先级更低出当前栈顶运算符直到遇到优先级更低的运算符为止。的运算符为止。信息工程系信息工程系162022-4-23滨州学院计算机科学技术系16中缀表达式转为后缀表达式中缀表达式转为后缀表达式 设设中缀表达式中缀表达式和和后缀表达式后缀表达式分别在数组分别在数组IFX和和PFX中，用中，用栈栈S实现中缀式转为后缀式，实现中缀式转为后缀式， 对对IFX中表达式从左到右扫描，设中表达式从左到右扫描，设TOKEN是扫描读到的符号，转换算法可描述

11、如下。是扫描读到的符号，转换算法可描述如下。 n栈初始化。栈初始化。 n从左到右扫描数组从左到右扫描数组IFX，重复下述两步操作，重复下述两步操作，直到表达式尾。直到表达式尾。 信息工程系信息工程系172022-4-23滨州学院计算机科学技术系17 从从IPX中取出中取出TOKEN(数字、运算符、左括号、右括号数字、运算符、左括号、右括号)； CASE TOKEN OF w ( ：压：压 入栈入栈 S; w 操作数：将操作数直接送入操作数：将操作数直接送入PFX，后面加一个空格，后面加一个空格;w 运算符：如栈空或运算符：如栈空或TOKEN比栈顶元素优先级高，将比栈顶元素优先级高，将 TOKE

12、N进栈；进栈；否则，将栈内优先级高于或等于否则，将栈内优先级高于或等于TOKEN的的运算符，退栈并将退栈元素送入运算符，退栈并将退栈元素送入PFX； w ) ：退栈并将退栈元素送退栈并将退栈元素送PFX，直到碰到左括号，直到碰到左括号，左括号退栈不送左括号退栈不送PFX。w 结束符号结束符号: 连续退栈并送退栈元素到连续退栈并送退栈元素到PFX，直至栈空。，直至栈空。信息工程系信息工程系182022-4-23滨州学院计算机科学技术系18举例：将中缀表达式举例：将中缀表达式 8-(3+5)*(5-6/2)#转为后缀表达式转为后缀表达式8 8 3 8 3 5 8 3 5 + 8 3 5 +5 8

13、3 5 +5 6 8 3 5 +5 6 2 8 3 5 +5 6 2 / - 8 3 5 +5 6 2 / - *- 信息工程系信息工程系192022-4-23滨州学院计算机科学技术系19表达式转换的简单方法表达式转换的简单方法中缀表达式转为后缀表达式有三步：中缀表达式转为后缀表达式有三步： （1）将中缀表达式中所有的）将中缀表达式中所有的子表达式子表达式按按计算规则计算规则用用嵌套括号括起来；嵌套括号括起来； （2）顺序将每对括号中的运算符移到相应括号的后）顺序将每对括号中的运算符移到相应括号的后面；面； （3）删除所有括号。）删除所有括号。 例如，将中缀表达式例如，将中缀表达式8-(3+5

14、)*(5-6/2）转为后缀表达式。按）转为后缀表达式。按如上步骤：如上步骤： w执行完上面第一步后为：执行完上面第一步后为：( 8- ( (3+5) * (5- (6/2) ) ) )； w执行完上面第二步后为：执行完上面第二步后为：(8 (3 5 )+ (5 (6 2 )/ ) - ) * ) - ； w执行完上面第三步后为：执行完上面第三步后为：8 3 5 +5 6 2 /-*- 信息工程系信息工程系202022-4-23滨州学院计算机科学技术系20作业作业v用栈实现将中缀表达式用栈实现将中缀表达式 10+(18+9*3)/15-6# 转换成后缀表达式转换成后缀表达式并进行后缀表达并进行后

15、缀表达式的计算，分别式的计算，分别画出两个步骤中的栈的画出两个步骤中的栈的变化示意图。变化示意图。信息工程系信息工程系21四四. . 栈与递归栈与递归1.函数调用与返回的过程函数调用与返回的过程2.递归函数递归函数3.递归的设计原则递归的设计原则4.递归的优点和缺点递归的优点和缺点5.消除递归消除递归信息工程系信息工程系221.函数调用与返回的过程函数调用与返回的过程（1）函数调用函数调用 当在一个函数的运行期间调用另一个函数时，在当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，运行该被调用函数之前，需先完成三项任务：需先完成三项任务： 将返回地址、所有实参等信息传递给被调用将

16、返回地址、所有实参等信息传递给被调用函数保存；函数保存； 为被调用函数的局部变量分配存储区；为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。将控制转移到被调用函数的入口。信息工程系信息工程系231.函数调用与返回的过程函数调用与返回的过程（2）函数返回）函数返回从被调用函数返回调用函数之前，应该完成下列从被调用函数返回调用函数之前，应该完成下列三项任务：三项任务： 保存被调函数的计算保存被调函数的计算结果结果； 释放被调函数保存释放被调函数保存局部变量局部变量的数据区；的数据区； 依照被调函数保存的依照被调函数保存的返回地址返回地址将将控制转移控制转移到调到调用函数。用函数。

17、v函数嵌套调用时，后调用的函数先返回。函数嵌套调用时，后调用的函数先返回。信息工程系信息工程系241.int main()2.3.int n = 10;4.int sn;5.sn = sum(n);6.cout sn endl;7.8.int sum ( int n )9.10.int i, s = 0;11.for( i=1; in; i+)12.s += i;13.return s;14.1.int main()2.3.int n = 10;4.int sn;5.sn = sum(n);6.cout sn endl;7.8.int sum ( int n )9.10.int i, s =

18、0;11.for( i=1; idata); if ( L-next != NULL ) PrintLinkList (L-next); LL-next以后将要学习的以后将要学习的广义表、广义表、树和二叉树树和二叉树等结构也具有等结构也具有递归的特点，所以常常使递归的特点，所以常常使用递归算法。用递归算法。递归过程的应用（递归过程的应用（2）（2）数据结构是递归的：）数据结构是递归的： 打印链表中各结点的值打印链表中各结点的值信息工程系信息工程系31递归过程的应用（递归过程的应用（3）问题存在递归的解决方法问题存在递归的解决方法w n阶Hanoi塔问题：假设有三个分别命名为X,Y,Z的塔座，在

19、X塔座上插有n个直径大小各不相同，依小到大编号为1，2，,n的圆盘，要求：把X上的n个圆盘移到Z上，排列顺序相同，移动规则为： 每次只能移动一个园盘；每次只能移动一个园盘； 园盘可以在任一塔上做多次移动；园盘可以在任一塔上做多次移动； 在任何时刻，大盘不能压在小盘的上面在任何时刻，大盘不能压在小盘的上面。XYZ信息工程系信息工程系32栈与递归的实现栈与递归的实现:Hanoiw 数学归纳法 nn = 1, OK; n设设n = k 时，时， 若可以以若可以以Y为辅助塔，把为辅助塔，把k个盘从个盘从X移动到移动到Z; n当当n = k + 1时，方法：时，方法： 把把X中中k个盘，以个盘，以Z为辅

20、助塔，移动到为辅助塔，移动到Y; 把把X中第中第k+1个盘，移动到个盘，移动到Z; 把把Y中中k个盘，以个盘，以X为辅助塔，移动到为辅助塔，移动到Z;信息工程系信息工程系33问题存在递归的解决方法问题存在递归的解决方法 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,

21、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 ); 信息工程系信息工程系343.递归的设计原则递归的设计原则v如果递归设计不当如果递归设计不当 容易造成容易造成无穷递归无穷递归，最终会耗尽应用程序最终会耗尽应用程序的栈空间，导致的栈空间，导致栈溢栈溢出错误出错误，使程序失败，使程序失败。/ 无穷递归的例子无穷递归的例子/ 讲不完的故事讲不完的

22、故事void Story () print ( “从前有座山，从前有座山，山上有个庙，庙里有个和山上有个庙，庙里有个和尚在讲故事：尚在讲故事：” ); Story();信息工程系信息工程系353.递归的设计原则递归的设计原则（1）基准情形 必须存在不用继续递归即可解决的情况。必须存在不用继续递归即可解决的情况。（2）不断推进 对于需要递归解决的情况，每一次递归都对于需要递归解决的情况，每一次递归都要使得求解朝着基准情况的方向推进。要使得求解朝着基准情况的方向推进。（3）递归可递归可行性 假设所有的递归调用都能运行。假设所有的递归调用都能运行。（4）合成效益 解决一个问题时，解决一个问题时，切勿

23、在不同的递归调用切勿在不同的递归调用中做重复的工作中做重复的工作。信息工程系信息工程系36v一个不符合合成效益法则的例子：一个不符合合成效益法则的例子：long Fib ( int n ) if ( n=1 ) return 0; if ( n=2 ) return 1; return Fib(n-1)+Fib(n-2);Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)信息工程系信息工程系374.递归的优点和缺点递归的优点和缺点v优点： 递归函数结构清晰，程序易读，正确性容递归函数结构清晰，程序易读，正确性容易证明。易证明。v缺点： 反复的递归函数调用使得执行效率较低。反复的递归函数调用使得执行效率较低。信息工程系信息工程系385.消除递归消除递归v为什么消除递归？ 某些语言不支持函数的递归调用。某些语言不支持函数的递归调用。 在某些关键部分，递归算法影响了执行在某些关键部分，递归算法影响了执行的效率。的效率。v如何消除递归？ （1）转化为）转化为递推（循环递推（循环）。 （2）自己管理