1、 数据结构课程设计说明书 班级 小组成员:_成绩: _ 小组成员: 成绩: _ 小组成员: _成绩: _ 设计题目:_ 迷宫问题 _ 设计时间: 2013.7.1 至 2013.7.5 指导教师:_ _ 评 语:_ _ _ _ 评阅教师: _ I 目录 设计总说明II 第 1 章 课程设计内容和要求 1 1.1 问题描述. 1 1.2 设计要求. 1 1.3 需求分析. 2 第 2 章 课程设计总体方案及分析 3 2.1 问题分析 3 2.2 系统总体设计 4 2.3 系统详细设计. 6 第 3 章 程序运行结果与分析 11 3.1 调试分析 11 3.2 测试结果 11 第 4 章 心得总结
2、 20 参考文献 21 附录 22 II 设计总说明：本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向前 探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直 至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要 用一个保存从入口到当前位置的路径的结构。因此，在求迷宫通路的算法中要应 用“队列”的思想假设“当前位置”指的是“在搜索过程中的某一时刻所在图中 某个方块位置” ， 则求迷宫中一条路径的算法的基本思想是： 若当前位置 “可通” ， 则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当 前位置”，如此重复直至到达出口；若当前位
3、置“不可通”，则应顺着“来向” 退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通 道块的四周 4 个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓 “下一位置”指的是当前位置四周 4 个方向（上、下、左、右）上相邻的方块。 假设以队列记录 “当前路径” ， 则队列中存放的是 “当前路径上最后一个通道块” 。 由此，“纳入路径”的操作即为“当前位置入队”；“从当前路径上删除前一通 道块”的操作即为“出队”。 关键词：迷宫；穷举；队列。 第 1 页 共 31 页 第 1 章 课程设计内容和要求 1.1 问题描述 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无 顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子 仅有一个出口， 在出口处放置一块奶酪， 吸引老鼠在迷宫中寻找道路以到达出口。 对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。 老鼠经过多次试验最终学会走通迷宫的路线。 设计一个计算机程序对任意设定的 矩形迷宫如下图 A 所示，求出一条从入口到出口的通路，或得出没有通路的 论。 图 1.1 矩形迷宫图 1.2 设计要求 要求设计程序输出如下： (1) 建立一个大小为 mn 的任意迷宫（迷宫数据可由用户输
