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

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

第三

第三章栈和队列

第九

第九讲栈的应用

1．巩固栈的定义及表示。

2．掌握栈的应用方法,理解栈的重要作用。

教学重点：

利用栈实现表达式求值

教学难点：

利用栈实现表达式求值

授课内容

3．1.4栈的应用举例

由于栈的“先进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。

【例3.1】简单应用：数制转换问题

将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3456，r=8为例转换方法如下：

NN/8（整除）N%8（求余）

34674333低

433541

5466

606高

所以：（3456）10=（6563）8

我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。

算法思想如下：当N0时重复1，2

若N≠0，则将N%r压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。

用N/r代替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

1

1

1

1

1

1

1

1

0

1

1

1

0

1

1

1

1

2

1

1

0

1

0

1

1

1

1

1

3

1

0

1

0

0

0

0

0

1

1

4

1

0

1

1

1

0

1

1

1

1

5

1

1

0

0

1

1

0

0

0

1

6

1

0

1

1

0

0

1

1

0

1

7

1

1

1

1

1

1

1

1

1

1

出口(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的设计会很方便地求出从某点(x，y)按某一方向v(0=v=7)到达的新点（i，j）的坐标：i=x+move[v].x;j=y+move[v].y;

x

y

0

0

1

1

1

1

2

1

0

3

1

-1

4

0

-1

5

-1

-1

6

-1

0

7

-1

1

图3.6

图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)

栈的设计：

当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺