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

课程设计说明书 No. 1 课 程 设 计 任 务 书 专专 业业计算机科学与技术计算机科学与技术 设设 计计 起起 止止 日日 期期 班班 级级姓姓 名名 设计题目：迷宫问题的操作设计题目：迷宫问题的操作 设计任务（主要技术参数）设计任务（主要技术参数） ：： 学会运用数据结构建立迷宫问题，编造出迷宫并设计出走出迷宫的方法 硬件环境：处理器：英特尔 第三代酷睿 i3-3110M @ 2.40GHz 双核 内存：4GB(三星 DDR3 1333MHz) 主硬盘：希捷 ST500LM012 HN-M500MBB (500GB/5400 转/分) 显示器：三星 SEC3649(14 英寸) 软件环境：操作系统：Windows 8 64 位(DirectX 11) 开发环境： VC++6.0 指导教师评语：指导教师评语： 成绩：成绩：签字：签字： 年年月月日日 课程设计说明书 No. 2 1 1、课程设计目的、课程设计目的 为了配合《数据结构》课程的开设，通过设计一完整的程序，掌握数据 结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本 方法特进行题目为两个链表合并的课程设计。 通过此次课程设计充分锻炼有关数 据结构中链表的创建、合并等方法以及怎样通过转化成C语言在微机上运行实现 等其他方面的能力。 2 2．课程设计的内容与要求．课程设计的内容与要求 2.1 问题描述： 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大 盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有 一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对 同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老 鼠经过多次试验最终学会走通迷宫的路线。 设计一个计算机程序对任意设定的矩 形迷宫如下图 A 所示，求出一条从入口到出口的通路，或得出没有通路的结论。 图 A 2.2 设计要求： 要求设计程序输出如下： (1) 建立一个大小为 m×n 的任意迷宫（迷宫数据可由用户输入或由程序自动生 成） ，并在屏幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列， （i,j）表示通路上某一点的坐标。 课程设计说明书 No. 3 （3）用一种标志（如数字 8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 3 3．课程设计总体方案及分析．课程设计总体方案及分析 3.1 问题分析： 1.迷宫的建立： 迷宫中存在通路和障碍， 为了方便迷宫的创建， 可用 0 表示通路， 用 1 表示障碍， 这样迷宫就可以用 0、1 矩阵来描述， 2.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可 以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先 定义一个较大的二维数组 maze[M+2][N+2],然后用它的前 m 行 n 列来存放元素， 即可得到一个 m×n 的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷 宫出口位置。 注：其中M，N 分别表示迷宫最大行、列数，本程序M、N 的缺省值为 39、39， 当然，用户也可根据需要，调整其大小。 3.迷宫路径的搜索： 首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜 索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动 到该位置， 然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相 邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标 记为 2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存 在一个队列中， 如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路 径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果 找到路径，则为最短路径。 课程设计说明书 No. 4 以矩阵 0 0 1 0 1为例，来示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 首先，将位置(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 910 (0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3) (3,4) 122345679-10 由此可以看出，得到最短路径：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 搜索算法流程图如下所示： ： 课程设计说明书 No. 5 3.2 概要设计 1.①构建一个二维数组 maze[M+2][N+2]用于存储迷宫矩阵 ②自动或手动生成迷宫，即为二维数组 maze[M+2][N+2]赋值 ③构建一个队列用于存储迷宫路径 ④建立迷宫节点 struct point,用于存储迷宫中每个节点的访问情况 ⑤实现搜索算法 ⑥屏幕上显示操作菜单 2.本程序包含 10 个函数： (1)主函数 main() (2)手动生成迷宫函数 shoudong_maze() 课程设计说明书 No. 6 (3)自动生成迷宫函数 zidong_maze() (4)将迷宫打印成图形 print_maze() (5)打印迷宫路径 (若存在路径) result_maze() (6)入队 enqueue() (7)出队 dequeue() (8)判断队列是否为空 is_empty() (9)访问节点 visit() (10)搜索迷宫路径 mgpath() 3.3 详细设计 实现概要设计中定义的所有数据类型及操作的伪代码算法 1.节点类型和指针类型 迷宫矩阵类型：int maze[M+2][N+2];为方便操作使其为全局变量 迷宫中节点类型及队列类型：struct point{int row,col,predecessor} que[512] 2.迷宫的操作 (1)手动生成迷宫 void shoudong_maze(int m,int n) {定义 i,j 为循环变量 for(i0 且 maze[p.row-1][p.col]==0,说明未到迷宫上边界，且其上方有通 路,则 visit(p.row,p.col+1,maze),将上方节点入队标记已访问} 访问到出口(找到路径)即 p.row==m-1 且 p.col==n-1,则逆序将路径标记为 3 即 maze[p.row][p.col]==3; while(p.predecessor!=-1) {p=queue[p.predecessor]; maze[p.row][