第九讲 栈的应用
1．巩固栈的定义及表示。 2．掌握栈的应用方法,理解栈的重要作用。
? 教学重点：
利用栈实现表达式求值 ? 教学难点：
利用栈实现表达式求值 ? 授课内容
3．1.4 栈的应用举例
由于栈的“先进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。 【例 3.1】简单应用：数制转换问题
将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3456，r=8为例转换方法如下：
N N / 8 （整除） N % 8（求余）
3467 433 3 低 433 54 1 54 6 6
6 0 6 高 所以：（3456）10 =（6563）8
我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。
算法思想如下：当N>0时重复1，2
1． 若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算
法结束。
2． 用N / r 代替 N 算法如下：
typedef int datatype; #define L 10
void conversion(int N，int r) void conversion(int N，int r)
{ SeqStack s; { int s[L],top; /*定义一个顺序栈*/ datetype x; int x;
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】 利用栈实现迷宫的求解。
问题： 这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。
求解思想：回溯法是一种不断试探且及时纠正错误的搜索方法。下面的求解过程采用回溯法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。
在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向。
需要解决的四个问题：
1．表示迷宫的数据结构：
设迷宫为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)
0 1 2 3 4 5 6 7 8 9 0 1
1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 2 3 4 5 6 7
1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 出口 (6,8)
图 3.4 用maze[m+2][n+2]表示的迷宫
迷宫的定义如下：
#define m 6 /* 迷宫的实际行 */ #define n 8 /* 迷宫的实际列 */ int maze [m+2][n+2] ;
2．试探方向：
在上述表示迷宫的情况下，每个点有8个方向去试探，如当前点的坐标(x,y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，如图3.5所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这8个方向的坐标增量放在一个结构数组move [ 8 ]中，在move 数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。move数组如图3.6所示。
Move数组定义如下：
typedef struct { int x，y } item ; item move[8] ;
这样对move的设计会很方便地求出从某点 (x，y) 按某一方向 v (0<=v<=7) 到达的新点（i，j）的坐标：i=x+move[v].x ; j=y+move[v].y ;
(x-1，y)
(x-1，y-1)
(x-1，y+1)
0 0 1 1 (x，y-1)
(x，y)
(x，y+1)
2 1 3 1 (x+1，y-1)
(x+1，y)
图3.5 与点(x，y)相邻的8个点及坐标
x y 1 1 0 -1 -1
3． 栈的设计：
当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从
(x+1，y+1)
4 0 5 -1 -1 6 -1 0 7 -1 1 前一点到达本点的方向。对于图3.4所示迷宫，依次入栈为：
武汉软件工程职业学院数据结构讲义第09讲_栈的应用
