v1.0 可编辑可修改
《数据结构与算法设计》
迷宫问题实验报告
——实验二
专业：物联网工程 班级：物联网1班 学号： 姓名：刘沛航
1
v1.0 可编辑可修改 一、 实验目的
本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容
用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和
障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
三、程序设计 1、概要设计 （1）
设定栈的抽象数据类型定义
ADT Stack{
数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={
InitStack(&S)
操作结果：构造一个空栈 Push（&S，e）
初始条件：栈已经存在
操作结果：将e所指向的数据加入到栈s中
Pop（&S,&e）
初始条件：栈已经存在
2
v1.0 可编辑可修改 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素
Getpop（&S，&e）
初始条件：栈已经存在
操作结果：若栈不为空，用e返回栈顶元
StackEmpty(&S)
初始条件：栈已经存在
操作结果：判断栈是否为空。若栈为空，返回1，否则返回0
Destroy(&S)
初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack
（2）设定迷宫的抽象数据类型定义
ADT yanshu{
数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL}
ROW={
COL={
InitMaze(MazeType &maze, int a[][COL], int row, int col){
初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。
3
v1.0 可编辑可修改 操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示
障碍
在迷宫四周加上一圈障碍
MazePath（&maze）{
初始条件：迷宫maze已被赋值
操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变 }
PrintMaze（M）{ 初始条件：迷宫M已存在 操作结果：以字符形式输出迷宫 }
}ADTmaze
（3）本程序包括三个模块
a、 主程序模块
void main() { 初始化； 构造迷宫； 迷宫求解； 迷宫输出； }
b、 栈模块——实现栈的抽象数据类型 c、 迷宫模块——实现迷宫的抽象数据类型
2、详细设计 （1）坐标位置类型： typedef struct{
4
v1.0 可编辑可修改 int row; ....的列
}PosType;先呢，想自己读入数据的，回来发现那样，很麻烦，所以
还是事先定义一个迷宫。
2.栈的元素类型 一开始有点迷惑，后来就解决了
3.本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n）
五、用户使用说明
1．本程序运行在windows系列的操作系统下，执行文件为：。
六、程序运行结果
1.建立迷宫：
2．通过1功能建立8*8的迷宫后，通过2功能继续建立迷宫内部：
5
数据结构迷宫问题实验报告
