090620208[雷青青]迷宫问题

1、 西安建筑科技大学课程设计（论文） 课程设计（论文）课程名称： 数据结构程序设计 题 目： 迷宫问题 院 （系）： 信息与控制工程学院 专业班级： 计算机902 姓 名： 雷青青 学 号： 090620208 指导教师： 李智杰 2011 年 9 月 9 日第 20 页 共20 页西安建筑科技大学课程设计（论文）任务书专业班级： 计算机0902 学生姓名： 雷青青 指导教师（签名）： 一、课程设计（论文）题目问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。二、本次课程设计（论文）应达到的

2、目的数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。本题目要达到目的：熟练掌握数组、链表的应用。 三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等） 基本要求（1） 实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。（2）编写递归形式的算法，求得迷

3、宫中所有可能的通路；（3）以方阵形式输出迷宫及其通路。四、应收集的资料及主要参考文献： 由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经上机练习了“数组、线性表”及其有关的基本操作。 参考文献：1本年级用的教材：数据结构与算法分析（C+版）（第二版）影印版 2005，7；2C+程序设计技能百练，中国铁道出版社，2004，1 蒋立翔编著；3. 数据结构与C+，西安交通大学出版社，1999，11 周叶著；4C/C+与数据结构，清华大学出版社，2002，3，1 王立柱；5数据结构使用C+语言描述，东南大学出版社，2001，1，1 陈慧南；五、审核批准意见教研室主任（签字） 设计总

4、说明迷宫问题是典型的简单小游戏，本系统采用Visual C+6.0为开发工具，迷宫问题的求解是一个很好的在栈或者队列等方面的应用问题，本次设计是以栈去实现的。问题的求解主要是给定一个入口坐标和出口坐标时求出一条从入口到出口的路径，如果不存在或存在要做出相应的判断，存在时打印其路径，并做动态演示。随着科学技术的不断提高,计算机科学日渐成熟，其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用。作为计算机应用的一部分,使用计算机对小游戏的开发与求解方法,成为不可缺少的一部分，计算机的的各种小游戏，在游戏世界中越来越流行。虽然迷宫游戏简单常见。但是他的方法，经典并且它是一

5、些网络游戏的基础。只有从小的从基础的开始一步一步迈向更加复杂化的程序，我们才能从中不断学习，使我们的编程能力不断加强。 由于计算机解迷宫时，通常用的是群举的方法，即从入口出发，顺某一方向搜索。若能走通，则继续往前走；否则沿原路退回，换一个方向再继续搜索，直至所有可能的通路都搜索完为止。为了保证在任何位置上都能沿原路返回，这就需要一个后进先出的结构来存储起位置，所以用到了栈的概念。迷宫问题相对来说就是他的求解问题，其次是他的显示问题，其中用到的各种算法与文件，所产生不同迷宫。相对我所做的迷宫程序来说，比较简单，但是他清楚，明晰的知名迷宫的各种功。因此，在下面的各章中将以开发这一套小游戏为例,谈谈

6、其开发过程和所涉及到的问题及解决方法。 目录一 绪论················1二 系统需求分析············1三 概要设计··············2四 详细设

7、计··············5五 总结················11六 致谢················14七 参考文献

8、3;·············14八 源程序代码·············15数据结构课程设计 迷宫问题一、 绪论1.1课程设计选题的目的数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作

9、者工作作风的训练，将起到显著的促进作用。1.2课题研究的主要内容要求完成构造迷宫，输入入口出口，输出迷宫路径。功能要求如下：1构建迷宫：可以系统构建，也可以用户自己构建，输入1为不通，输入0为通路。显示构建好的迷宫。2输出路径：输入入口与出口，利用编好的函数对迷宫进行试探，有路径输出路径，无路径提示用户此迷宫无出口。3最短路径：输出走出此迷宫的最短路径，即不用走回头路的一条路径。4要求系统有一定的容错性，给用户必要的提示。二、 系统需求分析2.1输入/输出形式迷宫中建立数组时，首先输入迷宫的行数和列数。边围规定为1，在程序中已赋值，内围用0、1输入，不用其他的数字，若输入错误会提示重新输入；然

10、后选择系统创建的迷宫还是自己创建迷宫，输入选项1或2（输入其他选项按2处理）；迷宫创建好后，输入入口和出口坐标（入口必须为通路即0，否则系统会报错，重新输入），找到路径或无路径；接下来会提示寻找其他路径还是退出此迷宫，输入1或2进行选择；选择1，则继续输入迷宫入口和出口，选择2或其他，则退出。若还想创建别的迷宫就在接下来输入y或Y，输入其他则退出程序。2.2程序功能在迷宫问题中，可由操作者自己设定迷宫大小，迷宫内部构造有两个选择，系统设计，节省时间，也可由操作者自己设计，迷宫入口和出口并能保证入口为通路，若有路径会显示其路径并显示最短路径。一个迷宫有不同入口和出口，可寻求多条路径。三、 概要设

11、计3.1设计思想迷宫中用回溯法从八个方向向前试探，用队列保存探测到的通路，建立一个数组模拟迷宫，将各个函数结合在一起。 走迷宫游戏 主程序退出系统选择用户自定义迷宫输出最短路径恢复迷宫输出整个路径判断每一步所走路径输出迷宫图31 迷宫系统结构图3.2实现方法迷宫中定义move数组，从东顺时针探测；进队出队完成探测；自己创建maze数组，并输入入口点和出口点，再进行计算。3.3函数间的关系创建迷宫输入进口和出口输出最短路径输出路径开始恢复迷宫判断退出此迷宫判断结束图32 函数流程图四、 详细设计4.1实现定义的数据类型（1）迷宫数组定义为结构体包含两个整型数据，迷宫出口和入口的值定义为整型。ty

12、pedef structint x,y;item;typedef structint x,y,d;（2）迷宫内部的设计时各坐标点设置成栈内整型。typedef stack<Datetype> stack_int;（3）迷宫中求路径和最短路径时定义结构体类型表示队列，包含整型坐标点，和整型下标；又有整型的队首尾指针。typedef structint x,y;int pre; SqType; ；int front,rear;（4）迷宫路径和最短路径输出时，遵循栈的规则，即先进后出。int path1(int *maze,int m,int n,int c,int d,int x1,i

13、nt y1)4.2实现定义操作伪代码算法迷宫的操作1.手动生成迷宫cout<<"请输入迷宫："<<m<<"行"<<n<<"列"<<", 输入必须为'0' 或 '1'；"<<endl;for(i=1;i<=m;i+) /输入第i行迷宫的构造；for(j=1;j<=n;j+) /输入第j列迷宫的结构；cin>>mazeij;A:if(mazeij!=0 && maz

14、eij!=1)cout<<"请再次输入："cin>>mazeij;goto A; /判错；cout<<"迷宫如下："<<endl; /显示用户输入的迷宫；for(i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)H:cout<<"请输入迷宫入口(a,b),出口(c,d)："cin>>i>>j>>c>>d;void shoudong_maze(int m,int n)定义i,j为循环变量for(i<

15、=m)for(j<=n)输入mazeij的值2.自动生成迷宫if(s="1")srand(time(0); /系统时间随机函数；for(i=1;i<=m;i+)for(j=1;j<=n;j+)mazeij=rand()%2; /随机赋值maze11=0; /(1,1)点为可通过点；mazemn=0; /(m,n)点为可通过点；3.打印迷宫路径void printpath(SqType sq,int)/打印路径int i;i=rear; docout<<"("<<sqi.x<<","

16、<<sqi.y<<")<-"i=sqi.pre; /回溯；while(i!=-1);4.迷宫恢复void restore(int *maze,int m,int n)/恢复迷宫for(int i=1;i<=m;i+)for(int j=1;j<=n;j+)if(mazeij=-1)mazeij=0;5.求一般路径伪代码：while(栈不空)栈顶元素=>(x,y,d)出栈;求出下一个要试探的方向d+;while(还有剩余试探方向)if(d方向可走)(x,y,d)入栈;求新点坐标(i,j);将新点(i,j)切换成当前点(x,y);

17、if(x,y)=(m,n)结束;else重置 d=0;else d+;6.求解最短路径伪代码：(x,y)入队;while(队列不为空)队首元素出队;for(方向为0;方向<总方向数;改变方向)到达点坐标;if(此坐标点为通路)入队;if(到达出口点)输出路径;恢复迷宫;当前点搜索完，取下一点搜索;4.3调试分析在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条中的一条或不是最短路径，所以通过算法比较，改用此算法。4.4测试结果4.4.1测试数据和结果1.采用随机创建好的迷宫但没有出路图41 随机输出结果图2，采用自己输入的迷宫。图42自己创建迷宫输出图43 路径输出图图44 转换

18、出口输出路径图4.4.2算法时间复杂度：O(m²）五、 总 结5.1问题描述主要问题有：方向设置，路径存储，迷宫图的存储，路径的求解，出口入口的设置。这个迷宫问题的算法中，要在开始设置迷宫的大小。在探索迷宫路线的过程中，是通过不断的尝试来得到最终的结果，由于不能对已经设定为可走路径进行返回，所以在这个算法中有时候可能不能得到走出迷宫的路径。5.2问题分析1.迷宫的建立：迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述，并且先开始建立好迷宫周围的墙，用1表示。2.迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，然后用它的

19、前m行n列来存放元素，即可得到一个m×n或m×m的二维数组，但是他的一个点是由三个元素组成，除了行和列，还有一个指针，即前驱点的下标（），这样（x,y）,(b,d)表示迷宫的入口与出口。3.迷宫路径的搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右以及对角线四个方向位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个

20、队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。以矩阵 0 0 1 0 1 为例，来示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 首先，将位置(0,0)(序号0)放入队列中，其前节点为空，从它开始搜索，其标记变为2，由于其只有一个非障碍位置，所以接下来移动到(0,1)(序号1)，其前节点序号为0，标记变为2，然后从(0,1)移动到(1,1)(序号2)，放入队列中，其前节点序号为1，(1,1)存在(1，2)(序号3)、(2，1)(序号4)两个可移动位置，其前节点序

21、号均为2.对于每一个非障碍位置，它的相邻非障碍节点均入队列，且它们的前节点序号均为该位置的序号，所以如果存在路径，则从出口处节点的位置，逆序就可以找到其从出口到入口的通路。5.3问题的解决方案迷宫问题中，采用move数组存储方向，采用二维数组存储迷宫图，采用栈存储路径，采用队列算出最短路径，参数传递出口入口和迷宫的大小。5.4设计体会5.4.1系统的优点迷宫问题中，突出优点为采用了时间随机函数，系统自动生成迷宫，节约用户时间。此外，用两种不同的存储方式（栈和队列）对迷宫进行探究。界面清晰、通俗易懂、操作简便、结构严谨、逻辑习惯强。 5.4.2本系统的不足1.对于迷宫问题，输入迷宫内部结构时，输

22、入形式为0、1空格或回车，输入形式有误时，会使程序无法运行下去，有时还会进入死循环。输入入口坐标时，没有容错，若大于迷宫规模，程序会出错。2.迷宫的图形的构建太简单，没有达到美化效果。而且还有许多自己想到的功能并没有实现，有点遗憾。5.4.3可改进的地方（1）各个菜单界面可以设计的更为美观，更简洁易懂。（2）可以从各个方面考虑设置容错机制使程序更健壮。（3）可以想办法把所有的路径都输出来，在进行排序。（4）迷宫整个的设计太单调。5.5结束语课程设计中感受到自己知识的匮乏，需要学习的东西很多，不能总是局限于书本，在课程设计中出现问题时，应该及时与周围同学交流，多交流才能使学到的东西更深入到心里，

23、总之，这是一次不错的锻炼，专业水平不说能提高什么，但在过程中学到的学习方法应该是能受益终生的！六、 致 谢在课程设计过程中，由于自己专业基础知识的不扎实，课程设计的时间总是感觉不够，在课程设计中也遇到了很多困难，好多时候都想止步不前，但是因为我写的是迷宫，网上资源特别丰富，所以有选择性的在网上搜寻了许多相关性的知识与程序代码。从而学习到了一些有用的知识。知道了网络资源的丰富。同时因有身边的舍友与同学，给与我提意见，鼓励我，引导我，以及书本资料的查询，学会了怎么去思考，怎么去解决遇到的问题，怎么让程序运行起来，课程设计结束了，但感觉收获了很多，不仅仅是任务完成了，更让我了解到身边这群值得我珍惜的

24、朋友是多么的难得以及个人的知识能力是多么重要。这仅仅是一个小小的课程设计，以后还要面对各种各样的更大的困难与逆境，只要坚持，找到正确的方法，相信一切都会克服的。七、 参考文献1.Robert L.Kruse , Alexander J.Ryba数据结构与算法分析（C+版）（第二版）影印版M.高等教育出版社，2005.72. Mark Allen Weiss.数据结构与算法分析C+描述M.人民邮电出版社, 2006.11 3. 严蔚敏,吴伟民.数据结构C语言版M.清华大学出版社,2007.034. 周霭如,林伟健.C+程序设计基础（第三版）.电子工业出版社，2010.01 5. 朱明方,吴及.数

25、据结构教程M.机械工业出版社,2007.01 /*我真诚地保证： 我自己独立地完成了整个程序从分析、设计到编码的全过程。 如果在上述过程中，我遇到了困难而求教于人，那么，我将在程序报告中详细地列举我所遇到的问题，以及别人给我的提示。在此，我感谢老师同学对我的启发和帮助。下面的报告中，我还会具体地提到他们在各个方法对我的帮助。 我的程序里中凡是引用到其他程序或文档之处，例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,我都已经在程序的注释里很清楚地注明了引用的出处。我从未抄袭过别人的程序，也没有盗用别人的程序，无论是修改式地抄袭还是原封不动地抄袭。我编写这个程序，从来没有想过要去破坏或妨

26、碍其他计算机系统的正常运转。 <雷青青 > */ 八、 源程序代码#include<iostream>#include<stack>#include<stdio.h>#include<time.h>#include<string>using namespace std;typedef structint x,y;item;typedef structint x,y,d;Datetype;typedef stack<Datetype> stack_int;void path (int *maze,int,int,

27、int,int);void printpath();#define NUM 100 /队列大小；typedef structint x,y; /所到点的坐标；int pre; /前驱点的下标；SqType; /队列；int front,rear; /队首指针与队尾指针；void printpath(SqType sq,int) /打印路径;int i;i=rear; docout<<"("<<sqi.x<<","<<sqi.y<<")<-"i=sqi.pre; /回溯；

28、while(i!=-1);void restore(int *maze,int m,int n) /恢复迷宫for(int i=1;i<=m;i+)for(int j=1;j<=n;j+)if(mazeij=-1)mazeij=0;int path1(int *maze,int m,int n,int c,int d,int x1,int y1) /最短路径 /m,n为迷宫的长和宽，c，d为迷宫入口坐标，x1，y1为迷宫出口坐标；maze为迷宫；item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1; /坐标增量数组；SqType sqNU

29、M;int x,y,i,j,v; front=rear=0;sq0.x=c;sq0.y=d;sq0.pre=-1; if(mazecd=0) mazecd=-1; /入口点入队；else goto G;while(front<=rear) /队列不为空x=sqfront.x;y=sqfront.y;for(v=0;v<8;v+)i=x+movev.x;j=y+movev.y;if(mazeij=0)rear+;sqrear.x=i;sqrear.y=j;sqrear.pre=front;mazeij=-1; /访问过的坐标点，入队；if(i=x1&&j=y1)cou

30、t<<"最短路径为："<<endl;printpath(sq,rear); /输出路径；restore(maze,m,n); /恢复迷宫；return 1; /for v;front+; /当前点搜索完，取下一个点搜索 /whileG:cout<<"无路径。"<<endl;return 0;void path(int *maze,int a,int b,int m,int n)item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;stack_int st;Date

31、type temp;int x,y,d,i,j;if(mazeab=1)cout<<"进口输入有误。"return;temp.x=a;temp.y=b;temp.d=-1; /初始化入口点坐标及方向；st.push(temp);while(!st.empty()temp=st.top();st.pop();x=temp.x;y=temp.y;d=temp.d+1;while(d<8)i=x+moved.x;j=y+moved.y;if(mazeij=0) /该点可到达；temp.x=x;temp.y=y;temp.d=d; /坐标及方向；st.push(t

32、emp); /坐标及方向入栈； x=i;y=j;mazexy=-1; /到达新点；if(x=m && y=n)cout<<" 迷宫路径为:"<<endl;cout<<"("<<m<<","<<n<<")<-"Datetype t;while(!st.empty()t=st.top();cout<<"("<<t.x<<","<<

33、;t.y<<")<-"st.pop(); /输出路径；cout<<endl;return ; /到达出口；else d=0; /重新初始化方向；else d+; /改变方向；cout<<"对不起，无法找到出口."return; /迷宫无路；void printpath()int m,n,i,j,l,c,d;string s;cout<<" 请输入迷宫的行数列数如:(m n)"<<endl;cin>>m>>n;int *maze=new int*m

34、+2;for(i=0;i<=m+1;i+)mazei=new intn+2; /申请迷宫的空间；for(i=0;i<=m+1;i+) mazei0=1;for(i=0;i<=n+1;i+)maze0i=1;for(i=0;i<=m+1;i+)mazein+1=1;for(i=0;i<=n+1;i+)mazem+1i=1; /建立迷宫周围的墙；cout<<"1、采用创建好的迷宫; 2、自己创建迷宫（其他输入按'2'处理）"<<endl;cin>>s;if(s="1")srand(time(0); /系统时间随机函数；for(i=1;i<=m;i+)for(j=1;j<=n;j+)mazeij=rand()%2; /随机赋值maze11=0;