资源描述：
《栈的迷宫求解(数据结构试验).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验二：迷宫问题班级：姓名：学号：一、需求分析（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)为添加一圈障碍。数组中以元素值为0表示通路，1表示障碍，限定迷宫的大小m,n<=100。（2）用户输入迷宫的规模m,n；并按照此规模输入迷宫的具体数据。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置
2、，字符“@”表示“死胡同”，即曾途径然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。（6）测试数据见原题，当入口位置为（1，1），出口位置为（9，8）时，输出数据应为：**#@@@#*#@@@#**@@###*####@***#***@#***#*#####*####*###**（7）程序执行的命令为：1）创建迷宫；2）求解迷宫；3）输出迷宫的解。二、概要设计1.设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai
3、ai∈CharSet,i=
4、1,2,…,n,n>=0}数据关系：R1={
5、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为空栈，则返回TRUE，否则返回FALSE。GetTop(S,&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。
6、Push(&S,e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse(S,visit())初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()。}ADTStack2.设定迷宫的抽象数据类型为：ADTmaze{数据对象：D={ai,j
7、ai,j∈{‘’、‘#’、‘@’、‘*’}，0≤i≤m+1,0≤j≤n+1,m,n≤10}数据关系：R={ROW，COL}ROW={
8、ai-1,j，ai,j∈D,
9、i=1,……，m+1,j=0,……，n+1}COL={
10、ai,j-1,ai,j∈D,i=0,……，m+1,j=1,……，n+1}基本操作：InitMaze(&M,a,row,col)初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行、每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，以字符’6’表示通路，以字符‘4’‘1’表示障碍，并在迷宫四周加上一圈障碍。MazePath(&M)初始条件：迷宫M已被赋值,链栈S已经存在。操作结果：若迷宫M中存在一条通路，则
11、按如下规定改变迷宫M的状态：以字符“6”表示路径上的位置，字符“4”表示“死胡同”；否则迷宫的状态不变。PrintMaze(M)初始条件：迷宫M已存在。操作结果：以字符形式输出迷宫。}ADTmaze;3.本程序包含三个模块1）主程序模块：voidmain(){初始化；do{接受命令；处理命令；}while(命令！=“退出”)；}2）栈模块——实现栈抽象数据类型3）迷宫模块——实现迷宫抽象数据类型各模块之间的调用关系如下：4.求解迷宫中一条通路的伪码算法：设定当前位置的初值为入口位置；do{若当前位置可通，则{将当前位置插入栈顶；//纳入路径若该位置是出口位置，则结束；//求得路
12、径存放在栈中否则切换当前位置的东邻方块为新的当前位置；}否则{若栈不空且栈位置尚有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则{删去栈顶位置；//后退一步，从路径中删去该通道块，主程序模块迷宫模块栈模块若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；}}}while(栈不空)；{栈空说明没有路径存在}三、详细设计1．坐标位置类型typedefstruct{intr,c;//迷宫中行、列的范围}P
