精心整理数据结构课程设计课程名称:数据结构题目:迷宫设计系别:软件学院专业:移动设备应用开发班级: 15 级移动 1 班姓名:黄国峰学期: 2016-2017 第一学期指导教师:李博时间: 2016 年 12 月目录第一部分需求分析第二部分详细设计第三部分调试分析第四部分用户手册第五部分测试结果第六部分附录第七部分参考文献一、 需求分析1、对于给定的一个迷宫,给出一个出口和入口,找一条从入口到出口的通路,并把这条通路显示出来;如果没有找到这样的通路给出没有这样通路的信息。2、可以用一个 m×n 的长方阵表示迷宫, 0 和 1 分别表示迷宫中的通路和障碍。设精心整理计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i ,j ,d) 的形式输出,其中: (i ,j) 指示迷宫中的一个坐标,d 表示走到下一坐标的方向。4、手动设置迷宫是任意给定的,所以程序要能够对给定的迷宫生成对应的矩阵表示,所以程序的输入包括了矩阵的行数、列数、迷宫内墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。5、自动生成的迷宫原理很简单,因为0 和 1 分别代表通道和障碍物,所以只需要随机生成 0 和 1 然后再给最外围都赋值为1,就形成了新的迷宫。二、详细设计1、计算机解迷宫通常用的是“穷举求解“方法,即从人口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。可以二维数组存储迷宫数据,通常设定入口点的下标为(1 ,1) ,出口点的下标为 (n ,n) 。为处理方便起见,可在迷宫的四周加一圈障碍。对于迷宫中任一位置,均可约定有东、南、西、北四个方向可通。2、如果在某个位置上四个方向都走不通的话,就退回到前一个位置,换一个方向再试,如果这个位置已经没有方向可试了就再退一步,如果所有已经走过的位置的四个方向都试探过了,一直退到起始点都没有走通,那就说明这个迷宫根本不通。3、所谓" 走不通 " 不单是指遇到 " 墙挡路 " ,还有" 已经走过的路不能重复走第二次" ,它包括 "曾经走过而没有走通的路" 。显然为了保证在任何位置上都能沿原路退回,需要用一个" 后进先出 " 的结构精心整理即栈来保存从入口到当前位置的路径。并且在走出出口之后...