《数据结构》课程设计报告
题目——迷宫求解
班 级： 信息与计算科学
0601
姓 名：张 俊（ 20061883 ）
高 宇（ 20061837 ）
曹志明（ 20061829 ）
李金德（ 20061844 ）
路阳阳（ 20061851 ）
刘后飞（ 20061849 ）
1
许 茹（ 20061875 ）
时 间： 2008/6/9---2008/6/15
一 需求分析
（1）以二维数组 Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和 Maze[m+1][j]
(0<=j<=n+1)及 Maze[i][0]和 Maze[i][n+1](0<=i<=m+1)为添加的一圈障碍。数组
中以元素值为 1 表示通路，0 表示障碍，限定迷宫的大小 m,n<=25。
（2）用户输入迷宫的数据时：文件中第一行的数据为迷宫的行数 m 和列数 n；
从第 2 行至第 m+1 行（每行 n 个数）为迷宫值，同一行中的两个数字之间用空
白字符相隔。
（3）迷宫的入口位置和出口位置可由用户随时设定。
（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出其中，
字符“0”表示障碍，字符“k”表示路径上的位置字符“-1”表示“死胡同”，即曾途径
然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则
报告相应信息。
（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修
改，便可求得全部路径。
（6）测试数据见附录，当入口位置为（1,1）,出口位置为（5，5）.
（7）程序执行的命令为：
1）创建迷宫;2）求解迷宫；3）输出迷宫的解。
二、概要设计
1、设定栈的抽象数据类型定义：
2
ADT Stack{
数据对象：D={ai|ai∈CharSet,i=1,2..,n,n>=0}
数据关系：R1={<ai-1，ai>|ai-1，ai∈D，i=2，..，n}
基本操作：
InitStack（&S）
操作结果：构造一个空栈 S。
DestroyStack(&S)
初始条件：栈 S 已存在；
操作结果：销毁栈 S。
ClearStack(&S)
初始条件：栈 S 已存在；
操作结果：将 S 清为空栈。
StackLength(S)
初始条件：栈 S 已存在；
操作结果：返回栈 S 的长度。
StackEmpty(S)
初始条件：栈 S 已存在；
操作结果：若栈 S 为空栈，则返回 TURE,否则返回 FALSE.
Push(&S,e)
初始条件：栈 S 已存在；
操作结果：在栈 S 的栈顶插入新的栈顶元素 e。
Pop（&S）
初始条件：栈 S 已存在；
操作结果：在栈 S 不空，则以 e 返回其值。
}
2.设定迷宫抽象数据类型为：
ADT Maze{
数据对象： D={aij|aij∈{'0','1','99'},0<=i<=m+1,0<=j<=n+1,m,n<=10}
数据关系： R={ROW,COL}
ROW={<ai-1,aij>|ai-1,aij∈D,i=1,……,m+1,j=0,……,n+1}
COL={<aij-1,aij>|aij-1,aij∈D,i=0,……,m+1,j=1,……,n+1}
基本操作：
InitMaze(&M,a,row,col)
初始条件：二维数组 a[row+2][col+2]已存在,其中自第一行至第 row+1 行,每行中自
第 1 列至第 col+1 列的元素已有值,并且以值 1 表示通路,以值 0 表示障碍.
操作结果：构成迷宫的字符型数组,以’1’表示通路,以字符'0'表示障碍,并在
迷宫四周加上一圈障碍.
MazePath(&M)
初始条件：迷宫 M 已被赋值.
操作结果：若迷宫 M 中存在一条通路,则按如下规定改变迷宫 M 的状态:以字符'k'表示
路径上的位置.字符'-1'表示“死胡同”;否则迷宫的状态不变.
3
PrintMaze(M)
初始条件：迷宫 M 已存在.
操作结果：以字符形式输出迷宫.
}ADTMaze.
3.本程序包含三个模块
1）主程序模块：
Void main()
{
初始化；
接受命令；
处理命令；
}
2）栈模块——实现栈抽象数据类型
3）迷宫模块——实现迷宫抽象数据类型
各模块之间的调用关系如下：
主程序模块
迷宫模块
栈模块
4.求解迷宫中一调通路的伪码算法：
设定当前位置的初值为入口位置；
do {
若当前位置可通，
则{ 将当前位置插入栈顶； // 纳入路径
若该位置是出口位置，则结束； // 求得路径存放在栈中
否则切换当前位置的东邻方块为新的当前位置；
}
否则 {
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为演顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶的位置均不可通，
则{ 删去栈顶位置； // 后退一步，从路径中删去该通道块，
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
}
}
} while（栈不空）；
4
{ 栈空说明没有路径存在 }
三、详细设计
1.坐标位置类型
typedef struct{
int r，c； // 迷宫中 r 行 c 列的位置
}PosType；
2.迷宫类型
typedef struct{
int m，n；
char arr[RANGE] [RANGE]; // 各位置取值'0''1'99'
} Maze Type；
void InitMaze（MazeType &maze，int a[][],int row,int col ）
// 按照用户输入的 row 行和 col 列的二维数组（元素值为 0 或 1）
//设置迷宫 maze 的初值，包括加上边缘一圈的值
bool MazePath(MazeType &maze,PosType start,PosType end)
//求解迷宫 maze 中，从入口 start 到出口 end 的一条路径，
//若存在，则返回 TRUE，否则返回 FALSE
void PrintMaze(MazeType maze)
//将迷宫以方阵的形式输出.
3.栈类型
typedef struct{
int step;//当前位置在路径上的“符号”
PosType seat;//当前的坐标位置
directiveType di;//往下一坐标位置的方向
}ElemType;//栈的元素类型
typedef strut NodeType{
ElemType date;
NodeType *next;
}NodeType,*LinkType; //结点类型，指针类型
typedef struct{
LinkType top;
int size;
}Stack;
栈的基本操作设置如下；
void InitStack(Stack &S)
//初始化，设 S 为空栈（S.top=NULL)
void DestoryStack（Stack &S)
//销毁栈 S，并释放所占空间
void ClearStack(Stack &S)
5
