资源描述：
《数据结构迷宫问题实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构与算法设计》迷宫问题实验报告——实验二专业：物联网工程班级：物联网1班学号：15180118姓名：刘沛航一、实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。二、实验内容用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得
2、出没有通路的结论。三、程序设计1、概要设计（1） 设定栈的抽象数据类型定义ADTStack{数据对象：D={ai
3、ai属于CharSet，i=1、2…n，n>=0}数据关系：R={
4、ai-1,ai属于D，i=2,3,…n}基本操作： InitStack(&S) 操作结果：构造一个空栈 Push（&S，e） 初始条件：栈已经存在 操作结果：将e所指向的数据加入到栈s中
5、 Pop（&S,&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元 StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1
6、，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s}ADTStack（2）设定迷宫的抽象数据类型定义ADTyanshu{数据对象：D={ai,j
7、ai,j属于{‘’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N}数据关系：R={ROW,COL} ROW={
8、ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N} COL={9、i,j-1,ai,j>
10、ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N}基本操作：InitMaze(MazeType&maze,inta[][COL],introw,intcol){初始条件：二维数组inta[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍 在迷宫四周加上一圈障碍 MazePath（&maze）{
11、 初始条件：迷宫maze已被赋值 操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变}PrintMaze（M）{初始条件：迷宫M已存在操作结果：以字符形式输出迷宫} }ADTmaze（3）本程序包括三个模块a、 主程序模块voidmain(){初始化；构造迷宫；迷宫求解；迷宫输出；}b、 栈模块——实现栈的抽象数据类型c、 迷宫模块——实现迷宫的抽象
12、数据类型2、详细设计（1）坐标位置类型：typedefstruct{ introw; //迷宫中的行 intcol; //......的列}PosType;//坐标 （2） 迷宫类型：typedefstruct{ intm,n; intarr[RANGE][RANGE];}MazeType; //迷宫类型void InitMaze(MazeType&ma
13、ze,inta[][COL],introw,intcol)//设置迷宫的初值，包括边缘一圈的值BoolMazePath(MazeType&maze,PosTypestart,PosTypeend)//求解迷宫maze中，从入口start到出口end的一条路径//若存在，则返回true，否则返回falseVoidPrintMaze
