数据结构课程设计-迷宫问题

《数据结构课程设计-迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课程设计课程名称：数据结构题目：迷宫设计系别：软件学院专业：移动设备应用开发班级：15级移动1班姓名：学期：2016-2017第一学期指导教师：时间：2016年12月目录第一部分需求分析第二部分详细设计第三部分调试分析第四部分用户手册第五部分测试结果第六部分附录第七部分参考文献一、需求分析1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没有这样通路的信息。2、可以用一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通

2、路的结论。3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。4、手动设置迷宫是任意给定的，所以程序要能够对给定的迷宫生成对应的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。5、自动生成的迷宫原理很简单，因为0和1分别代表通道和障碍物，所以只需要随机生成0和1然后再给最外围都赋值为1，就形成了新的迷宫。二、详细设计1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否

3、则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2、如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通。3、所谓"走不通"不单是指遇到"墙挡路"，还有"

4、已经走过的路不能重复走第二次"，它包括"曾经走过而没有走通的路"。　　显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。4、若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径

5、”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。5、找通路的程序的关键部分可以表示如下：do{若当前位置可通，则{　　将当前位置插入栈顶；　　　　　　//纳入路径　　若该位置是出口位置，则算法结束；　　//此时栈中存放的是一条从入口位置到出口位置的路径　　否则切换当前位置的东邻方块为新的当前位置；}否则{　　若栈不空且栈顶位置尚有其他方向未被探索，　则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；　若栈不空但栈顶位置的四周均不可通，　则{删去栈顶位置；　　　　

6、//从路径中删去该通道块　　　若栈不空，则重新测试新的栈顶位置，　　直至找到一个可通的相邻块或出栈至栈空；　　}　}}while(栈不空)；6、程序中用的数据结构解析：①程序中用了顺序栈保存当前找到的路径，当前位置不可通时，可以出栈，退回到前一个位置再继续探索通路，栈的定义如下：structSqStack{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位};//顺序栈②栈中元素的类型结构程序中先定义了一个表示坐标的类型结构：structPo

7、sType//迷宫坐标位置类型{intx;//行值inty;//列值};栈中元素的类型结构如下：structSElemType//栈的元素类型{intord;//通道块在路径上的＂序号＂PosTypeseat;//通道块在迷宫中的＂坐标位置＂intdi;//从此通道块走向下一通道块的＂方向＂(0～3表示东～北)};7、主函数的流程图输出从起点到终点的坐标显示当前含有通路的迷宫结构输出没有这样的通路输入所求通路的起点终点坐标显示当前的迷宫的结构设置内墙设置外墙输入迷宫的行数列数（包括外墙）手动设置自动生成自动生成迷宫