软件基础-3栈.ppt

《软件基础-3栈.ppt》由会员分享，可在线阅读，更多相关《软件基础-3栈.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第二二章章 线线性性结结构构一、栈的定义和运算一、栈的定义和运算二、顺序栈二、顺序栈三、链栈三、链栈四、栈的四、栈的应用应用五、小结五、小结第第 2 2 节节 栈栈1第第二二章章 线线性性表表2.2 2.2 栈栈 一、栈的概念和运算一、栈的概念和运算1.1.栈的定义栈的定义 栈是限定栈是限定只能在表的一端只能在表的一端进行插入和删除操作的线性表。进行插入和删除操作的线性表。允许插入和删除的一端称为允许插入和删除的一端称为栈顶栈顶(toptop)，另一端称为另一端称为栈底栈底(bottombottom)。设栈设栈s=(as=(a1 1,a,a2 2,.,a,.,an n)，a a1 1称为称为

2、栈底元素栈底元素,a an n称为称为栈顶元素栈顶元素。栈中元素按栈中元素按a a1 1,a,a2 2,.,a,.,an n次序进栈，又按次序进栈，又按a an n,.,a,.,a2 2,a,a1 1次序次序退栈。因此栈的操作特点是：退栈。因此栈的操作特点是：后进先出后进先出（LIFOLIFO）或或先进后出先进后出（FILOFILO）；）；n=0 n=0时称为时称为空栈空栈。2第第二二章章 线线性性表表2.2 2.2 栈栈 一、栈的概念和运算一、栈的概念和运算2.2.栈的存储栈的存储 栈的顺序存储顺序栈栈的顺序存储顺序栈ana1a2.栈底栈底栈顶栈顶.出栈出栈进栈进栈栈栈s=(a1,a2,an

3、)栈的链式存储链栈栈的链式存储链栈用用指指针针来来实实现现的的栈栈叫叫链链栈栈。栈栈的的容容量量事事先先不不能能估估计计时采用这种存储结构。时采用这种存储结构。3第第二二章章 线线性性表表2.2 2.2 栈栈 一、栈的概念和运算一、栈的概念和运算3.3.栈的基本运算栈的基本运算 栈的初始化栈的初始化 判栈空判栈空 EmptyEmpty 入栈入栈 PushPush 出栈出栈 PopPop 读栈顶元素读栈顶元素4top=0123450栈空栈空栈顶指针栈顶指针top,指向指向实际栈顶实际栈顶后的空后的空位置，初值为位置，初值为0top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设一维数组长

4、度为设一维数组长度为Mtop=0,栈空，此时出栈，则栈空，此时出栈，则下溢下溢（underflow)top=M,栈满，此时入栈，则栈满，此时入栈，则上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空2.2 2.2 栈栈 二、顺序栈二、顺序栈 (实现：一维数组实现：一维数组sM)52.2 2.2 栈栈 二、顺序栈二、顺序栈1.1.栈结构栈结构typedef structtypedef struct datatype dataMAX;datatype dataMAX;int top;int top;SeqStack;Seq

5、Stack;创建一个栈：创建一个栈：SeqStack *s;SeqStack *s;62.2 2.2 栈栈 二、顺序栈二、顺序栈2.2.栈的初始化栈的初始化SeqStack *StackList()SeqStack *StackList()/构造一个空栈构造一个空栈 SeqStack *s;SeqStack *s;s=(SeqStack*)malloc(sizeof(SeqStack);s=(SeqStack*)malloc(sizeof(SeqStack);s-top=0;s-top=0;/约定约定toptop始终指向新数据元素将存放的位置始终指向新数据元素将存放的位置 return s;r

6、eturn s;72.2 2.2 栈栈 二、顺序栈二、顺序栈3.3.判栈空判栈空int Empty(SeqStack *s)int Empty(SeqStack *s)if(s-top=0)return 1;if(s-top=0)return 1;/栈空栈空,返回返回 else return 0;else return 0;/栈非空栈非空,返回返回 82.2 2.2 栈栈 二、顺序栈二、顺序栈4.4.入栈入栈int Push(SeqStack *s,datatype x)int Push(SeqStack *s,datatype x)if(s-top=Max)return 0;if(s-top

7、=Max)return 0;/栈满栈满,返回返回 else else s-datas-top=x;s-datas-top=x;/x/x值入栈值入栈 s-top+;s-top+;/指示器加指示器加1 1 return 1;return 1;/成功，返回成功，返回 92.2 2.2 栈栈 二、顺序栈二、顺序栈.出栈且读栈顶元素出栈且读栈顶元素int Pop(SeqStack *s,datatype*x)int Pop(SeqStack *s,datatype*x)if(Empty(s)return 0;if(Empty(s)return 0;/栈空栈空,返回返回 else else s-top-;

8、s-top-;/指示器减指示器减1 1 *x=s-datas-top;*x=s-datas-top;/出栈出栈 return 1;return 1;/成功，返回成功，返回 102.2 2.2 栈栈 三、链栈三、链栈toptop问题？问题？若若top指向最后一个元素，则入栈和出栈操作时指向最后一个元素，则入栈和出栈操作时top的值都要变化，在的值都要变化，在C中参数传值方式难实现！中参数传值方式难实现！解决办法：解决办法：用增加头结点方式用增加头结点方式栈顶栈顶a1 .topan栈底栈底top头结点头结点next112.2 2.2 栈栈 三、链栈三、链栈.结点定义结点定义typedef stru

9、ct Node datatype data;struct Node *next;StackNode;栈顶栈顶a1 .topan栈底栈底top头结点头结点栈空栈空:若有头结点时若有头结点时top-next=Null为空栈；为空栈；若无头结点时若无头结点时top=Null为空栈为空栈 建立一个链栈：建立一个链栈：StackNode*top;如何判栈空？如何判栈空？头结点头结点next122.2 2.2 栈栈 三、链栈三、链栈2.2.链栈初始化链栈初始化StackNode*Creat()StackNode *top;/创建头结点创建头结点 top=(StackNode*)malloc(sizeof(

10、StackNode);top-next=Null;/设置头结点设置头结点 return top;/返回头指针返回头指针Nulltop132.2 2.2 栈栈 三、链栈三、链栈3.3.入栈头插法入栈头插法void Push(StackNode*s,datatype x)StackNode *p;/创建一个新结点创建一个新结点p p p=(StackNode*)malloc(sizeof(StackNode);p-data=x;/设置设置p p结点结点 p-next=s-next;/p/p结点加入链栈中结点加入链栈中 s-next=p;/头结点头结点nextnext指向新的栈顶结点指向新的栈顶结点

11、p ppxStackNode *p;p=(StackNode*)malloc(sizeof(StackNode);p-data=x;p-next=s-next;s-next=p;sa1Nulla2ai头结点头结点142.2 2.2 栈栈 三、链栈三、链栈.出栈出栈int Pop(StackNode*s,datatype *x)StackNode *p;/创建一个新结点创建一个新结点p p if(s-next=Null)return 0;/栈空，返回失败栈空，返回失败 *x=s-next-data;/传回栈顶结点的数据传回栈顶结点的数据 p=s-next;/p/p结点指向栈顶结点结点指向栈顶结点

12、 s-next=p-next;/头结点头结点nextnext域指向域指向p p下一个结点下一个结点 free(p);/释放释放p p结点删除栈顶结点结点删除栈顶结点 return 1;/返回成功返回成功152.2 2.2 栈栈 四、栈的应用四、栈的应用 数制转换数制转换 函数的递归调用函数的递归调用 表达式求值表达式求值 迷宫求解迷宫求解16 数制转换数制转换例例 把十进制数把十进制数159转换成八进制数转换成八进制数(159)10=(237)815981982802 3 7 余余 7余余 3余余 2toptop7top73top7322.2 2.2 栈栈 算法见书第55页，自学172.22.

13、2栈栈 表达式求值表达式求值 1.高级语言中的表达式是用人们熟悉的公式形式书写的，高级语言中的表达式是用人们熟悉的公式形式书写的，如：如：a+b*c-d 中缀表达式中缀表达式为解决运算顺序问题把运算符分成若干等级级别高的先运算。为解决运算顺序问题把运算符分成若干等级级别高的先运算。.后缀表达式后缀表达式（也称逆波兰表达式（也称逆波兰表达式RPN)如：如：abc*+d-运算符在运算对象的后面，无需判断运算符优先级，遇到运算运算符在运算对象的后面，无需判断运算符优先级，遇到运算符就计算运算对象，简单方便。符就计算运算对象，简单方便。182.2.栈栈.中缀表达式求值中缀表达式求值 为解决运算顺序问题

14、把运算符分成若干等级，称为优先数。为解决运算顺序问题把运算符分成若干等级，称为优先数。运算符：运算符：*/*+-（）界限符：界限符：；优先级：优先级：4 3 3 2 2 1 1 0输入：表达式符号序列输入：表达式符号序列输出：表达式值输出：表达式值 y为进行表达式的翻译，为进行表达式的翻译，需设立两个栈需设立两个栈，分别存放，分别存放操作数操作数(NS)NS)和运算符和运算符(OS)OS)，初始化栈初始化栈 NS、OS：在在OSOS中放入表达式结束符中放入表达式结束符“；”。191.1.中缀表达式求值中缀表达式求值 A*B+C/D;自左至右扫描表达式，对扫描的每个符号自左至右扫描表达式，对扫描

15、的每个符号w w作如下处理：作如下处理：1)1)若若w w为操作数，将其压入为操作数，将其压入NSNS栈，继续扫描栈，继续扫描2)2)若若w w为运算符，需看当前为运算符，需看当前OSOS的栈顶元素优先数：的栈顶元素优先数：若若w w大于大于OSOS栈顶运算符，则将栈顶运算符，则将w w压入压入OSOS栈栈,继续扫描继续扫描。若若w w为为“；”，且，且OSOS栈顶也为栈顶也为“；”，则表示表达式处理结，则表示表达式处理结束，此时束，此时NSNS栈顶的元素栈顶的元素即为此表达式的即为此表达式的结果结果值。值。若若w w为为“)”,”,且且OSOS栈顶也为栈顶也为“(”,”,从从OSOS栈中弹出

16、栈中弹出“(”,”,继续继续扫描扫描.若若w w小于或等于小于或等于OSOS栈顶运算符，则从栈顶运算符，则从NSNS栈中弹出两个操作数，栈中弹出两个操作数，设为设为x x、y y，再从再从OSOS栈中弹出一个运算符，设为栈中弹出一个运算符，设为，构成一条指，构成一条指令：令：y y x Tx T，将结果将结果T T送入送入NSNS栈。栈。继续与继续与OSOS栈顶元素比较栈顶元素比较,2.2.栈栈20例例例例 A*B+C/D;A*B+C/D;top2top2top1top1初态初态初态初态;(a)a)OSOSNSNSB BA A*;(b)b)NSNSOSOST1T1;(c)c)T1=A*BT1=

17、A*BNSNSOSOSD DC CT1T1/+;(d)d)NSNSOSOS(g)g)NSNSOSOST2=C/DT2=C/DT2T2T1T1+;(e)e)NSNSOSOST3T3;(f)f)T3=T2+T1T3=T2+T1NSNSOSOS212.2.后缀表达式求值后缀表达式求值后缀表达式求值后缀表达式求值只需一个操作数栈，步骤：只需一个操作数栈，步骤：只需一个操作数栈，步骤：只需一个操作数栈，步骤：1)1)读入表达式一个字符读入表达式一个字符读入表达式一个字符读入表达式一个字符2)2)若是操作数，压入栈，转若是操作数，压入栈，转若是操作数，压入栈，转若是操作数，压入栈，转4 43)3)若是运算

18、符，从栈中弹出若是运算符，从栈中弹出若是运算符，从栈中弹出若是运算符，从栈中弹出2 2个数，将运算结果再压入栈个数，将运算结果再压入栈个数，将运算结果再压入栈个数，将运算结果再压入栈4)4)若表达式输入完毕，栈顶即表达式值；若表达式输入完毕，栈顶即表达式值；若表达式输入完毕，栈顶即表达式值；若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转若表达式未输入完，转若表达式未输入完，转若表达式未输入完，转1 1toptop4 4toptop4 43 3toptop4 43 35 5toptop例例例例 计算计算计算计算 4+3*5 4+3*5转换为后缀表达式：转换为后缀表达式：转换为后缀表达式：

19、转换为后缀表达式：435*+435*+toptop4 41515toptop1919后缀表达式计算简单方便，如何完成后缀表达式计算简单方便，如何完成后缀表达式计算简单方便，如何完成后缀表达式计算简单方便，如何完成由中缀到后缀的转换呢？由中缀到后缀的转换呢？由中缀到后缀的转换呢？由中缀到后缀的转换呢？22中缀表达式到后缀表达式的转换：中缀表达式到后缀表达式的转换：中缀表达式到后缀表达式的转换：中缀表达式到后缀表达式的转换：需用一个运算符栈需用一个运算符栈需用一个运算符栈需用一个运算符栈 请把请把请把请把 a+(b*c+d)/e 转换为后缀表达式转换为后缀表达式转换为后缀表达式转换为后缀表达式 输

20、入：中缀表达式输出：后缀表达式输入：中缀表达式输出：后缀表达式输入：中缀表达式输出：后缀表达式输入：中缀表达式输出：后缀表达式从左至右扫描中缀表达式，每个符号做如下判断：从左至右扫描中缀表达式，每个符号做如下判断：从左至右扫描中缀表达式，每个符号做如下判断：从左至右扫描中缀表达式，每个符号做如下判断：1 1）若是变量则作为新表达式的变量；）若是变量则作为新表达式的变量；）若是变量则作为新表达式的变量；）若是变量则作为新表达式的变量；2 2）若是）若是）若是）若是“(”就入栈；就入栈；就入栈；就入栈；3 3）若是运算符则检查栈，如果栈空，则运算符进栈，）若是运算符则检查栈，如果栈空，则运算符进栈

21、，）若是运算符则检查栈，如果栈空，则运算符进栈，）若是运算符则检查栈，如果栈空，则运算符进栈，否则，与栈顶运算符比较：否则，与栈顶运算符比较：否则，与栈顶运算符比较：否则，与栈顶运算符比较：(1)(1)若若若若小小小小于于于于或或或或等等等等于于于于栈栈栈栈顶顶顶顶运运运运算算算算符符符符级级级级别别别别，则则则则栈栈栈栈顶顶顶顶元元元元素素素素出出出出栈栈栈栈，写写写写入新表达式，继续比较下一个栈顶运算符入新表达式，继续比较下一个栈顶运算符入新表达式，继续比较下一个栈顶运算符入新表达式，继续比较下一个栈顶运算符;(2)(2)反之反之反之反之，将新运算符入栈；，将新运算符入栈；，将新运算符入栈

22、；，将新运算符入栈；4 4）若若若若是是是是“)”,”,则则则则将将将将栈栈栈栈顶顶顶顶运运运运算算算算符符符符一一一一一一一一出出出出栈栈栈栈，写写写写入入入入新新新新表表表表达达达达式式式式中中中中，直到读出相应的直到读出相应的直到读出相应的直到读出相应的“(”为止，然后删去为止，然后删去为止，然后删去为止，然后删去“(”。abc*d+e/+23例例例例中缀表达式中缀表达式中缀表达式中缀表达式A*B+C/D;A*B+C/D;求等价的求等价的求等价的求等价的后缀表达式后缀表达式后缀表达式后缀表达式?toptop后缀：后缀：后缀：后缀：A A(1(1)NSNStoptop后缀：后缀：后缀：后缀

23、：A A(2(2)NSNS*toptop后缀：后缀：后缀：后缀：ABAB(3(3)NSNS*toptop后缀：后缀：后缀：后缀：AB*AB*(4(4)NSNS+toptop后缀：后缀：后缀：后缀：AB*CAB*C(5(5)NSNS+NSNStoptop后缀：后缀：后缀：后缀：AB*CAB*C(6(6)+/toptop后缀：后缀：后缀：后缀：AB*CDAB*CD(7(7)NSNS+/(8(8)toptop后缀：后缀：后缀：后缀：AB*CD/+AB*CD/+NSNS+/242.2.栈栈 过程嵌套和递归调用过程嵌套和递归调用过程嵌套和递归调用是程序设计中很重要的应用。当过程过程嵌套和递归调用是程序设

24、计中很重要的应用。当过程调用子程序时，必须把断点的信息及地址保存起来，当子调用子程序时，必须把断点的信息及地址保存起来，当子过程执行完毕返回时，取用这些信息，找到返回地址，从过程执行完毕返回时，取用这些信息，找到返回地址，从断点处继续执行。当程序中出现多重嵌套调用时，必须开断点处继续执行。当程序中出现多重嵌套调用时，必须开辟一个栈，将各层断点信息依次入栈，当各层子过程返回辟一个栈，将各层断点信息依次入栈，当各层子过程返回时，又以相反的次序从栈顶取出，这样才能保证程序的正时，又以相反的次序从栈顶取出，这样才能保证程序的正常执行。常执行。25函数的递归调用函数的递归调用1.定义：定义：在调用一个函

25、数的过程中直接或间接地调用该函数本身。直接调用直接调用int f(int x)int y,z;.z=f(x);return(2*z);f 函数调用 f函数26int f1(x)int x;int y,z;.z=f2(y);return(2*z);int f2(t)int t;int a,c;.c=f1(a);return(3+c);间接调用间接调用27特点特点 是无终止的递归调用，因此，应该给定一个限制递应该给定一个限制递归次数的条件。归次数的条件。f 1函数调用 f2函数f 2函数调用 f1函数28 long fac(int n)long s;if(n=1)s=1;else s=n*fac(

26、n-1);return(s);例如：写一函数求例如：写一函数求n!1 (n=0,1)n!=n(n-1)！(n1)29以求4的阶乘为例：fac(4)=4*fac(3)fac(3)=3*fac(2)fac(2)=2*fac(1)fac(1)=1fac(4)=4*3*2*1fac(2)=2*1fac(3)=3*2*1下下推推回回代代30利用栈实现递归调用利用栈实现递归调用主程序主程序(1)输出输出fac(4);4 fac(4);（1）n=4top(2)s=4*f(3)n3 fac(3);（2）n=3 （1）n=4 top(3)s=3*f(2)n2 fac(2);（3）n=2 （2）n=3 （1）n=

27、4 top(4)s=2*f(1)n1（4）n=1 （3）n=2 （2）n=3 （1）n=4 tops结束结束输出输出24long fac(int n)long s;if(n=1)s=1;else s=n*fac(n-1);return(s);main()printf(“%d”fac(4);返回返回(3)2(2)3(1)4top(4)1 s=2*1(3)2(2)3(1)4top s=3*2*1;(2)3(1)4top s=4*3*2*1 (1)4top31回文游戏：顺读与逆读字符串一样（不含空格）回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串读入字符串2.去掉空格（原串）去

28、掉空格（原串）3.压入栈压入栈4.原串字符与出栈字符依次比较原串字符与出栈字符依次比较 若不等，非回文若不等，非回文 若直到栈空都相等，回文若直到栈空都相等，回文字符串：字符串：“madam im adam”32第第二二章章 线线性性表表2.2.栈栈 五、小结五、小结1 1、理解栈的概念和特点、理解栈的概念和特点2 2、掌握进、掌握进/出栈的算法（顺序栈和链栈）出栈的算法（顺序栈和链栈）3 3、了解栈的应用、了解栈的应用4 4、掌握表达式求值、掌握表达式求值 33第第二二章章 线线性性表表2.2.栈栈六、作业与实验六、作业与实验 教材第教材第7070页习题中的一页习题中的一1414 实验：二、实验：二、本节结束，返回目录34