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

1、课 程 设 计 报 告课程名称数据结构课程设计课题名称迷宫问题专业计算机科学与技术班级计科 4 班学号2013026674 姓名李梦宇指导教师2012 年 6 月 9 日一 、 设 计 内 容 与 设 计 要 求1设计内容：1）问题描述以一个 m*n 的长方阵表示迷宫， 0和 1 分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。2）基本要求链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（ i，j，d）的形式输出，其中： （i，j）指示迷宫中的一个坐标，d 表示走到下一个坐标的方向。式的算法，求得迷宫中所

2、有可能的通路。3）测试数据迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 4）实现提示计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则，沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达

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

4、试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。遇到的问题以及解决问题的方法。程经验教训、心得体会。5) 使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6) 书写格式见附带说明。7) 附录（带注释）目录一、任务书2 二、基本算法7 三、需求分析7 a. 程序的功能7 b. 输入输出的要求7 c. 程序算法分析8 四、概要设计8 i.设计中非递归程序的模块结构图8 ii.程序的数据结构和数据库结构分析9 iii. 试探方向的设计10 iv.达某点，以避免发生死循环11 五、详细设计11 a. 伪码设计11 b. mgpath（）流程图12 六、调

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

6、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 从迷宫的入口位置开始，沿图示方向顺序依次进

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

8、 表示走到下一个坐标的方向。（ii ）输出迷宫示意图c、程序算法分析：67851432x y o 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0 表示通路，用 1 表示障碍，这样迷宫就可以用0、1 矩阵来描述，：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组mazem+2n+2, 然后用它的前 m行 n 列来存放元素，即可得到一个m n 的二维数组，这样 (0,0) 表示迷宫入口位置， (m-1,n-1)表示迷宫出口位置。注：其中 m ，n分别表示迷宫最大行、 列数，本程序 m

9、 、n的缺省值为 39、39，当然，用户也可根据需要，调整其大小。搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置， 并从它开始搜索路径。 为防止搜索重复出现， 则将已搜索过的位置标记为 2，同时保留搜索痕迹， 在考虑进入下一个位置搜索之前，将当前位置保存在一个栈中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。三、概

10、要设计i ）设计中非递归程序的模块结构图图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系，虚线方框表示文件的组成main（）mapath （）mgpath（） ：求解迷宫问题，即输出从（1，1）到（ m ，n ）的全部路径和最短路径（包含最短路径长度）。当找到一条路径时，不使用return语句退出，而是出栈一次，重新回溯走另一条路径，并用minlen 记录最短路径长度， path 数组记录最短路径。ii ）程序的数据结构和数据库结构分析设迷宫为 m 行 n 列，利用 mazemn 来表示一个迷宫， mazeij=0或 1; 其中：0 表示通路， 1 表示不通，当从某点向下试探时

11、，中间点有4个方向可以试探，（见图）而四个角点有 2 个方向， 其它边缘点有 3个方向， 为使问题简单化我们用 mazem+2n+2来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为 4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。如图 3.4 表示的迷宫是一个68的迷宫。入口坐标为（1，1） ，出口坐标为 （m ，n） 。入口(1,1) 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 2 1 0 0 1 0 1 1 1 1 1 3 1 0 0 0 0 0

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

13、此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用 0，1，2，3 表示东、南、西、北）的坐标增量放在一个结构数组move 4 中，在 move 数组中，每个元素有两个域组成，x：横坐标增量， y：纵坐标增量。 move数组如图 3 所示。move数组定义如下：typedef struct int x ; /行int y ; /列m n item ; item move4 ; 这样对 move的设计会很方便地求出从某点 ( x，y) 按某一方向 v (0 v3) 到达的新点（ i ，j ）的坐标： i

14、 =x + movev.x ，j = y + movev. y 。iii、栈的设计当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为( 行，列，来的方向 ) 。对于图 1 所示迷宫，依次入栈为：栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3 迷宫，走的路线为：(1,1)0(2,1)1(2,2)0(3,2)1(3,3)0(3,4)0（下脚标表示方向），当无路可走，则应回溯，对应的操作是出栈，沿下一个方向即方向继续试探。栈中元素是一个由行、列、方向

15、组成的三元组，栈元素的设计如下：typedef struct int x , y , d ;/* 横纵坐标及方向 */ datatype ; x y 0 0 1 1 1 0 2 0 -1 3 -1 0 top 3,4,0 3,3,0 3,2,1 2,2,0 2,1,1 1,1,0 (x ，图 2 与点 (x，y)相邻的 4 个点及坐标(x，y+1) (x， y-1) (x+1，y) (x-1 ，图 3 增量数组 move 栈的定义为： seqstack s ; iv 、达某点，以避免发生死循环：一种方法是另外设置一个标志数组markmn ，它的所有元素都初始化为0，一旦到达了某一点 ( i ,

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

17、 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_seqstack (s，temp) ; 阿 while (! empty_seqstack

18、(s ) ) pop_seqstack (s,temp) ; ; ; 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)*/ /*while (! empty_seqstack (s ) )*/ return 0 ;/*迷宫

19、无路 */ 栈中保存的就是一条迷宫的通路。bmgpath（）流程图开始栈不为空是否找到出口让该结点不可走找 到 下 一 个 可走结点无路可走回溯输出路径比较输出最短路径五、调试分析a、迷宫的测试数据如下：左上角（1,1 ）为入口，右下角（ 8,9 ）为出口。0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 b、 程序调试截图i)递归算法程序求所有路径，预设测试

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

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

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

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

24、我人生旅途上一个非常美好的回忆！同时在做课程设计时要能够从多方面去考虑，去研究，用多种算法去实现要求。此次课程设计，学到了很多课内学不到的东西，比如独立思考解决问题，出现差错的随机应变，这些都让我受益非浅，今后的制作应该能够更轻松，自己也都能够解决并高质量的完成项目。附录a、参考书目1、 数据结构教程（第3 版） 李春葆尹为民编著清华大学出版社出版2、 数据结构教程（第三版）上级实验指导李春葆尹为民编著清华大学出版社出版3、 数据结构（学习指导、实验指导、课程设计） 陈媛编著机械工业出版社出版b、源程序清单（带注释）i）非递归算法求迷宫源程序/* 实现一个以链表作存储结构的栈类型，然后编写*

25、一个求解迷宫的非递归程序。求得的通路以三元组* （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,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,

26、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=maxsize; /最短路径长度void mgpath() /路径为 :(1,1)-(m,n) in

27、t 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,stackk.di); if (k+1)%5=0) printf(

28、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; case 1:

29、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.ist

30、acktop.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) ,pathk.i,pathk.j, 终点);break; if (k+1)%5=0) printf(nt); /输出时每 5个结点换一行 print