迷宫求解数据结构课程设计

《迷宫求解数据结构课程设计》由会员分享，可在线阅读，更多相关《迷宫求解数据结构课程设计（19页珍藏版）》请在毕设资料网上搜索。

1、 目目 录录 1 课程设计课程设计 错误!未定义书签。 1.1 问题描述 . 错误错误!未定义书签。未定义书签。 1.2 需求分析 . 2 1.3 概要设计 . 3 1.4 流程图 . 4 1.5 详细设计 . 5 1.6 调试分析 . 8 1.7 运行结果及分析 . 8 2 课程设计课程设计个人总结个人总结 11 附录附录 . 12 数据结构数据结构应用应用评分表评分表 . 18 1 1.1.1 1问题描述问题描述： a.问题描述：以一个 m * n 的长方阵表示迷宫，0和1分别表示迷宫的通路和障碍。设计 一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。

2、b.基本要求 ： （1）实现一个以链表做存储的栈类型，然后编写一个求解迷宫的非递归程序。求的通 路以三元组（i，j，d）的形式输出，其中： （i，j）指示迷宫中的一个坐标，d 表示走 到下一坐标的方向。如：对于下列数据的迷宫，输出一条通路： （1，1，1） ， （1，2，2） ， （2，2，2） ， （3，2，3） ， （3，1，2）。 （2）编写递归形式的算法，求得迷宫中所有可能的道路； （3）以方阵形式输出迷宫及其到道路（选做） c.测试数据：迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0

3、 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 d.实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着米 一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探 索，直至出口位置，求的一条通路。假如所有的可能的通路都探索到而未能到出口，则 所设定的迷宫没有通路。 可以二维数组存储迷宫数据， 通常设定入口点的下标为 （1， 1） ， 出口点的下标为（n，n） 。为处理器方便起见，可在迷宫的四周加上

4、一圈障碍 。对于迷 2 宫中任一位置，均可约定有东、西、南、北四个方向可通。 1.1.2 2 需求分析需求分析： 本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向前探索，若能走通，则 继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到 为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存 从入口到当前位置的路径。因此，在求迷宫通路的算法中要应用“栈”的思想假设“当 前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置” ，则求迷宫中一条 路径的算法的基本思想是：若当前位置“可通” ，则纳入“当前路径” ，并继续朝“下一 位置”探索

5、，即切换“下一位置”为“当前位置” ，如此重复直至到达出口；若当前位 置“不可通” ，则应顺着“来向”退回到“前一通道块” ，然后朝着除“来向”之外的其 他方向继续探索；若该通道块的四周 4 个方块均“不可通” ，则应从“当前路径”上删 除该通道块。所谓“下一位置”指的是当前位置四周 4 个方向（上、下、左、右）上相 邻的方块。假设以栈记录“当前路径” ，则栈顶中存放的是“当前路径上最后一个通道 块” 。由此， “纳入路径”的操作即为“当前位置入栈” ； “从当前路径上删除前一通道块” 的操作即为“出栈” 。 问题分析： 1.迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用 0 表

6、示通路，用 1 表示 障碍，这样迷宫就可以用 0、1 矩阵来描述， 2.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置 都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考 虑先定义一个较大的二维数组 mazeM+2N+2,然后用它的前 m 行 n 列来存放元 素，即可得到一个 mn 的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1) 表示迷宫出口位置。 注：其中 M，N 分别表示迷宫最大行、列数，本程序 M、N 的缺省值为 39、39， 当然，用户也可根据需要，调整其大小。 3.迷宫路径的搜索： 3 首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路 径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍， 就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择 另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索 过的位置标记为 2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当 前位置保存在一个队列中，如果所有相邻的非障碍位