课程设计报告课程名称数据结构课程设计课题名称迷宫问题专业班级学号姓名指导教师2012年6月9日课程设计任务书课程名称数据结构课程设计课题迷宫问题专业班级学生姓名学号指导老师审批任务书下达日期：2012年6月9日任务完成日期：2012年6月16日一、设计内容与设计要求1．设计内容：1）问题描述以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。

设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。

2）基本要求a.实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。

求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。

b.编写递归形式的算法，求得迷宫中所有可能的通路。

3）测试数据迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。

4计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则，沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。

假如所有可能的通路都探索到而未能到达出口，则设定的迷宫没有通路。

可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m，n）。

为处理方便起见，可在迷宫的四周加一圈障碍。

对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

2．设计要求：●课程设计报告规范1)需求分析a.程序的功能。

b.输入输出的要求。

2)概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。

3)详细设计a.采用C语言定义相关的数据类型。

b.写出各模块的类C码算法。

c.画出各函数的调用关系图、主要函数的流程图。

4)调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。

b.程序调试中遇到的问题以及解决问题的方法。

c.课程设计过程经验教训、心得体会。

5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。

6)书写格式见附带说明。

7)附录a.参考书目b.源程序清单（带注释）●考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。

具体考核标准包含以下几个部分：①平时出勤（占10%）②系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）③程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）④设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。

⑤独立完成情况（占10%）。

课程验收要求①运行所设计的系统。

②回答有关问题。

③提交课程设计报告纸质稿。

④提交源程序、设计报告文档电子稿。

⑤依内容的创新程度，完善程序情况及对程序讲解情况打分。

二、进度安排附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。

正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。

正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。

正文总字数要求在5000字以上（不含程序原代码）。

目录一、任务书 (2)二、基本算法 (7)三、需求分析 (7)a.程序的功能 (7)b.输入输出的要求 (7)c.程序算法分析 (8)四、概要设计 (8)i.设计中非递归程序的模块结构图 (8)ii.程序的数据结构和数据库结构分析 (9)iii.试探方向的设计 (10)iv.达某点，以避免发生死循环 (11)五、详细设计 (11)a.伪码设计 (11)b.mgpath（）流程图 (12)六、调试分析 (13)七、总结 (14)八、评分表 (16)九、附录（源代码清单） (17)一、基本算法走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西南、西、西北、北、东北8个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果8个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。

每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。

用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。

迷宫的入口点在位置（1，1）处，出口点在位置（m,m ）处。

设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。

二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的边界；第1行第1列元素和第m 行第m 列元素置成“0”， 表示迷宫的入口和出口；其余元素值用随机函数产生。

假设当前所在位置是（x,y ）。

沿某个方向前进一步，它可能到达的位置最多有8个。

如果用二维数组move 记录8个方向上行下标增量和列下标增量，则沿第i 个方向前进一步，可能到达的新位置坐标可利用move 数组确定： x=x+move[i][0] y=y+move[i][1] 从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。

在搜索过程中，每前进一步，在所到位置处做标记“”（表示这个位置在通路上）每次后退的时候，先将当前所在位置处的通路标记“”改 成死路标记“×” 不要重复进入），然后将该位置的坐标从栈顶弹出。

搜索到出口位置时，数组中那些值为“”的元素形成一条通路。

二、需求分析a.程序的功能。

(i) 实现一个以链表作存储结构的栈类型，以非递归算法求取所有通路和最短路径(ii)以一个递归算法，对任意输入的迷宫矩阵（1代表不通，0代表通路）求出所有通路b.输入输出的要求。

(i) 求得的通路以三元组（i ，j ，d ）的形式输出，其中：（i ，j ）指示迷宫中的一个坐标，d 表示走到下一个坐标的方向。

（ii ）输出迷宫示意图c 、程序算法分析1.迷宫的建立：6 7 8 5 1 4 3 2 x y o迷宫中存在通路和障碍，为了方便迷宫的创建，可用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，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个栈中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。

这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。

三、概要设计i）设计中非递归程序的模块结构图图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系，虚线方框表示文件的组成mgpath（）：求解迷宫问题，即输出从（1，1）到（M，N）的全部路径和最短路径（包含最短路径长度）。

当找到一条路径时，不使用return语句退出，而是出栈一次，重新回溯走另一条路径，并用minlen记录最短路径长度，Path数组记录最短路径。

ii）程序的数据结构和数据库结构分析设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1; 其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。

这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。

如图3.4表示的迷宫是一个6×8的迷宫。

入口坐标为（1，1），出口坐标为（m，n）。

入口(1,1)出口 (6,8)迷宫的定义如下：#define m 6 /* 迷宫的实际行 */#define n 8 /* 迷宫的实际列 */int maze [m+2][n+2] ;iii．试探方向的设计示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图2所示。

因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。

为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move [ 4 ]中，在move 数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。

Move数组如图3所示。

move数组定义如下：typedef struct {int x ; //行int y ; //列} item ;item move[4] ;这样对move 的设计会很方便地求出从某点 (x ，y ) 按某一方向 v (0≤v ≤3) 到达的新点（i ，j ）的坐标：i =x + move[v].x ，j = y + move[v].y 。

iii 、栈的设计当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。

因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。

对于图1所示迷宫，依次入栈为：栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3迷宫，走的路线为：(1,1)0→(2,1)1→(2,2)0→(3,2)1→(3,3)0→(3,4)0（下脚标表示方向），当无路可走，则应回溯，对应的操作是出栈，沿下一个方向即方向继续试探。