《数据结构教程》-第三章

第3章栈3.3栈的应用举例

3.3.1数制转换

3.3.2表达式求值

3.3.3子程序调用

3.3.4递归调用

3.3.5中断处理和现场保护

3.3.6求解迷宫问题返回上一页3.1栈的定义和运算3.1.1栈的定义1.找的定义栈(Stack)是限制在表尾进行插人和删除的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的，栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。如图3-1所示。2.找的特性(1)栈的主要特点是“后进先出”(lastinfirstout)，简称LIFO。下一页返回3.1栈的定义和运算(2)允许插入、删除的这一端称为栈顶(Top)，另一端称为栈底(Bottom)。3.应用实例(1)分币筒公交车上售票员用的分币筒就是一个最典型的栈。多个分币依次进入分币筒后，只能按后进先出的顺序退出分币筒。(2)铁路调度站在单轨的铁路上，南方的火车要驶向北方，北方的火车又要驶向南方，如何保证南来北往的火车安全行驶而不出事故呢?它们的调度工作正是利用了栈的后进先出的原理。下一页返回上一页3.1栈的定义和运算3.1.2栈的运算1.进栈:Push(&s，x)初始条件:栈s已存在且非满。操作结果:在栈顶插入一个元素x，栈中多了一个元素。2.出栈:Pop(&s)初始条件:栈s存在且非空。操作结果:删除栈顶元素，栈中少了一个元素。3.读栈顶元素:ReadTop(s，&e)初始条件:栈s已存在且非空。操作结果:输出栈顶元素，并存于变量e中，但栈中元素不变。下一页返回上一页3.1栈的定义和运算4.判找空:SEmpty(s)初始条件:栈s已存在。操作结果:若栈空则返回为1，否则返回为0。5.判找满:SFull(s)初始条件:栈已存在。操作结果:若栈满则返回为1，否则返回为0。6.显示找元素:ShowStack(s)初始条件:栈s已存在，且非空。操作结果:显示栈中所有元素。返回上一页3.2栈的存储和实现3.2.1顺序栈1.顺序找的实现(1)用一维数组实现顺序栈设栈中的数据元素的类型是字符型，用一个足够长度的一维数组5来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用G(或G++)语言描述如下:下一页返回3.2栈的存储和实现(2)用结构体数组实现顺序栈顺序栈的结构体描述:再定义一个指向顺序栈的指针:SeqStack*S;//定义S为结构体类型的指针变量下一页返回上一页3.2栈的存储和实现(3)栈操作的示意图(图3-2)当top=-1时，表示栈空，如图3-2(a)所示；当top=0时，表示栈中有一个元素，图3-2(b)表示栈中已输入一个元素a；入栈时，栈顶指针上移，指针top加1，图3-2(c)是4个元素入栈后的状况；出栈时，栈顶指针下移，指针top减1，图3-2(d)是在d出栈后的情况。此时栈中还有a,b,c3个元素，top=2,指针已经指向了新的栈顶。但是出栈的元素d仍然在原先的存储单元，只是不在栈中了，因为栈是只能在栈顶进行操作的线性表。当top=4时，即top=MAXLEN-1，表示栈满。下一页返回上一页3.2栈的存储和实现2.顺序找运算的基本算法(1)置空栈首先建立栈空间，然后初始化栈顶指针。下一页返回上一页3.2栈的存储和实现(2)进栈进栈运算是在栈顶位置插入一个新元素x，其算法步骤为:①判栈是否为满，若栈满，作溢出处理，并返回0;②若栈未满，栈顶指针top加1;③将新元素x送入栈顶，并返回1。下一页返回上一页3.2栈的存储和实现(3)出栈出栈运算是指取出栈顶元素，赋给某一个指定变量x，其算法步骤为:①判栈是否为空，若栈空，作下溢处理，并返回0;②若栈非空，将栈顶元素赋给变量x;③指针top减1，并返回1。下一页返回上一页3.2栈的存储和实现(4)读栈顶元素(5)判栈空下一页返回上一页3.2栈的存储和实现(6)判栈满3.2.2链栈1.链栈的实现用链式存储结构实现的栈称为链栈。因为链栈的结点结构与单链表的结构相同，通常就用单链表来实现，在此用LinkStack表示，即有:下一页返回上一页3.2栈的存储和实现由于栈中的操作只能在栈顶进行的，所以用链表的头做栈顶是最合适的。链栈结构如图3-3所示。下一页返回上一页3.2栈的存储和实现2.链找基本操作(1)入栈(2)出栈下一页返回上一页3.2栈的存储和实现下一页返回上一页3.2栈的存储和实现(3)显示返回上一页3.3栈的应用举例3.3.1数制转换数值进位制的换算是计算机实现计算和处理的基本问题。比如将十进制数N转换为j进制的数，其解决的方法很多，其中一个常用的算法是除j取余法。将十进制数每次除以j,所得的余数依次入栈，然后按“后进先出”的次序出栈便得到转换的结果。其算法原理是N=(N/j)*j+N%j式中，/为整除;%为求余。[例3-1]将十进制数138转换为二进制数。下一页返回3.3栈的应用举例下一页返回上一页3.3栈的应用举例所以(138)10=(10001010)2(1)算法思想①若N<>0，则将N%j取得的余数压入栈s中，执行(2)，若N=0，将栈s的内容依次出栈，算法结束;②用N/j代替N;③当N>0，则重复步骤(1)、(2)。(2)算法的实现下一页返回上一页3.3栈的应用举例下一页返回上一页3.3栈的应用举例下一页返回上一页3.3栈的应用举例3.3.2表达式求值表达式是由运算对象、运算符、括号等组成的有意义的式子。1.中缀表达式一般所用表达式是将运算符号放在两运算对象的中间，比如:a+h,c/d等，把这样的式子称为中缀表达式(InfixNotation)。2.后缀表达式后缀表达式(PostfixNotation)规定把运算符放在两个运算对象(操作数)的后面。在后缀表达式中，不存在运算符的优先级问题，也不存在任何括号，计算的顺序完全按照运算符出现的先后次序进行。下一页返回上一页3.3栈的应用举例3.中缀表达式转换为后缀表达式其转换方法采用运算符优先算法。转换过程需要一个运算符号栈和一个后缀表达式输出数组。(1)读入操作数，直接送输出符号数组。(2)读入运算符，压入运算符号栈。①若后进的运算符优先级高于先进的，则继续进栈;②若后进的运算符优先级不高于先进的，则将运算符号栈内高于或等于后进运算符级别的运算符依次弹出到输出符号数组后，自己进栈。(3)括号处理。①遇到开括号“(“,进运算符号栈;下一页返回上一页3.3栈的应用举例②遇到闭括号“)”，则把最靠近的开括号“(”，以及其后进栈的运算符依次弹出到输出符号数组(括号均不进入输出符号数组)。(4)遇到结束符“#’’，则把运算符号栈内的所有运算符号依次弹出，并压入输出符号数组。(5)若输人为+、-单目运算符，改为0与运算对象在前，运算符在后。例如:-A转换为:0A-。[例3-2]A/B^C+D*E-A*C运算过程如表3-1所示。得到后缀表达式为:ABC^/DE*+AC*-[例3-3]3+4/(25-(6+15))*运算过程如表3-2所示。下一页返回上一页3.3栈的应用举例得到后缀表达式为:3425615+-/8*+4.后缀表达式求值后缀表达式求值的运算要用到一个数栈stack和一个存放后缀表达式的字符型数组exp。其实现过程就是从头至尾扫描数组中的后缀表达式。(1)当遇到运算对象时，就把它插人到数栈stack中。(2)当遇到运算符时，就执行两次出栈的操作，对出栈的数进行该运算符指定的运算，并把计算的结果压入到数栈stack。(3)重复(1),(2)，直至扫描到表达式的终止符“#’’，在数栈的栈顶得到表达式的值。以例3-3的结果看后缀表达式的计算过程，如图3-4所示。下一页返回上一页3.3栈的应用举例3.3.3子程序调用在计算机程序设计中，子程序的调用(SubroutineGall)及返回地址就是利用栈来完成的。在G(或G++)语言的主函数对无参子函数的嵌套调用过程中，在调用子程序前，先将返回地址保存到堆栈中，然后才转去执行子程序。当子函数执行到return语句(或函数结束)时，便从栈中弹出返回地址，从该地址处继续执行程序。例如:主函数调用子函数a()时，则在调用之前先将a函数返回地址压入栈中;在子函数a()中调用子函数b()时，又将b函数返回地址压入栈中;同样，在子函数b()中调用子函数c()时，又将c函数返回地址压入栈中。其调用返回地址进栈示意图如图3-5所示。下一页返回上一页3.3栈的应用举例当执行完子函数c()以后，就从栈顶弹出c()函数返回地址，回到子函数b();子函数b()执行完毕返回时，又从栈顶弹出b函数返回地址，回到子函数a();子函数a()返回时，再在栈顶弹出a函数返回地址，回到主函数，继续执行主函数程序。无参函数嵌调用返回示意图如图3-6所示。3.3.4递归调用1.递归一个直接调用自己，或者通过一系列调用语句间接地调用自己的函数称为递归函数。在程序设计中，有许多实际问题是递归定义的，使用递归的方法编写程序将使许多复杂的问题大大简化。所以，递归是程序设计中的一个强有力的工具。下一页返回上一页3.3栈的应用举例2.典型例子(1)2阶斐波那契(Fibonacci)数列(2)阶乘函数n!的定义为:下一页返回上一页3.3栈的应用举例根据定义不难写出相应的递归函数:3.3.5中断处理和现场保护1.中断处理在c++语言中，系统调用是通过中断(InterruptProcessing)来进行，中断调用示意图如图3-7所示。下一页返回上一页3.3栈的应用举例如果把中断处理想象成函数调用，则中断处理程序可以看成被调用的函数。2.现场保护和恢复执行中断时，微处理机有时必须对状态寄存器、累加器以及相关的寄存器对进行现场保护(压栈);中断处理完毕，则必须按后进先出的原则恢复现场(出栈)。下面，以汇编语言来说明现场保护和恢复的原理:...;接受中断处理PUSHAX;保护现场PUSHBCPUSHCXPUSHBP下一页返回上一页3.3栈的应用举例PUSHF;F状态寄存器进栈...;中断处理POPF;恢复现场，后进栈的先出栈POPBPPOPCXPOPBXPOPAX(1)栈是一种运算受限制的线性表,它只允许在栈顶进行插入和删除等操作。(2)栈的逻辑结构和线性表相同，数据元素之间存在一对一的关系，其主要特点是“后进先出”。下一页返回上一页3.3栈的应用举例(3)栈的存储结构有顺序栈和链栈之分，要求掌握栈的G语言描述方法。(4)重点掌握在顺序栈和链栈上实现:进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。(5)熟悉栈在计算机的软件设计中的各种应用，能灵活应用栈的基本原理解决一些综合性的应用问题。3.3.6求解迷宫问题1.问题描述给定一个MxN的迷宫图，求一条从指定入口到出口的路径。假设迷宫图如图3-8所示，其中的方块图表示迷宫。对于图中的每个方块，用空自表示通道，用阴影表示墙。所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。下一页返回上一页3.3栈的应用举例2.数据组织为了表示迷宫，设置一个数组mg，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块为墙，对应的迷宫数组mg如下。迷宫方位图如图3-9所示。intmg[M+1][N+1]={/*M=10，N=10*/下一页返回上一页3.3栈的应用举例下一页返回上一页3.3栈的应用举例另外，在算法中用到的栈采用顺序栈存储结构，即将栈定义为:3.设计运算算法下一页返回上一页3.3栈的应用举例求迷宫问题就是求出从入口到出口的路径。在求解时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前试探，若能走通，则继续往前走;否则沿原路退回，换一个方向再继续试探，直至所有可能的通路都试探完为止。运算算法解释图如图3-10所示。为了保证在任何位置上都能沿原路退回(称为回溯)，需要用一个后进先出的栈来保存从入口到当前位置的路径。求解迷宫(1,1)到(M-2,N-2)路径的过程是:先将入口进栈(初始方位设置为