《数据结构与算法设计》迷宫问题实验报告
实验二
专业物联网工程
班级物联网1班
学号
姓名
f一、实验目的
本程序是利用非递归的方法求出一条走出迷宫的路径并将路径输出。首先由用户输入一组二维数组来组成迷宫确认后程序自动运行当迷宫有完整路径可以通过时以0和1所组成的迷宫形式输出标记所走过的路径结束程序当迷宫无路径时提示输入错误结束程序。
二、实验内容
用一个mm长方阵表示迷宫0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫求出一条从入口到出口的通路或得出没有通路的结论。
三、程序设计
1、概要设计
1设定栈的抽象数据类型定义
ADTStack
数据对象Daiai属于CharSeti1、2…
0
数据关系Rai1aiai1ai属于Di23…
基本操作
I
itStackS
操作结果构造一个空栈
PushSe
初始条件栈已经存在
操作结果将e所指向的数据加入到栈s中
PopSe
初始条件栈已经存在
操作结果若栈不为空用e返回栈顶元素并删除栈顶元素GetpopSe
初始条件栈已经存在
操作结果若栈不为空用e返回栈顶元
fStackEmptyS
初始条件栈已经存在
操作结果判断栈是否为空。若栈为空返回1否则返回0DestroyS
初始条件栈已经存在
操作结果销毁栈s
ADTStack
2设定迷宫的抽象数据类型定义
ADTya
shu
数据对象Daijaij属于‘’、‘’、‘’、‘’0iM0jN
数据关系RROWCOL
ROWai1jaijai1jaij属于Di12…Mj01…N
COLaij1aijaij1aij属于Di01…Mj12…N
基本操作
I
itMazeMazeTypemazei
taCOLi
trowi
tcol
初始条件二维数组i
taCOL已经存在其中第1至第m1行每行自第1到第
1列的元素已经值并以值0表示障
碍值1表示通路。
操作结果构造迷宫的整形数组以空白表示通路字符‘0’表示障碍
在迷宫四周加上一圈障碍
MazePathmaze
初始条件迷宫maze已被赋值
操作结果若迷宫maze中存在一条通路则按如下规定改变maze的状态以字符‘’表示路径上
的位置。字符‘’表示‘死胡同’否则迷宫的状态不变
Pri
tMazeM
初始条件迷宫M已存在
操作结果以字符形式输出迷宫
ADTmaze
3本程序包括三个模块
a、主程序模块
fvoidmai

初始化
构造迷宫
迷宫求解
迷宫输出
b、栈模块实现栈的抽象数据类型
c、迷宫模块实现迷宫的抽象数据类型
2、详细设计
1坐标位置类型
typedefstruct
i
trow迷宫中的行
i
tcol的列
PosType坐标
2迷宫类型
typedefstruct
i
tm
i
tarrRANGERANGE
MazeType迷宫类型
voidI
itMazeMazeTypemazei
taCOLi
trowir