数据结构栈的应用本

1、第三章 栈的应用数制转换“除基取余法除基取余法”算法基于原理算法基于原理除以基数取余数，逆序排列。除以基数取余数，逆序排列。例如：例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序进制转换算法思想1.1.初始化一个空栈初始化一个空栈S S；2.2.当十进制数当十进制数N N非零时，循环执行以下操作：非零时，循环执行以下操作：把把N N与与8 8求余得到的八进制数压入栈求余得到的八进制数压入栈S S；N N更更新为新为N N与与8 8的商。的商。3.3.

2、当栈当栈S S非空时，循环执行以下操作：非空时，循环执行以下操作：弹出栈顶元素弹出栈顶元素e e，然后输出，然后输出e e。void conversion () InitStack(S); scanf (%d,&N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion余数入栈余数入栈余数出栈余数出栈括号匹配括号匹配问题括号匹配问题1.括号匹配括号匹配 ( ) , ( ( ) ), ( )2.括号不匹配括号不匹配 ( ), ( ( ) ), (

3、 ( ) )检验括号匹配的方法：检验括号匹配的方法：“期待的急迫程度期待的急迫程度”检查括号匹配算法的设计思想检查括号匹配算法的设计思想设一栈；设一栈；遇到左括号则入栈；遇到左括号则入栈；遇到右括号时，若栈空，则不匹配遇到右括号时，若栈空，则不匹配( (右括右括号太多号太多) )，否则，如果栈顶元素与该右括，否则，如果栈顶元素与该右括号匹配，则出栈，否则不匹配号匹配，则出栈，否则不匹配( (括号不配括号不配对对) )。输入结束后，若栈为空，则匹配，否则输入结束后，若栈为空，则匹配，否则不匹配不匹配( (左括号太多左括号太多) )。Status Matching()int state = 1;I

4、nitStack(S);ch=getchar();while (ch!=# & state) switch(ch) case (|:Push(S, ch); break; case ): if(!StackEmpty(S)&GetTop(S)=() Pop(S,e); else state = 0; break; case : if( !StackEmpty(S)&GetTop(S) =) Pop(S,e); else state = 0; break; ch=getchar(); if (StackEmpty(S)&state) return OK; else

5、 return ERROR;行编辑程序出现的问题出现的问题每接受一个字符立即存入存储器吗？每接受一个字符立即存入存储器吗？NONO合理的做法合理的做法设立一个输入缓冲区，用以接受用户输入的一行设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设字符，然后逐行存入用户数据区，并假设“#”#”为退格符，为退格符，“”为退行符。为退行符。用户输入用户输入缓存区缓存区（用栈模拟）用户数据区用户数据区入栈入栈出栈出栈假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行： while (*s) putc

6、har(*s+);行编辑程序算法的设计思想行编辑程序算法的设计思想设一栈（输入缓冲区）；设一栈（输入缓冲区）；读入的字符为退格符，则删除栈顶字符；读入的字符为退格符，则删除栈顶字符；读入的字符为退行符，则清空栈；读入的字符为退行符，则清空栈；否则，读入的字符入栈。否则，读入的字符入栈。每处理完一行字符，将栈底到栈顶的字符每处理完一行字符，将栈底到栈顶的字符存入存储器，清空栈，开始进行下一行的存入存储器，清空栈，开始进行下一行的字符处理，直到文件结束。字符处理，直到文件结束。void LineEdit()InitStack(S); /缓存栈Sch=getchar();while (ch != E

7、OF) /EOF为全文结束符 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break;/ 重置S为空栈 case : ClearStack(S); break; default : Push(S, ch); break; ch = getchar(); / 接收本行下一个字符 将从栈底到栈顶的字符传送至调用过程的数据区；将从栈底到栈顶的字符传送至调用过程的数据区；可以借助另一个辅助栈来完成可以借助另一个辅助栈来完成InitStack(S2);. /辅助栈S2while(!EmptyStack(S) /从S栈出来

8、，进入S2Pop(S,e);Push(S2,e);while(!EmptyStack(S2)Pop(S2,e);将e写入用户数据区ClearStack(S); ClearStack(S2);if (ch != EOF) ch = getchar(); /读取下一行字符 DestroyStack(S); DestroyStack(S2);（算术）表达式求值算术表达式的组成算术表达式的组成操作数操作数（运算对象或运算量）运算符运算符界限符界限符（如圆括号，作用是改变运算次序）常量、变量、常量、变量、函数、表达式函数、表达式单目、双单目、双目目以+ +、- -、* *、/ /四种运算为例算术表达式的

9、分类算术表达式的分类根据运算符在表达式中的不同位置中缀表达式 后缀表达式 前缀表达式 例：表达式例：表达式3 * ( 5 2 )3 * ( 5 2 )3 5 2 - * 3 5 2操作数之间的相对操作数之间的相对次序不变；次序不变；运算符的相对次序运算符的相对次序可能不同；可能不同；中缀式必须有括号信息，否则运算中缀式必须有括号信息，否则运算顺序改变；顺序改变；前缀式：无括号；连续出现的两个操作数和在它前缀式：无括号；连续出现的两个操作数和在它们之前出现且紧靠它们的运算符构成了一个们之前出现且紧靠它们的运算符构成了一个最小最小表达式；表达式；后缀式：无括号；运算符的排列顺序就是计算顺后缀式：无

10、括号；运算符的排列顺序就是计算顺序，每个运算符加上在它之前且紧靠它的两个操序，每个运算符加上在它之前且紧靠它的两个操作数构成了一个最小表达式。作数构成了一个最小表达式。三种表达式的特点三种表达式的特点中缀表达式求值设置两个工作栈：设置两个工作栈：运算符栈运算符栈S1S1和和操作数栈操作数栈S2S2。S2S2也放表达也放表达式的运算结果。式的运算结果。算法思想算法思想1 1 、首先置、首先置操作数栈操作数栈S2S2为空栈，置运算符栈为空栈，置运算符栈S1S1的栈底为表达的栈底为表达式的起始符式的起始符 # (# (优先级最低优先级最低) )。 2 2 、依次读入表达式、依次读入表达式中的每个字符

11、中的每个字符chch，直至表达式结束：，直至表达式结束： w 若若chch是是操作数操作数, ,则进则进S2S2栈；栈； w 若若chch是运算符，若其优先级不高于是运算符，若其优先级不高于S1S1栈顶运算符栈顶运算符的优先级时，则取出栈的优先级时，则取出栈S2S2的栈顶和次栈顶的两个元素以及的栈顶和次栈顶的两个元素以及栈栈S1S1的栈顶运算符，进行相应的运算，并将结果放入栈的栈顶运算符，进行相应的运算，并将结果放入栈S2S2中；中；w 如此下去，直至如此下去，直至chch的优先级高于的优先级高于S1S1栈顶运算符的优先级，栈顶运算符的优先级，将将chch入入S1S1栈。栈。OperandTy

12、pe EvaluateExpression( ) InitStack(S1); Push(S1, #); InitStack(S2);c=getchar(); while (c!=#|GetTop(S1)!=#) if (!In(c, OP) Push(S2,c) ;c=getchar(); else / while return GetTop(S2); / EvaluateExpression switch (Precede(GetTop(S1),c) case : Pop(S1, op); Pop(S2, b); Pop(S2, a); Push(S2,Operate(a,op,b); b

13、reak; / switch举例举例: 3*(5-2) 步骤步骤 optroptr栈栈S1 S1 opndopnd栈栈 S2 S2 输入字符输入字符chch 主要操作主要操作 1 # 3*(5-2)# push(s2,3) 2 # 3 *(5-2)# push(s1,*) 3 #* 3 (5-2)# push(s1,() 4 #*( 3 5-2)# push(s2,5) 5 #*( 35 -2)# push(s1,-) 6 #*(- 35 2)# push(s2,2) 7 #*(- 352 )# operate(5,-,2 ) 8 #*( 33 )# pop(s1)消除一对括号 9 #* 33

14、 # operate(3,*,3 ) 10 # 9 # return(gettop(s2)后缀表达式求值1.运算符已经按计算顺序从左到右排好；2.没有括号算法思想算法思想p设一栈设一栈存放操作数；存放操作数；p遇到操作数直接入栈；遇到操作数直接入栈；p遇到运算符，则取出栈顶的两个数进行运遇到运算符，则取出栈顶的两个数进行运算，将结果算，将结果入栈；入栈；p最终结果保存在最终结果保存在栈中（栈中唯一元素）。栈中（栈中唯一元素）。int Postfix ( )InitStack(S);/操作数栈c=getchar();while ( c != # ) if( isdigit(c) ) /操作数入栈

15、Push(S,c); else Pop(S,b); Pop(S,a);Push(S, Operate(a,c,b);c=getchar();Pop(S,result);return result;后缀表达式求值：后缀表达式求值：8 3 5 +5 6 2 / - *- #883835+83+5=8888562/6/2=38853-885-3=22*88*2=1616-8-16=-8-8栈与递归1.1.函数调用与返回的过程函数调用与返回的过程2.2.递归函数递归函数3.3.递归的设计原则递归的设计原则4.4.递归的优点和缺点递归的优点和缺点5.5.消除递归消除递归函数调用与返回的过程函数调用函数调

16、用当在一个函数的运行期间当在一个函数的运行期间调用另一个函数调用另一个函数时，在时，在运行被调用函数之前，需先完成三项任务：运行被调用函数之前，需先完成三项任务：1.1.将所有的实在参数、返回地址等将所有的实在参数、返回地址等信息信息传递给被传递给被调用函数调用函数保存保存；2.2.为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区；3.3.将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。函数调用与返回的过程函数返回函数返回从被调用函数从被调用函数返回返回调用函数调用函数之前之前，应该完成下列，应该完成下列三项任务：三项任务：1.1.保存保存被调函数的被调函数的计算结

17、果计算结果；2.2.释放释放被调函数的被调函数的数据区数据区；3.3.依照被调函数保存的返回地址将依照被调函数保存的返回地址将控制转移控制转移到调到调用函数。用函数。函数函数嵌套调用嵌套调用时，时，后调用后调用的函数的函数先返回先返回。递归函数递归的定义递归的定义函数函数直接或间接直接或间接调用自身，称为递归调用自身，称为递归。(Recursion)(Recursion)递归的应用递归的应用1.1.问题具有递归的数学定义问题具有递归的数学定义2.2.使用了递归的数据结构使用了递归的数据结构3.3.问题存在递归的解决方法问题存在递归的解决方法 阶乘阶乘n!n!、FibonacciFibonacc

18、i数列数列 链表、二叉树链表、二叉树 HanoiHanoi塔问题塔问题递归过程的应用（1）问题的数学定义是递归的问题的数学定义是递归的例例1 1：求：求n n的阶乘的阶乘n n！long Fact(int n) if (n=0) return(1); else return ( n*Fact(n-1) ); 求阶乘(n!)过程的模拟n=3 n=3 fac(3)fac(3)n=2 n=2 F=3F=3* *fac(2)fac(2)n=1 n=1 F=2F=2* *fac(1)fac(1)n=0 n=0 F=1F=1* *fac(0)fac(0)fac(0)fac(0)return fac(3)=

19、3*2*1return fac(2)=2*1return fac(1)=1*1return fac(0)=1这种分解这种分解- -求解的策略叫求解的策略叫“分治法分治法”采用采用“分治法分治法”进行递归求解的问题需进行递归求解的问题需要满足以下三个条件：要满足以下三个条件：1.1.能将一个问题转变成一个新问题，而新问题与能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的原问题的解法相同或类同，不同的仅是处理的对象，并且这些处理对象更小且变化有规律。对象，并且这些处理对象更小且变化有规律。2.2.可以通过上述转化而使问题简化。可以通过上述转化而使问题简化。3.3.必

20、须有一个明确的递归出口，或成递归的边界。必须有一个明确的递归出口，或成递归的边界。void p(参数表)if(递归结束条件成立)可直接求解；elsep(较小的参数);递归过程的应用（1）问题的数学定义是递归的问题的数学定义是递归的例例2 2：计算：计算FibonacciFibonacci数列：数列：0,1,1,2,3,5,8,13,21,0,1,1,2,3,5,8,13,21,long Fib ( int n ) if ( n=1 ) return 0; if ( n=2 ) return 1; return Fib(n-1) + Fib(n-2);递归过程的应用（2）数据结构是递归的数据结构

21、是递归的例例1 1：逆序打印链表中各结点的值 LL-nextvoid PrintLinkList ( LinkList L ) if ( L-next != NULL ) PrintLinkList (L-next); printf (L-next-data); 逆序打印逆序打印带头带头结点的单链表结点的单链表L!=NULL) L-data ) ;逆序打印不带头结点的单链表递归过程的应用（2）数据结构是递归的数据结构是递归的例例2 2：顺序打印链表中各结点的值 LL-nextvoid PrintLinkList ( LinkList L ) if ( L-next != NULL ) prin

22、tf (L-next-data); PrintLinkList (L-next); 顺序打印带头顺序打印带头结点的单链表结点的单链表递归过程的应用（3）问题存在递归的解决方法问题存在递归的解决方法例例1 1：Hanoi塔问题n n阶阶HanoiHanoi塔问题塔问题：假设有三个分别命名为X,Y,Z的塔座，在X塔座上插有n个直径大小各不相同，依小到大编号为1，2，,n的圆盘，要求：把X上的n个圆盘移到Z上，排列顺序相同，移动规则为：1.1.每次只能移动一个圆盘；每次只能移动一个圆盘； 2.2.圆盘可以在任一塔上做多次移动；圆盘可以在任一塔上做多次移动； 3.3.在任何时刻，大盘不能压在小盘的上面

23、。在任何时刻，大盘不能压在小盘的上面。XYZ问题存在递归的解决方法 Hanoi (n, x, y, z)表示解决n个盘子的汉诺塔问题（从x搬到z，可以借助y）。解决方法：解决方法：若若n=1，直接将盘子，直接将盘子从从x搬到搬到z即即可；可；否则，可以分解为如下步骤：否则，可以分解为如下步骤：Hanoi ( n-1, x, z, y )Hanoi ( n-1, x, z, y )move ( n, x, z )move ( n, x, z )Hanoi ( n-1, y, x, z )Hanoi ( n-1, y, x, z )Hanoi算法实现void void HanoiHanoi ( i

24、nt ( int n n, char , char x x, char , char y y, char , char z z) ) if ( n=1 ) if ( n=1 ) move ( n, x, z ); move ( n, x, z ); else else Hanoi Hanoi ( n-1, x, z, y ); ( n-1, x, z, y ); move ( n, x, z ); move ( n, x, z ); HanoiHanoi ( n-1, y, x, z ); ( n-1, y, x, z ); 123465789 演示Hanoi塔中递归工作栈变化过程0 3 a

25、b c返址 n x y z6 2 a c b6 1 a b c acabcb8 1 c a b ac6 1 b c aba bc8 1 a b cac 8 2 b a c 递归工作递归工作栈栈递归过程执行过程中占用的数据区递归的设计原则如果递归设计不当如果递归设计不当.容易造成容易造成无穷递归无穷递归，最，最终会耗尽应用程序的栈终会耗尽应用程序的栈空间，导致空间，导致栈溢出错误栈溢出错误，使程序失败。，使程序失败。？/ 无穷递归的例子/ 讲不完的故事void StoryStory () printf ( “从前有座山，山上有个庙，庙里有个和尚在讲故事：” ); Story();Story();

26、递归的设计原则（1 1）基准情形）基准情形必须存在不用继续递归即可解决的情况。（2 2）不断推进）不断推进对于需要递归解决的情况，每一次递归都要使得求解朝着基准情况的方向推进。（3 3）设计法则）设计法则假设所有的递归调用都能运行。（4 4）合成效益）合成效益解决一个问题时，切勿在不同的递归调用中做重复的工作。Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)用这个函数计算Fib(40)Fib(40)竟然用了83758375毫秒毫秒!一个不符合合成效益法则的例子long long FibFib( ( intint n ) n ) if

27、( n=1 ) return 0; if ( n=1 ) return 0; if ( n=2 ) return 1; if ( n=2 ) return 1; return return Fib(n-1)Fib(n-1)+ +Fib(n-2)Fib(n-2); ; 递归的优点和缺点优点优点缺点缺点递归函数递归函数结构清晰结构清晰，程序易读，正确性容易证明，程序易读，正确性容易证明反复的递归函数调用使得执行反复的递归函数调用使得执行效率较低效率较低消除递归为什么消除递归？为什么消除递归？1.1.某些语言不支持函数的递归调用某些语言不支持函数的递归调用2.2.在某些关键部分，递归算法影响了执行的效率在某些关键部分，递归算法影响了执行的效率如何消除递归？如何消除递归？1.1.转化为转化为循环递推循环递推2.2.自己管理一个自己