数据结构课设--迷宫

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：迷宫算法院（系）：计算机学院专业：计算机科学与技术班级：84010103学号：2008040101061姓名：李雪城指导教师：丁一军沈阳航空航天大学课程设计报告I目录1课程设计介绍............................................................................................................21.1课程设计内容.......................................................................................................21.2课程设计要求.......................................................................................................22课程设计原理............................................................................................................22.1课设题目粗略分析...............................................................................................22.1.1迷宫的建立....................................................................................................22.1.2迷宫的存储....................................................................................................22.1.3迷宫路径的搜索............................................................................................22.2原理图介绍...........................................................................................................32.2.1功能模块图....................................................................................................32.2.2流程图分析...................................................................................................33数据结构分析............................................................................................................53.1概要设计................................................................................................................53.1.1本程序设计思路...........................................................................................53.1.2本程序包含的函数.......................................................................................53.2详细设计...............................................................................................................53.2.1节点类型和指针类型....................................................................................53.2.2迷宫的操作...................................................................................................53.2.3输出结果........................................................................................................74调试与分析................................................................................................................84.1调试分析...............................................................................................................84.2测试结果.............................................................................................................84.2.1当输入的行列数超过预设范围....................................................................84.2.2当输入的行列数未超过预设范围................................................................9参考文献........................................................................................................................10附录（关键部分程序清单）...................................................................................11沈阳航空工业学院课程设计报告21课程设计介绍1.1课程设计内容编写算法能够生成迷宫，并求解迷宫的路径（求解出任意一条到出口的路径即可）。迷宫有上下左右四个方向的走法。1.2课程设计要求1．不必演示求解过程，只需输出迷宫求解的路径。2．参考相应的资料，独立完成课程设计任务。3．交规范课程设计报告和软件代码。2课程设计原理2.1课设题目粗略分析2.1.1迷宫的建立迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述，2.1.2迷宫的存储迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。其中M，N分别表示迷宫最大行、列数，本程序M、N的最大值为39、39，当然，也可根据需要调整其大小。2.1.3迷宫路径的搜索首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路沈阳航空工业学院课程设计报告3径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。根据这种算法可以找到路径。2.2原理图介绍2.2.1功能模块图图2.2.1功能模块图如图2.2.1所示，功能模块图。2.2.2流程图分析生成迷宫将迷宫打印成图形打印迷宫路径入队出队判断队列是否为空访问节点搜索迷宫路径沈阳航空工业学院课程设计报告4图2.2.2迷宫路径算法流程图如图2.2.2所示,迷宫路径算法流程图。开始将（0,0）入队列判断首结点是否为通路判断队列是否为空？是否将队头出队是否到达迷宫出口上下左右是否存在通路是存储结点，将结点入队列解出迷宫，并给出路径否迷宫无解结束是否是沈阳航空工业学院课程设计报告53数据结构分析3.1概要设计3.1.1本程序设计思路(1)构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵(2)生成迷宫，即为二维数组maze[M+2][N+2]赋值(3)构建一个队列用于存储迷宫路径(4)建立迷宫节点structpoint,用于存储迷宫中每个节点的访问情况(5)实现搜索算法(6)屏幕上显示操作过程3.1.2本程序包含的函数(1)主函数main()(2)生成迷宫函数s_maze()(3)将迷宫打印成图形print_maze()(4)打印迷宫路径(若存在路径)result_maze()(5)入队enqueue()(6)出队dequeue()(7)判断队列是否为空is_empty()(8)访问节点visit()(9)搜索迷宫路径mazepath()3.2详细设计3.2.1节点类型和指针类型迷宫矩阵类型：intmaze[M+2][N+2];为方便操作使其为全局变量迷宫中节点类型及队列类型：structpoint{introw,col,predecessor}queue[512]3.2.2迷宫的操作(1)生成迷宫voids_maze(intm,intn){定义i,j为循环变量沈阳航空工业学院课程设计报告6for(i=m)for(j=n)输入maze[i][j]的值}(2)打印迷宫图形voidprint_maze(intm,intn){用i,j循环变量，将maze[i][j]输出□、■}(3)打印迷宫路径voidresult_maze(intm,intn){用i,j循环变量，将maze[i][j]输出□、■、☆}(4)搜索迷宫路径①迷宫中队列入队操作voidenqueue(structpointp){将p放入队尾，tail++}②迷宫中队列出队操作structpointdequeue(structpointp){head++,返回que[head-1]}③判断队列是否为空intis_empty(){返回head==tail的值，当队列为空时，返回0}④访问迷宫矩阵中节点voidvisit(introw,intcol,intmaze[41][41]){建立新的队列节点visit_point,将其值分别赋为row,col,head-1,maze[row][col]=2,表示该节点以被访问过;调用enqueue(visit_point),将该节点入队}⑤路径求解voidmazepath(intmaze[41][41],intm,intn){先定义入