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

《武汉软件工程职业学院《数据结构讲义》第09讲 栈的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈和队列第九讲栈的应用1．巩固栈的定义及表示。2．掌握栈的应用方法,理解栈的重要作用。Ø教学重点：利用栈实现表达式求值Ø教学难点：利用栈实现表达式求值Ø授课内容3．1.4栈的应用举例由于栈的“先进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。【例3.1】简单应用：数制转换问题将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3456，r=8为例转换方法如下：NN/8（整除）N%8（求余）34674333低4335415466606高所以：（3456）10=（6563）8我

2、们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。算法思想如下：当N>0时重复1，21．若N≠0，则将N%r压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。2．用N/r代替N算法如下：typedefintdatatype;#defineL10voidconversion(intN，intr)voidconversion(intN，intr){SeqStacks;{ints[L],top;/*定义一

3、个顺序栈*/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)算

4、法3.1(a)是将对栈的操作抽象为模块调用，使问题的层次更加清楚。而算法3.1(b)中的直接用int向量S和int变量top作为一个栈来使用，往往初学者将栈视为一个很复杂的东西，不知道如何使用，通过这个例子可以消除栈的“神秘”，当应用程序中需要一个与数据保存时相反顺序使用数据时，就要想到栈。通常用顺序栈较多，因为很便利。在后面的例子中，为了在算法中表现出问题的层次，有关栈的操作调用了的相关函数，如象算法3.1(a)那样，对余数的入栈操作：Push_SeqStack(&s，N%r);因为是用c语言描述，第一个参数是栈的地址才能对栈进行加工

5、。在后面的例子中，为了算法的清楚易读，在不至于混淆的情况下，不再加地址运算符，请读者注意。【例3.2】利用栈实现迷宫的求解。问题：这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解思想：回溯法是一种不断试探且及时纠正错误的搜索方法。下面的求解过程采用回溯法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向;若所有的方向均没有

6、通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向。需要解决的四个问题：1．表示迷宫的数据结构：设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1;其中：0表示通路，1表示不通，当从某点向下试探时，中间点有8个方向可以试探，（见图3.4）而四个角点有3个方向，其它边

7、缘点有5个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为8，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。如图3.4表示的迷宫是一个6×8的迷宫。入口坐标为（1，1），出口坐标为（m，n）。入口(1,1)0123456789第三章栈和队列0111111111111011101111211010111113101000001141011101111511001100016101100110171111111111出口(6,8

8、)图3.4用maze[m+2][n+2]表示的迷宫迷宫的定义如下：#definem6/*迷宫的实际行*/#definen8/*迷宫的实际列*/intmaze[m+2][n+2];2．试探方向：在上述表示迷宫