数据结构课程设计(迷宫问题)

1、课 程 设 计 报 告课程名称 数据结构课程设计 课题名称 迷宫问题 专 业 班 级 学 号 姓 名 指导教师 2012年 6月 9日课程设计任务书课程名称 数据结构课程设计 课 题 迷宫问题 专业班级 学生姓名 学 号 指导老师 审 批 任务书下达日期： 2012年 6月 9日任务完成日期： 2012年 6月 16日22一、设计内容与设计要求1设计内容：1）问题描述以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。2）基本要求a.实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。

2、求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。b.编写递归形式的算法，求得迷宫中所有可能的通路。3）测试数据迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。0010001000100010000011010111001000010000010001010111100111000101110000004）实现提示计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则，沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到

3、达出口，则设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2设计要求：l 课程设计报告规范1)需求分析a.程序的功能。b.输入输出的要求。2)概要设计a. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计a.采用c语言定义相关的数据类型。b.写出各模块的类c码算法。c.画出各函数的调用关系图、主要函

4、数的流程图。4)调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式见附带说明。7)附录a.参考书目b.源程序清单（带注释）l 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： 平时出勤 （占10%） 系

5、统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） 设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 独立完成情况（占10%）。l 课程验收要求 运行所设计的系统。 回答有关问题。 提交课程设计报告纸质稿。 提交源程序、设计报告文档电子稿。 依内容的创新程度，完善程序情况及对程序讲解情况打分。二、进度安排附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（a4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距

6、为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。 目录一、 任务书2二、 基本算法7三、 需求分析7a. 程序的功能7b. 输入输出的要求7c. 程序算法分析8四、 概要设计8i. 设计中非递归程序的模块结构图8ii. 程序的数据结构和数据库结构分析9iii. 试探方向的设计10iv. 达某点，以避免发生死循环11五、 详细设计11a. 伪码设计11b. mgpath（）流程图1

7、2六、 调试分析13七、 总结14八、 评分表16九、 附录（源代码清单）17一、基本算法走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西南、西、西北、北、东北8个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果8个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在

8、位置（m,m）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的边界；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；其余元素值用随机函数产生。假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有8个。如果用二维数组move记录8个方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定： x=x+movei0 y=y+movei1从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。在搜索过程中，每前进一步，在所到位置处做

9、标记“h”（表示这个位置在通路上），并将该位置的坐标压入栈中。每次后退的时候，先将当前所在位置处的通路标记“h”改成死路标记“”（表示这个位置曾到达过但走不通，以后不要重复进入），然后将该位置的坐标从栈顶弹出。搜索到出口位置时，数组中那些值为“h”的元素形成一条通路。二、需求分析a.程序的功能。(i) 实现一个以链表作存储结构的栈类型，以非递归算法求取所有通路和最短路径(ii)以一个递归算法，对任意输入的迷宫矩阵（1代表不通，0代表通路）求出所有通路 b.输入输出的要求。(i) 求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。（ii

10、）输出迷宫示意图c、程序算法分析1.迷宫的建立：迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述，2.迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组mazem+2n+2,然后用它的前m行n列来存放元素，即可得到一个mn的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。注：其中m，n分别表示迷宫最大行、列数，本程序m、n的缺省值为39、39，当然，用户也可根据需要，调整其大小。3.迷宫

11、路径的搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个栈中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。三、概要设计i）设计中非递归程序的模块结构图图中方框表示函数，方框中指出函数

12、名，箭头方向表示函数间的调用关系，虚线方框表示文件的组成main（）mapath（）mgpath（）：求解迷宫问题，即输出从（1，1）到（m，n）的全部路径和最短路径（包含最短路径长度）。当找到一条路径时，不使用return语句退出，而是出栈一次，重新回溯走另一条路径，并用minlen记录最短路径长度，path数组记录最短路径。ii）程序的数据结构和数据库结构分析设迷宫为m行n列，利用mazemn来表示一个迷宫，mazeij=0或1; 其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化我们用mazem+

13、2n+2来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。如图3.4表示的迷宫是一个68的迷宫。入口坐标为（1，1），出口坐标为（m，n）。入口(1,1) 012345678n90111111111111011101111210010111113100000001141001101111511000100016101100010171111111111m 出口 (6,8) 图1 用mazem+2n+2表示的迷宫迷宫的定义如下：#define m 6 /* 迷宫的实际行 */#define

14、 n 8 /* 迷宫的实际列 */int maze m+2n+2 ;iii试探方向的设计 示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图2所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move 4 中，在move 数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。move数组如图3所示。move数组定义如下：type

15、def struct int x ; /行int y ; /列 item ; item move4 ;这样对move的设计会很方便地求出从某点 (x，y) 按某一方向 v (0v3) 到达的新点（i，j）的坐标：i =x + movev.x ，j = y + movev.y 。(x，y)图2 与点(x，y)相邻的4个点及坐标(x，y+1)(x，y-1)(x+1，y)(x-1，y)xy00111020-13-10图3 增量数组moveiii、栈的设计当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方

16、向，即每走一步栈中记下的内容为(行，列，来的方向)。对于图1所示迷宫，依次入栈为：top 3,4,0 3,3,0 3,2,1 2,2,0 2,1,1 1,1,0栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3迷宫，走的路线为：(1,1)0(2,1)1(2,2)0(3,2)1(3,3)0(3,4)0（下脚标表示方向），当无路可走，则应回溯，对应的操作是出栈，沿下一个方向即方向继续试探。栈中元素是一个由行、列、方向组成的三元组，栈元素的设计如下：typedef structint x , y , d ;/* 横纵坐标及方向*/datatype ;栈的定义为： seqstack

17、 s ;iv、达某点，以避免发生死循环：一种方法是另外设置一个标志数组markmn，它的所有元素都初始化为0，一旦到达了某一点 ( i , j )之后，使mark i j 置1，下次再试探这个位置时就不能再走了。另一种方法是当到达某点（i , j）后使maze i j 置 -1，以便区别未到达过的点，同样也能起到防止走重复点的目的，此处采用后一方法，算法结束前可恢复原迷宫。四、详细设计a.伪码设计(1) 栈初始化;(2) 将入口点坐标及到达该点的方向（设为-1）入栈(3) while (栈不空) 栈顶元素（x , y , d）出栈 ;求出下一个要试探的方向d+ ; while （还有剩余试探方

18、向时） if （d方向可走）则 （x , y , d）入栈 ; 求新点坐标 (i, j ) ;将新点（i , j）切换为当前点（x , y） ; if ( (x ,)= =(,n) ) 结束 ; else 重置 d=0 ; else d+ ; 算法如下： int path(int &maze，int m, int n, int move) /m,n为 maze的一、二维长度，move为结构体数组存放了试探的4个方向坐标 seqstack s ; datetype temp ; int x, y, d, i, j ; temp.x=1 ; temp.y=1 ; temp.d=-1 ; push_

19、seqstack (s，temp) ;阿 while (! empty_seqstack (s ) ) pop_seqstack (s,temp) ;x=temp.x ; y=temp.y ; d=temp.d+1 ;while (d4) i=x+moved.x ; j=y+moved.y ;if ( mazeij= =0 ) temp=x, y, d ;push_seqstack ( s, temp ) ;x=i ; y=j ; mazexy= -1 ;if (x= =m&y= =n) return 1 ; /*迷宫有路*/else d=0 ; else d+ ; /*while (d4)*

20、/ /*while (! empty_seqstack (s ) )*/ return 0 ;/*迷宫无路*/ 栈中保存的就是一条迷宫的通路。bmgpath（）流程图开始栈不为空比较输出最短路径回溯无路可走输出路径让该结点不可走找到下一个可走结点是否找到出口五、调试分析a、迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。001000100010001000001101011100100001000001000101011110011100010111000000b、 程序调试截图i) 递归算法程序求所有路径，预设测试迷宫，输出迷宫图黑色方块代表墙壁ii) 运行程序得出所有通

21、路，以图的方式输出，圆圈代表路径（程序截图如右）iii）输入上表给出的测试矩阵，运行源代码清单1，以三元组输出所有通路，及最短路径，程序运行截图（如上）六、总结经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是翻阅资料。在此期间我失落过，也曾一度热情高涨。点点滴滴令我回味无长。这次课程设计使我体会到只有做到细心耐心，恒心才能做好事情。这次的课程设计，加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、

22、编程调试，掌握应用软件的分析方法和工程设计方法。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。而且做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解了。而且还可以记住很多东西。认识来源于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准。所以这个期末测试之后的课程设计对我们的作用是非常大的。这次的课程设计使我懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能

23、力。在整个设计过程中，构思是很花费时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多也时用错了方法，总是实现不了。同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。每个实

24、验通常都要花费很久的时间才能理清一个程序的思路，而且要不断的调试程序才能把程序调试正确，同时还要做到界面的输出也是需要美化的。这次课程设计终于顺利完成了，在设计中遇到了很多专业知识问题，最后在老师的辛勤指导下，也完成了课程设计。通过这次的课程设计，让我更加了解到数据结构的重要性。以及它对我们专业的发展发挥的作用。对我们而言，知识上的收获很重要，但精神上的丰收更加可喜。让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆！同时在做课程设计时要能够从多

25、方面去考虑，去研究，用多种算法去实现要求。此次课程设计，学到了很多课内学不到的东西，比如独立思考解决问题，出现差错的随机应变，这些都让我受益非浅，今后的制作应该能够更轻松，自己也都能够解决并高质量的完成项目。评分表理学院课程设计评分表课题名称： 迷宫问题 项 目评 价设计方案的合理性与创造性设计与调试结果设计说明书的质量答辩陈述与回答问题情况课程设计周表现情况综合成绩 教师签名： 日 期： 附录a、参考书目1、数据结构教程（第3版）李春葆 尹为民 编著 清华大学出版社出版2、数据结构教程（第三版）上级实验指导李春葆 尹为民 编著 清华大学出版社出版3、数据结构（学习指导、实验指导、课程设计）

26、陈媛 编著 机械工业出版社出版b、源程序清单（带注释）i）非递归算法求迷宫源程序/* 实现一个以链表作存储结构的栈类型，然后编写 * 一个求解迷宫的非递归程序。求得的通路以三元组 * （i，j，d）的形式输出，其中：（i，j）指示迷宫中 * 的一个坐标，d表示走到下一个坐标的方向。 */#include #include #define m 9 /行数#define n 8/列数#define maxsize 100/栈最多元素个数int mgm+2n+2 = /迷宫测试数据矩阵,左上角（1,1）为入口，右下角（9,8）为出口1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,

27、1,0,1,1,0,1,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;struct int i;int j;int di; stackmaxsize,pathmaxsize;/定义栈和存放最短路径的数组int top=-1;/栈顶指针int count=1;/路径数计数int minlen=max

28、size;/最短路径长度void mgpath()/路径为:(1,1)-(m,n)int i,j,di,find,k;top+;/进栈stacktop.i=1;stacktop.j=1;stacktop.di=-1;mg11=-1;/初始结点进栈while (top-1)/栈不空时循环i=stacktop.i;j=stacktop.j;di=stacktop.di;if (i=m & j=n)/找到了出口,输出路径 printf(%4d: ,count+);for (k=0;k=top;k+) /以三元组输出路径printf(%d,%d,%d) ,stackk.i,stackk.j,stack

29、k.di);if (k+1)%5=0) printf(nt);/输出时每5个结点换一行printf(n);if (top+1minlen)/比较找最短路径for (k=0;k=top;k+)pathk=stackk;minlen=top+1;mgstacktop.istacktop.j=0;/让该位置变为其他路径可走结点top-; i=stacktop.i;j=stacktop.j;di=stacktop.di;find=0;while (di4 & find=0)/找下一个可走结点di+;switch(di)case 0:i=stacktop.i-1;j=stacktop.j;break;c

30、ase 1:i=stacktop.i;j=stacktop.j+1;break;case 2:i=stacktop.i+1;j=stacktop.j;break;case 3:i=stacktop.i,j=stacktop.j-1;break;if (mgij=0) find=1;if (find=1)/找到了下一个可走结点stacktop.di=di;/修改原栈顶元素的di值top+;stacktop.i=i;stacktop.j=j;stacktop.di=-1;/下一个可走结点进栈mgij=-1;/避免重复走到该结点else/没有路径可走,则退栈mgstacktop.istacktop.

31、j=0; /让该位置变为其他路径可走结点top-;printf(最短路径如下:n);printf(长度: %dn,minlen);printf(路径: );for (k=0;kminlen;k+)switch(pathk.di)case 0:printf(%d,%d,%s) ,pathk.i,pathk.j,);break;case 1:printf(%d,%d,%s) ,pathk.i,pathk.j,);break;case 2:printf(%d,%d,%s) ,pathk.i,pathk.j,);break;case 3:printf(%d,%d,%s) ,pathk.i,pathk.j,);break;case-1: printf(%d,%d,%s