迷宫问题求解.doc

迷宫问题求解课程设计报告课题名称: 迷宫问题的求解及演示姓名: 学号:专业: 计算机与信息学院班级: 指导教师: 共 17页数据结构课程设计任务书针对本课程设计,完成以下课程设计任务书: 1. 熟悉系统实现工具和上机环境。 2. 根据课程设计任务,查阅相关资料。 3. 针对所选课题完成以下工作: (1 )需求分析(2 )概要设计(3 )详细设计(4 )编写源程序(5 )静态走查程序和上机调试程序 4. 书写上述文档和撰写课程设计报告共 17页目录第一部分课程设计任务书………………………………………… 1 第二部分课程设计报告…………………………………………… 2 第一章课程设计内容和要求………………………………………… 4 问题描述……………………………………………… 4 需求分析……………………………………………… 4 第二章课程设计总体方案及分析…………………………………… 4 概要设计……………………………………………… 7 详细设计……………………………………………… 7 调试分析……………………………………………… 10 测试结果……………………………………………… 10 第三章设计总结………………………………………………… 13 课程设计总结………………………………………………… 13 参考文献………………………………………………… 附录( 源代码) ……………………………………………… 14 共 17页第二部分课程设计报告第一章课程设计内容和要求 问题描述: 迷宫以 16*16 的矩阵存储在数据文件中( 迷宫中的障碍物要占到一定比例) ,编写非递归的程序,求出一条从入口到出口的路径并显示之(结果若能用 C 的绘图函数显示更好) 需求分析: 1 .要求设计程序输出如下: (1) 建立一个大小为 m×n 的任意迷宫( 迷宫数据可由用户输入或由程序自动生成) ,并在屏幕上显示出来; (2) 找出一条通路的二元组( i,j) 数据序列,( i,j) 表示通路上某一点的坐标。(3 )用一种标志(如数字 8 )在迷宫中标出该条通路; (4 )在屏幕上输出迷宫和通路; (5 )上述功能可用菜单选择。 2. 迷宫的建立: 迷宫中存在通路和障碍,为了方便迷宫的创建,可用 0 表示通路,用 1 表示障碍,这样迷宫就可以用 0、1 矩阵来描述, 3. 迷宫的存储: 迷宫是一个矩形区域, 可以使用二维数组表示迷宫, 这样迷宫的每一个位置都可以用其行列号来唯一指定,但是二维数组不能动态定义其大小, 我们可以考虑先定义一个较大的二维数组 maze[M+2][N+2], 然后用它的前m行n 列来存放元素, 即可得到一个 m×n 的二维数组, 这样(0,0) 表示迷宫入口位置, (m-1,n-1) 表示迷宫出口位置。共 17页注: 其中 M,N 分别表示迷宫最大行、列数, 本程序 M、N 的缺省值为 39、 39 ,当然, 用户也可根据需要,调整其大小。 4. 迷宫路径的搜索: 首先从迷宫的入口开始, 如果该位置就是迷宫出口, 则已经找到了一条路径,搜索工作结束。否则搜索其上、下、左、右位置是否是障碍,若不是障碍,就移动到该位置,然后再从该位置开始搜索通往出口的路径; 若是障碍就选择另一个相邻的位置, 并从它开始搜索路径。为防止搜索重复出现,则将已搜索过的位置标记为 2 ,同时保留搜索痕迹,在考虑进入下一个位置搜索之前, 将当前位置保存在一个队列中, 如果所有相邻的非障碍位置均被搜索过, 且未找到通往出口的路径, 则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法, 如果找到路径, 则为最短路径。以矩阵 00101 为例,来示范一下 100101000100100 首先, 将位置(0,0)( 序号 0) 放入队列中, 其前节点为空, 从它开始搜索, 其标记变为 2 ,由于其只有一个非障碍位置,所以接下来移动到(0,1)( 序号 1), 其前节点序号为 0, 标记变为 2, 然后从(0,1) 移动到(1,1)( 序号 2), 放入队列中,其前节点序号为 1, (1,1) 存在(1, 2)( 序号 3)、(2, 1)( 序号 4) 两个可移动位置, 其前节点序号均为 2. 对于每一个非障碍位置, 它的相邻非障碍节点均入队列, 且它们的前节点序号均为该位置的序号, 所以如果存在路径,则从出口处节点的位置,逆序就可以找到其从出口到入口的通路。如下表所示: 012345678 9 10 由此可以看出,得到最短路径: (3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 搜索算法流程图如下所示: 共 17页第二章课程设计总体方案及分