章丽玲

(湖北第二师范学院 计算机学院，武汉 430205)

迷宫问题是“数据结构”课程中经典的非数值型的程序设计问题，理解迷宫问题的不同解决思路，对掌握《数据结构》课程的核心知识点具有非常重要的意义，本文将采用几种典型的数据结构，利用不同的算法来实现迷宫问题。

1构造迷宫

用一个二维数组mg[M+2][N+2]表示迷宫，如图1所示，M=8，N=8，状态为0时表示对应方块是通道(可走)，状态为1时表示对应方块是障碍物(不可走)，为了算法方便，一般迷宫的外围加一条围墙。设定入口为mg[1][1]，出口为mg[8][8]。

图1 迷宫图

2 算法思路

求解迷宫问题通常采用“穷举探索求解法”，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走，否则沿原路退回(回溯)，换一个可行的方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能原路退回，常用的数据结构有栈和队列，如果把迷宫中的每一个位置看作是一个点的话，那么就可以把迷宫转换为一个个相连或分断的各个顶点之间的关系，因此，可以使用另一种数据结构——无向图来表示。下面将针对不同的数据结构来实现迷宫问题。

2.1 用栈实现迷宫

栈是一种只能在一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)。栈的主要特点是后进先出，正是栈的这一特点使得它成为解决迷宫问题的数据结构。

2.1.1 数据结构设计

采用顺序栈实现迷宫，迷宫栈声明如下：

typedef struct

{

int i; //当前……