《数据结构与算法》PPT课堂课件-第3章-栈.pdf

《《数据结构与算法》PPT课堂课件-第3章-栈.pdf》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-第3章-栈.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、12021/6/13第三章 栈栈是一种特殊的线性表，是操作受限的线性表，称其为限定性数据结构。3.1 ADT栈（stack）栈的定义和特点n定义：限定仅在表首进行插入或删除操作的线性表，表表首首栈栈顶顶，表表尾尾栈栈底底，不含元素的空表称空栈n特点：先进后出（FILO）或后进先出（LIFO）22021/6/13ana1a2.栈底栈顶.出栈进栈栈S=(a1,a2,an)p栈的操作示例32021/6/133.1 ADT栈(Stack)ADT栈上定义的常用的基本运算(1)Empty():判断栈空(2)Full():判断栈满(3)Top():返回栈顶元素(4)Push(x):将元素x入栈(5)Pop(

2、x):出栈，并将栈顶元素存入x中42021/6/133.1.1栈栈应应用用的的简简单单例例子子 例例1、程程序序编编译译时时的的表表达达式式或或字字符符串串的的括括号号匹匹配配问问题题。例如，算术表达式(x*(x+y)-z)，其中位置1和4处有左括号，而位置8和11处有右括号，满足配对要求。但算术表达式 (x+y)*z)(，其中位置8处的右括号没有可与之配对的左括号，而位置9处的左括号没有可与之配对的右括号。这里要在栈的基本运算的基础上定义算术表达式（字符串）expr中的圆括号配对检查运算void Parenthesis(char*expr)52021/6/13例2、回文游戏：顺读与逆读字符串

3、一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文例3、多进制输出：字符串：“madam im adam”例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top73262021/6/133.2 栈的存储结构3.2.1 用数组实现栈顺序栈3.2.1.1实现：一维数组sMtop=-1123450栈空栈顶指针top,指向实际栈顶后后的空位置，初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-

4、1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空72021/6/133.2.1.2栈的数组实现的优缺点v优点：所列的7个基本运算都可在O(1)的时间里完成，效率高。v缺点：为了使每个栈在算法运行过程中不会溢出，通常要为每个栈预置一个较大的栈空间。另一方面，由于各个栈的实际大小在算法运行过程中不断变化。经常会发生其中一个栈满，而另一个栈空的情形，空间利用率低。82021/6/133.2.2两个栈共用一个数组的实现v2个栈共享一个数组stack0.

5、n 利用栈底位置不变的特性，可以将2个栈的栈底分别设在数组stack的两端。然后各自向数组stack的中间伸展，如图所示。好处：提高空间利用率，减少栈发生上溢的可能性。92021/6/133.2.3 用指针实现栈链栈typedef struct snode*slink;typedef struct snode StackItem element;slink next;StackNode;l链栈结点及用指针实现的栈结点定义102021/6/13入栈算法出栈算法 .栈底toptopxptop .栈底topp3.2.3.1 入栈、出栈算法实现及演示：112021/6/133.2.3.2栈的应用例1、

6、过程的嵌套调用r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程程3122021/6/13例 递归的执行情况分析（假设初始w=3）例2、递归过程及其实现定义：函数直接或间接的调用自自身身叫递归实现：建立递归工作栈void print(int w)int i;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”);运行结果：1，2，2，3，3，3，132021/6/13递递归归调调用用执执行行情情况况如如下下：主主程程序序(1)print(w)w=3;3print(2);（1）w=3 top(2)输输

7、出出：3,3,3w2print(1);（2）w=2 （1）w=3 top(3)输输出出：2,2w1print(0);（3）w=1 （2）w=2 （1）w=3 top(4)输输出出：1w0（4）w=0 （3）w=1 （2）w=2 （1）w=3 topw(3)输输出出：2,2(2)2(1)3top(4)输输出出：1(3)1(2)2(1)3top(2)输输出出：3,3,3 (1)3top返返回回(3)1(2)2(1)3top(4)0结结束束(1)142021/6/13A*B+C/D;top2top1初态;(a)OSNSBA*;(b)NSOST1;(c)T1=A*BNSOSDCT1/+;(d)NSOS

8、(g)NSOST2=C/DT2T1+;(e)NSOST3;(f)T3=T2+T1NSOS思思想想：从从左左到到右右扫扫描描表表达达式式，若若当当前前读读入入的的是是操操作作数数，则则进进操操作作数数（NS）栈栈，若若读读入入的的符符号号是是运运算算符符，应应进进行行判判断断：1.若若是是“（”，进进运运算算符符栈栈；若若是是“）”，当当运运算算符符栈栈顶顶是是“（”，则则弹弹出出栈栈顶顶元元素素，继继续续扫扫描描下下一一符符号号。否否则则当当前前读读入入符符号号暂暂不不处处理理，从从操操作作数数栈栈弹弹出出两两个个操操作作数数，从从运运算算符符栈栈弹弹出出一一个个运运算算符符，生生成成运运算算

9、指指令令，结结果果送送入入操操作作数数栈栈，继继续续处处理理当当前前读读入入符符号号。2.若若读读入入的的运运算算符符的的优优先先级级大大于于运运算算符符栈栈顶顶的的优优先先级级，则则进进运运算算符符栈栈，继继续续扫扫描描下下一一符符号号；否否则则从从操操作作数数栈栈顶顶弹弹出出两两个个操操作作数数，从从运运算算符符栈栈弹弹出出一一个个运运算算符符，生生成成运运算算指指令令，把把结结果果送送入入操操作作数数栈栈。继继续续处处理理刚刚才才读读入入的的符符号号。3.若若读读入入的的是是“；”，且且运运算算符符栈栈顶顶的的符符号号也也是是“；”时时，则则表表达达式式处处理理结结束束。从从操操作作数数

10、栈栈弹弹出出表表达达式式结结果果。152021/6/13例3、表达式求值 中缀表达式 后缀表达式（RPN)a*b+c ab*c+a+b*c abc*+a+(b*c+d)/e abc*d+e/+中缀表达式：操作数栈和运算符栈p计算 2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符12162021/6/13后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1top4top43top735topp计算 4+3*5后缀表

11、达式：435*+top415top19172021/6/13(1)(2)(4)(5)(6)(7)(3)例4、地图四染色问题R 7 7 1 2 3 4 5 6 71 2 3 4 5 6 7 1 0 0 0 0 1 00 1 1 1 1 1 01 0 1 0 1 1 01 0 1 1 0 1 01 1 0 1 1 0 01 0 0 1 1 0 00 0 0 0 0 0 01 2 3 4 5 6 7 122 3414334231#紫紫色色 2#黄黄色色3#红红色色4#绿绿色色182021/6/13例：已知字符串的内容为b%-y-3*y2，利用栈的进栈和退栈操作将其转换成by-%3y2 *-试给出进栈和退栈的操作序列。设进栈用表示，出栈用表示操作序列：192021/6/13作业：1、书P61 3.2（1）用数组实现 3.2 （2）用指针实现2、利用栈将链表逆置