文档介绍：《数据结构与算法设计》迷宫问题实验报告——实验二专业:物联网工程班级:物联网 1班学号:15180118姓名:刘沛航一、实验目的本程序是利用非递归的方法求出一条走出迷宫的路径,并将路径输出。首先由用户输入一组二维数组来组成迷宫, 确认后程序自动运行,当迷宫有完整路径可以通过时, 以0和1所组成的迷宫形式输出,标记所走过的路径结束程序; 当迷宫无路径时,提示输入错误结束程序。二、实验内容用一个m*m长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫, 求出一条从入口到出口的通路,或得出没有通路的结论。三、程序设计1、概要设计1)设定栈的抽象数据类型定义ADTStack{数据对象:D={ai|ai属于CharSet,i=1、2⋯n,n>=0}数据关系:R={<ai-1,ai>|ai-1,ai属于D,i=2,3,⋯n}基本操作:InitStack(&S)操作结果:构造一个空栈Push(&S,e)初始条件:栈已经存在操作结果:将 e所指向的数据加入到栈 s中Pop(&S,&e)初始条件:栈已经存在操作结果:若栈不为空,用 e返回栈顶元素,并删除栈顶元素Getpop(&S,&e)初始条件:栈已经存在操作结果:若栈不为空,用 e返回栈顶元StackEmpty(&S)初始条件:栈已经存在操作结果:判断栈是否为空。若栈为空,返回 1,否则返回 0Destroy(&S)初始条件:栈已经存在操作结果:销毁栈 s}ADTStack2)设定迷宫的抽象数据类型定义ADTyanshu {数据对象:D={ai,j|ai,j 属于{‘、’‘、*’‘@’、‘#’},0<=i<=M,0<=j<=N}数据关系:R={ROW,COL}ROW={<ai-1,j,ai,j>|ai-1,j,ai,j属于D,i=1,2,⋯M,j=0,1,⋯N}COL={<ai,j-1,ai,j>|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){初始条件:迷宫 maze已被赋值操作结果:若迷宫maze中存在一条通路,则按如下规定改变 maze的状态;以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’;否则迷宫的状态不变}PrintMaze(M){初始条件:迷宫 M已存在操作结果:以字符形式输出迷宫}}ADTmaze3)本程序包括三个模块a、主程序模块voidmain (){初始化;构造迷宫;迷宫求解;迷宫输出;}b、栈模块——实现栈的抽象数据类型c、迷宫模块——实现迷宫的抽象数据类型2、详细设计1)坐标位置类型:typedefstruct{introw; //迷宫中的行intcol; //......的列}PosType;//坐标2)迷宫类型:typedefstruct{intm,n;intarr[RANGE][RANGE];}MazeType; //迷宫类型void//设置迷宫的初值,包括边缘一圈的值BoolMazePath(MazeType&maze,PosTypestart,PosTypeend)//求解迷宫 maze中,从入口 start到出口end的一条路径//若存在,则返回 true,否则返回 falseVoidPrintMaze(MazeTypemaze)//将迷宫打印出来3)栈类型:typedefstruct{int step; //当前位置在路径上的 "序号"PosType seat; //当前的坐标位置DirectiveType di; //往下一个坐标位置的方向}SElemType;//栈的元素类型typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;栈的基本操作设置如下:VoidInitStack(SqStack&S)//初始化,设 S为空栈(=NUL)VoidDestroyStack(Stack&S)//销毁栈S,并释放空间VoidClearStack(SqStack&S)//将栈S清空IntStackLength(SqStack&S)//返回栈S的长度StatusStackEmpty(SqStack&S)?、若S为空栈(==NULL),则返回TRUE,否则返回FALSEStatueGetTop(SqStack&S,SEle