数据结构课程设计报告-迷宫问题.docx

《数据结构课程设计报告-迷宫问题.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构课程设计报告题目迷宫问题作者张娇院系信息工程学院专业信息管理与信息系统学号指导老师李赵兴答辩时间2015-12-19目录1系统需求分析-2-1.1问题描述-2-1.1.1来源-2-1.1.2基本表示-2-1.1.3所用到的主要知识点-3-1.2基本要求-3-1.2.1要求设计程序输出如下：-3-1.2.1基本输入要求-3-1.2.3程序主要部分及所能达到的功能-3-小结-3-2系统设计（或总体设计）-5-2.1系统分析：-5-2.1.1迷宫的建立：-5-2.1.2迷宫的存储：-5-2.1.3迷宫路径的搜索：-6-2.2概要设计-7-2.2.1.步骤介绍-7-2.2.2本程序包含1

2、0个函数：-8-小结-9-3系统实现（或详细设计）-10-3.1数据类型-10-3.1.1节点类型和指针类型-10-3.2迷宫的具体操作-10-3.2.1手动生成迷宫-10-3.2.2自动生成迷宫-10-3.2.3打印迷宫图形-11-3.2.4打印迷宫路径-11-3.2.5搜索迷宫路径-11-3.3菜单选择-12-小结-13-4系统测试-14-4.1运行界面-14-4.2手动输入迷宫-14-4.3自动输入迷宫-16-4.4数据提示-18-小结-19-5总结-20-1系统需求分析　需求分析即需求加分析，是信息系统开发过程中至关的一步，也是关键性的一步，在该部分中根据设计题目的要求，充分地分

3、析和理解问题，叙述系统的功能要求，明确问题要求做什么，以及限制条件是什么，包括问题描述和基本要求。1.1问题描述1.1.1来源迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。图（1-1-1）例图1.1.2基本表示1用二维数

4、组表示迷宫，先定义一个较大的二维数maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。2节点类型和指针类型（1）迷宫矩阵类型：intmaze[M+2][N+2];为方便操作使其为全局变量（2）迷宫中节点类型及队列类型：structpoint{introw,col,predecessor}queue[512]1.1.3所用到的主要知识点队列（保存当前位置）、二维数组（存放迷宫内的数据即0和1）、广度优先遍历的算法（找到路径，且为最短路径）1.2基本要求1.2.1要求设计程序输出如下：

5、1建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；2找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。3用一种标志（如☆）在迷宫中标出该条通路；4在屏幕上输出迷宫和通路；5上述功能可用菜单选择。1.2.1基本输入要求1首先根据用户需要选择自动生成迷宫，或手动生成迷宫2根据提示要求，输入迷宫的行数和列数，且输入数据为整型1.2.3程序主要部分1迷宫的建立2迷宫的存储3迷宫路径的搜索4探索通路，有则在屏幕上输出迷宫和通路，否则，输出迷宫并提示无通路小结通过系统需求分析这一部分的进展，使得自己对课程设计任务书又有了更深的理解，

6、对迷宫问题求解步骤有了详细的思路，让我对自己所研究的迷宫求解问题脑海里有了大致的轮廓。该问题设计系统界面要求简单大方，易于操作；系统需要实现用户选择的界面，使得系统功能更加完善。2系统设计（或总体设计）说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。2.1系统分析：设计流程如图2-1：图（2-1）设计流程图2.1.1迷宫的建立：迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。2.1.2迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定

7、，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。注：其中M，N分别表示迷宫最大行、列数，本程序M、N的缺省值为39、39，当然，用户也可根据需要，调整其大小。2.1.3迷宫路径的搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜