武汉软件工程职业学院《数据结构讲义》第09讲-栈的应用

第九讲栈的应用1．巩固栈的定义及表示。2．掌握栈的应用方法,理解栈的重要作用。教学重点：利用栈实现表达式求值教学难点：利用栈实现表达式求值授课内容3．1.4栈的应用举例由于栈的“先进先出”特点，在很多实际问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。【例3.1】简单应用：数制转换问题将十进制数N转换为r进制的数，其转换方法利用辗转相 除法 二年级余数除法练习二年级余数除法竖式二年级余数除法题算式二年级余数除法竖式题除数是一位数的除法练竖式计算 ：以N=3456，r=8为例转换方法如下：NN/8（整除）N%8（求余）34674333低4335415466606高所以：（3456）10=（6563）8我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。算法思想如下：当N>0时重复1，2若N≠0，则将N%r压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。用N/r代替N算法如下：typedefintdatatype;#defineL10voidconversion(intN，intr)voidconversion(intN，intr){SeqStacks;{ints[L],top;/*定义一个顺序栈*/datetypex;intx;Init_SeqStack(&s);top=-1;/*初始化栈*/while(N)while(N){Push_SeqStack(&s，N%r);{s[++top]=N%r;/*余数入栈*/N=N/r;N=N/r;/*商作为被除数继续*/}}while(Empty_SeqStack(&s))while(top!=-1){Pop_SeqStack(&s，&x);{x=s[top--];printf(“%d”，x);printf(“%d”,x);}}}}算法3.1(a)算法3.1(b)算法3.1(a)是将对栈的操作抽象为模块调用，使问题的层次更加清楚。而算法3.1(b)中的直接用int向量S和int变量top作为一个栈来使用，往往初学者将栈视为一个很复杂的东西，不知道如何使用，通过这个例子可以消除栈的“神秘”，当应用程序中需要一个与数据保存时相反顺序使用数据时，就要想到栈。通常用顺序栈较多，因为很便利。在后面的例子中，为了在算法中表现出问题的层次，有关栈的操作调用了的相关 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数，如象算法3.1(a)那样，对余数的入栈操作：Push_SeqStack(&s，N%r);因为是用c语言描述，第一个参数是栈的地址才能对栈进行加工。在后面的例子中，为了算法的清楚易读，在不至于混淆的情况下，不再加地址运算符，请读者注意。【例3.2】利用栈实现迷宫的求解。问题：这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解思想：回溯法是一种不断试探且及时纠正错误的搜索方法。下面的求解过程采用回溯法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向;若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向。需要解决的四个问题：表示迷宫的数据结构：设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1;其中：0表示通路，1表示不通，当从某点向下试探时，中间点有8个方向可以试探，（见图3.4）而四个角点有3个方向，其它边缘点有5个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为8，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。如图3.4表示的迷宫是一个6×8的迷宫。入口坐标为（1，1），出口坐标为（m，n）。入口(1,1)01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111出口(6,8)图3.4用maze[m+2][n+2]表示的迷宫迷宫的定义如下：#definem6/*迷宫的实际行*/#definen8/*迷宫的实际列*/intmaze[m+2][n+2];2．试探方向：在上述表示迷宫的情况下，每个点有8个方向去试探，如当前点的坐标(x,y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，如图3.5所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这8个方向的坐标增量放在一个结构数组move[8]中，在move数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。move数组如图3.6所示。Move数组定义如下：typedefstruct{intx，y}item;itemmove[8];这样对move的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 会很方便地求出从某点(x，y)按某一方向v(0<=v<=7)到达的新点（i，j）的坐标：i=x+move[v].x;j=y+move[v].y;xy00111121031-140-15-1-16-107-11图3.6增量数组move(x，y)图3.5与点(x，y)相邻的8个点及坐标(x，y+1)(x，y-1)(x+1，y)(x-1，y)(x-1，y+1)(x-1，y-1)(x+1，y-1)(x+1，y+1)栈的设计：当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。对于图3.4所示迷宫，依次入栈为：top—>5,8,2　　5,7,05,6,04,5,1top—>3,6,03,6,33,5,03,5,03,4,03,4,03,3,03,3,02,2,12,2,11,1,11,1,1栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3.4迷宫，走的路线为：(1,1)1(2,2)1(3,3)0(3,4)0(3,5)0(3,6)0（下脚标表示方向），当从点(3,6)沿方向0到达点(3,7)之后，无路可走，则应回溯，即退回到点(3,6)，对应的操作是出栈，沿下一个方向即方向1继续试探，方向１、２试探失败，在方向３上试探成功，因此将(3,6,3)压入栈中，即到达了（4,5）点。栈中元素是一个由行、列、方向组成的三元组，栈元素的设计如下：typedefstruct{intx,y,d;/*横纵坐标及方向*/}datatype;栈的定义仍然为：SeqStacks;如何防止重复到达某点，以避免发生死循环：一种方法是另外设置一个标志数组mark[m][n]，它的所有元素都初始化为0，一旦到达了某一点(i,j)之后，使mark[i][j]置1，下次再试探这个位置时就不能再走了。另一种方法是当到达某点（i,j）后使maze[i][j]置-1，以便区别未到达过的点，同样也能起到防止走重复点的目的，本书采用后者方法，算法结束前可恢复原迷宫。迷宫求解算法思想如下：栈初始化;将入口点坐标及到达该点的方向（设为－１）入栈while(栈不空){栈顶元素＝＞（x,y,d）出栈;求出下一个要试探的方向d++;while（还有剩余试探方向时）{if（d方向可走）则{（x,y,d）入栈;求新点坐标(i,j);将新点（i,j）切换为当前点（x,y）;if((x,ｙ)==(ｍ,n))结束;else重置d=0;}elsed++;}}算法如下：intpath(maze，move)intmaze[m][n];itemmove[8];{SeqStacks;datetypetemp;intx,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1;Push_SeqStack(s，temp);while(!Empty_SeqStack(s)){Pop_SeqStack(s,＆temp);x=temp.x;y=temp.y;d=temp.d+1;while(d<8){i=x+move[d].x;j=y+move[d].y;if(maze[i][j]==0){temp={x,y,d};Push_SeqStack(s,temp);x=i;y=j;maze[x][y]=-1;if(x==m&&y==n)return1;/*迷宫有路*/elsed=0;}elsed++;}/*while(d<8)*/}/*while*/return0;/*迷宫无路*/}算法3.2栈中保存的就是一条迷宫的通路。【例3.3】表达式求值表达式求值是程序设计语言编译中一个最基本的问题。它的实现也是需要栈的加入。下面的算法是由算符优先法对表达式求值。表达式是由运算对象、运算符、括号组成的有意义的式子。运算符从运算对象的个数上分，有单目运算符和双目运算符；从运算类型上分，有算术运算、关系运算、逻辑运算。在此仅限于讨论只含二目运算符的算术表达式。中缀表达式求值：中缀表达式：每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括：+、-、*、/、%、^（乘方）和括号（）。设运算规则为：．运算符的优先级为：（）——>^——>＊、/、%——>+、-　；．有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；．乘方连续出现时先算最右面的；表达式作为一个满足表达式语法规则的串存储，如表达式“3*2^（4+2*2-１*3）-5”,它的的求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因为后面可能还有更高的运算，正确的处理过程是：需要两个栈：对象栈s1和算符栈s2。当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符。根据运算规则，左括号“（”在栈外时它的级别最高，而进栈后它的级别则最低了;乘方运算的结合性是自右向左，所以，它的栈外级别高于栈内;就是说有的运算符栈内栈外的级别是不同的。当遇到右括号“）”时，一直需要对运算符栈出栈，并且做相应的运算，直到遇到栈顶为左括号“(”时，将其出栈，因此右括号“）”级别最低但它是不入栈的。对象栈初始化为空，为了使表达式中的第一个运算符入栈，算符栈中预设一个最低级的运算符“（”。根据以上分析，每个运算符栈内、栈外的级别如下：算符栈内级别栈外级别^34*、/、%22+、-11(04）-1-1中缀表达式表达式“3*2^（4+2*2-１*3）-5”求值过程中两个栈的状态情况见图3.7所示。读字符对象栈s1算符栈s2说明33(3入栈s1*3(**入栈s223，2(*2入栈s1^3，2(*^^入栈s2(3，2(*^((入栈s243，2，4(*^(4入栈s1+3，2，4(*^(++入栈s223，2，4，2(*^(+2入栈s1*3，2，4，2(*^(+**入栈s223，2，4，2，2(*^(+*2入栈s1-3，2，4，4(*^(+做2+2=4，结果入栈s13，2，8(*^(做4+4=8，结果入栈s23，2，8(*^(--入栈s2１3，2，8，1(*^(-1入栈s1*3，2，8，1(*^(-**入栈s233，2，8，1，3(*^(-*3入栈s1)3，2，8，3(*^(-做1*3，结果3入栈s13，2，5(*^(做8-3，结果5入栈s23，2，5(*^(出栈-3，32(*做2^5，结果32入栈s196(做3*32，结果96入栈s196(--入栈s2596，5(-5入栈s1结束符91(做96-5,结果91入栈s1图3.7中缀表达式3*2^（4+2*2-１*3）-5的求值过程为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不在引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。中缀表达式“3*2^（4+2*2-1*3）-5”的后缀表达式为：“32422*+13*-^*5-”。后缀表达式求值计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以‘#’为结束字符，为了简化问题，限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据之间的转换的问题。typedefchardatetype;doublecalcul_exp(char*A){/*本函数返回由后缀表达式A表示的表达式运算结果*/Seq_Starcks;ch=*A++;Init_SeqStack(s);while(ch!=’#’){if(ch!=运算符)Push_SeqStack(s,ch);else{Pop_SeqStack(s,&a);Pop_SeqStack(s,&b);/*取出两个运算量*/switch(ch).{casech==’+’：c=a+b;break;casech==’-’：c=a-b;break;casech==’*’：c=a*b;break;casech==’/’：c=a/b;break;casech==’%’：c=a%b;break;}Push_SeqStack(s,c);}ch=*A++;}Pop_SeqStack(s,result);returnresult;}算法3.3栈中状态变化情况：当前字符栈中数据说明３3３入栈２3，２２入栈４3，2，4４入栈２3，2，4，2２入栈２3，2，4，2，2２入栈＊3，2，4，4计算２＊２，将结果４入栈＋3，2，8计算４＋４，将结果８入栈１3，2，8，1１入栈３3，2，8，1，3３入栈＊3，2，8，3计算１＊３，将结果４入栈－3，2，5计算８－５，将结果５入栈^3，32计算2^5，将结果32入栈*96计算３＊32，将结果96入栈596，55入栈-96计算96-5，结果入栈结束符空结果出栈图3.8后缀表达式求值过程中缀表达式转换成后缀表达式：将中缀表达式转化为后缀表达示和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B中存放。读者不难写出算法，在此不在赘述。【例3.4】栈与递归：栈的一个重要应用是在程序设计语言中实现递归过程。现实中，有许多实际问题是递归定义的，这时用递归方法可以使许多问题的结果大大简化，以n!为例：n!的定义为：n!=1　　n=0/*递归终止条件*/n*(n-1)n>0/*递归步骤*/根据定义可以很自然的写出相应的递归函数intfact(intn){if(n==0)return1;elsereturn(n*fact(n-1));}递归函数都有一个终止递归的条件，如上例n=0时，将不再继续递归下去。递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数而已。在每次调用时系统将属于各个递归层次的信息组成一个活动记录（ActivaTionRecord），这个记录中包含着本层调用的实参、返回地址、局部变量等信息，并将这个活动记录保存在系统的“递归工作栈”中，每当递归调用一次，就要在栈顶为过程建立一个新的活动记录，一旦本次调用结束，则将栈顶活动记录出栈，根据获得的返回地址信息返回到本次的调用处。下面以求3!为例说明执行调用时工作栈中的状况。为了方便将求阶乘程序修改如下：main(){intm，n=３;m=fact(n);R1：printf(“%d!=%d\n”，n，m);参数返回地址fact(0)0R2fact(1)1R2fact(2)2R2fact(3)3R１}intfact(intn){intf;if(n==0)f=1;elsef=n*fact(n-1);图3.9递归工作栈示意图R2:returnf;}算法3.4其中R1为主函数调用fact时返回点地址，R2为fact函数中递归调用fact(n-1)时返回点地址。程序的执行过程可用图3.10来示意。设主函数中n=3　：n=3n=2n=1n=0m=fact(n)f=3*fact(2)f=2*fact(1)f=1*fact(0)f=1returnf；returnfreturnfreturnff=3*2*1*1f=2*1*1f=1*1f=1图3.10fact(3)的执行过程