迷宫问题数据结构

1、摘要：本文详细介绍了迷宫问题的设计与实现，该程序具有迷宫的设计生成、逃离迷宫的路线的寻找、打印逃离路线及标拄了逃离路线的迷宫等功能。在课程设计中，程序设计语言采用Visual C+，程序运行平台为Windows 98/2000/XP。对于迷宫逃离路线的产生及打印本系统采用了栈的结构，有利于数据的存储与输出。在设计该程序时采用了挨个试探的方法，简单易懂。程序通过调试运行，实现了最初的设计目标，并且经过适当完善后，可以求出迷宫逃离路线的最短行程，在实际中可以解决更多的问题。关键词：c+；结构体；栈结构；链表目 录1需求分析12概要设计33详细设计和实现53.1软件设计几个方面：53.2功能模块设计

2、：63.3详细代码设计：83.4运行结果：164调试与操作说明16总 结17致 谢18参 考 文 献191需求分析迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。本次课程设计目的是巩固C+课程所学知识，特别加强数组，指针，结构体，栈结构的应用，熟

3、悉面向过程的结构化序设计方法，通过本次课程设计的实践，锻炼程序设计的能力以及用C+解决实际问题的能力，为以后后续课程的学习打好基础。在设计中，在Windows xp 操作系统下，利用Microsoft Visual c+语言对迷宫问题进行设计制作下面将对Microsoft Visual c+进行简要介绍：VC+是微软公司开发的一个IDE(集成开发环境),换句话说,就是使用VC+的一个开发平台.有些软件就是这个编出来的.另外还有VB,VF.只是使用不同语言.但是,VC+是Windows平台上的C+编程环境，学习VC要了解很多Windows平台的特性并且还要掌握MFC、ATL、COM等的知识，难度

4、比较大。Windows下编程需要了解Windows的消息机制以及回调（callback）函数的原理；MFC是Win32API的包装类，需要理解文档视图类的结构，窗口类的结构，消息流向等等；COM是代码共享的二进制标准，需要掌握其基本原理等等。 VC作为一个主流的开发平台一直深受编程爱好者的喜爱，但是很多人却对它的入门感到难于上青天，究其原因主要是大家对他错误的认识造成的，严格的来说VC+不是门语言，虽然它和C+之间有密切的关系,如果形象点比喻的话，可以把C+看作为一种“工业标准”，而VC+则是某种操作系统平台下的“厂商标准”,而“厂商标准”是在遵循“工业标准”的前提下扩展而来的。VC+应用程序

5、的开发主要有两种模式，一种是WIN API方式，另一种则是MFC方式，传统的WIN API开发方式比较繁琐，而MFC则是对WIN API再次封装，所以MFC相对于WIN API开发更具备效率优势，但为了对WINDOWS开发有一个较为全面细致的认识，笔者在这里还是以讲解WIN API的相关内容为主线。话说到这里可能更多人关心的是学习VC+需要具备什么条件，为什么对于这扇门屡攻不破呢？要想学习好VC必须具备良好的C/C+的基础，必要的英语阅读能力也是必不可少的，因为大量的技术文档多以英文形式发布。VC基于C，C+语言，主要由是MFC组成，是与系统联系非常紧密的编程工具，它兼有高级，和低级语言的双重

6、性，功能强大，灵活，执行效率高，几乎可说VC在 Windows平台无所不能。 最大缺点是开发效率不高。 VC适用范围 1、 VC主要是针对Windows系统，适合一些系统级的开发，可以方便实现一些底层 的调用。在VC里边嵌入汇编语言很简单。 2、 VC主要用在驱动程序开发 3、 VC执行效率高,当对系统性能要求很高的时候，可用VC开发。 4、 VC主要适用于游戏开发 5、 VC多用于单片机，工业控制等软件开发，如直接对I/O地址操作，就要用C+。 6、 VC适用开发高效，短小，轻量级的COM组件,DLL。比如WEB上的控件。 7、 VC可以开发优秀的基于通信的程序。8、 VC可以开发高效灵活的

7、文件操作程序。9、 VC可以开发灵活高效的数据库操作程序。 10、 VC是编CAD软件的唯一选择！包括AUTOCAD，UG的二次开发。 11、VC在多线程、网络通信、分布应用方面，VC+有不可比拟的优势。2概要设计总体功能设计：(1)设置一个迷宫节点的数据结构。(2)建立迷宫图形。(3)对迷宫进行处理找出一条从入口点到出口点的路径。(4)输出该路径。(5)打印通路迷宫图。初始化迷宫通过随机方法设置迷宫布局建立并输出迷宫原图搜索迷宫通路输出迷宫通路及路线图结束图2-1 功能结构图当迷宫采用二维数组表示时，老鼠在迷宫任一时刻的位置可由数组的行列序号i，j来表示。而从 i,j位置出发可能进行的方向见

8、下图1.如果i,j周围的位置均为0值，则老鼠可以选择这8个位置中的任一个作为它的下一位置。将这8个方向分别记作：E（东）、SE（东南）、S（南）SW（西南）W（西）、NW（西北）、N（北）和NE（东北）。但是并非每一个位置都有8个相邻位置。如果i,j位于边界上，即i=1，或i=m，或j=1，或j=n，则相邻位置可能是3个或5个为了避免检查边界条件，将数组四周围用值为1的边框包围起来，这样二维数组maze应该声明为mazem+2,n+2在迷宫行进时，可能有多个行进方向可选，我们可以规定方向搜索的次序是从东（E）沿顺时针方向进行。为了简化问题，规定i,j的下一步位置的坐标是x,y，并将这8个方位伤

9、的x和y坐标的增量预先放在一个结构数组move8中（见图2）。该数组的每个分量有两个域dx和dy。例如 要向东走，只要在j值上加上dy，就可以得到下一步位置的x,y值为i,j+dy。于是搜索方向的变化只要令方向值dir从0增至7，便可以从move数组中得到从i,j点出发搜索到的每一个相邻点x,y。x=i+movedir.dxy=j+movedir.dy dx dy 图2-2 方向位移图 图2-3向量差图为了防止重走原路，我们规定对已经走过的位置，将原值为0改为-1，这既可以区别该位置是否已经走到过，又可以与边界值1相区别。当整个搜索过程结束后可以将所有的-1改回到0，从而恢复迷宫原样。这样计算

10、机走迷宫的方法是：采取一步一步试探的方法。每一步都从（E）开始，按顺时针对8个方向进行探测，若某个方位上的mazex,y=0，表示可以通行，则走一步；若mazex,y=1，表示此方向不可通行须换方向再试。直至8个方向都试过，mazex,y均为1，说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。为此需要设置一个栈，用来记录所走过的位置和方向（i，j，dir）。当退回一步时，就从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到一个行进方向，则把当前位置和新的方向重新进栈，并走到新的位置。如果探测到x=m，y=n，则已经到达迷宫的出口，可以停止检测，输出存在栈中的路径

11、；若在某一位置的8个方向上都堵塞，则退回一步，继续探测，如果已经退到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。3详细设计和实现3.1软件设计几个方面：一、 抽象： 我们把迷宫问题抽象化，把迷宫看作一个矩阵，对于矩阵中的任意个位置都有八个方向可以进行下一步，而路径的保存则可以利用栈结构保存矩阵在该点的坐标即可。二、 模块化：将整个系统根据功能作用划分为多个部分以方便程序的读写及修改，增加程序的可读性友好性，也使整个系统的设计更具条理。三、软件的设计原则应遵循以下几个方面：1、 设计对于分析模型应该是可跟踪的：软件的模块可能被映射到多个需求上。2、 设计结构应该尽可能的模拟实际问题。3、

12、 设计应该表现出一致性。4、 不要把设计当成编写代码。5、 在创建设计时就应该能够评估质量。6、 评审设计以减少语义性的错误。软件设计包括软件的结构设计，数据设计，接口设计和过程设计结构设计是指：定义软件系统各主要部件之间的关系数据设计是指：将模型转换成数据结构的定义接口设计是指：软件内部，软件和操作系统间以及软件和人之间如何通信过程设计是指：系统结构部件转换成软件的过程描述3.2功能模块设计：系统算法：(1)建立迷宫节点的结构类型stack。(2)入迷宫图形 0表示可以通 1表示不可以通。 用二维数组mazem+2n+2进行存储。数组四周用1表示墙壁，其中入口点（1，1）与出口点（m，n）固

13、定。 (3)函数path()对迷宫进行处理，从入口开始：While(!(s->top=-1)&&(dir>=7)|(x=M)&&(y=N)&&(mazexy=-1) For(扫描八个可以走的方向) If(找到一个可以走的方向)进入栈标志在当前点可以找到一个可以走的方向避免重复选择mazexy=-1不再对当前节点扫描 If(八个方向已经被全部扫描过，无可以通的路) 标志当前节点没有往前的路 后退一个节点搜索If(找到了目的地) 输出路径退出循环 未找到路径 (4)输出从入口点到出口点的一条路径。 (5)输出标有通路的迷宫图。算法流程图：

14、开始初始化迷宫，显示迷宫初始化方向位移数组寻找迷宫中的一条出路If mazexy=0设1，1为出口该点数据入栈TFWhile 栈不空且dir<7doelseIf dir<7dir+TF回退一步出口或入口dir>=7 或栈空显示通路结束图3-1 算法流程图3.3详细代码设计：#define M2 12 /*M2*N2为实际使用迷宫数组的大小*/#define N2 11#define maxlen M2 / 栈长度#include <stdio.h>#include<iostream.h>#include <malloc.h>int M=M2

15、-2,N=N2-2;/M*N迷宫的大小typedef struct /定义栈元素的类型int x,y,dir;elemtype;typedef struct / 定义顺序栈elemtype stack maxlen;int top;sqstktp; struct moved /定义方向位移数组的元素类型对于存储坐标增量的方向位移数组move int dx,dy;/ void inimaze(int mazeN2)/初始化迷宫 int i,j,num; for(i=0,j=0;i<=M+1;i+)/设置迷宫边界mazeij=1; for(i=0,j=0;j<=N+1;j+) maze

16、ij=1; for(i=M+1,j=0;j<=N+1;j+) mazeij=1; cout<<"原始迷宫为："<<endl; for(i=1;i<=M;i+) for (j=1;j<=N;j+) num=(800*(i+j)+1500) % 327;/根据MN的值产生迷宫 if (num<150)&&(i!=M|j!=N) mazeij=1; else mazeij=0; cout<<mazeij<<" "/显示迷宫 cout<<endl; cout<

17、;<endl; /inimaze/void inimove(struct moved move)/初始化方向位移数组/依次为East，Southeast，south，southwest，west，northwest，north，northeastmove0.dx=0;move0.dy=1;move1.dx=1;move1.dy=1;move2.dx=1;move2.dy=0;move3.dx=1;move3.dy=-1;move4.dx=0;move4.dy=-1;move5.dx=-1;move5.dy-=1;move6.dx=-1;move6.dy=0;move7.dx=-1;mov

18、e7.dy=1;/void inistack(sqstktp *s) /*初始化栈*/s->top=-1; /*inistack*/int push(sqstktp*s,elemtype x)if(s->top=maxlen-1)return(false);elses->stack+s->top=x;/*栈不满，执行入栈操作*/return(true);/*push*/elemtype pop(sqstktp *s)/*栈顶元素出栈*/elemtype elem;if(s->top<0) /如果栈空，返回空值elem.x=NULL;elem.y=NULL;e

19、lem.dir=NULL;return(elem);elses->top-;return(s->stacks->top+1); /栈不空，返回栈顶元素 /pop/void path(int mazeN2,struct moved move,sqstktp *s) /寻找迷宫中的一条通路int i,j,dir,x,y,f;elemtype elem;i=1;j=1;dir=0;maze11=-1; /设11为入口处do x=i+movedir.dx;/球下一步可行的到达点的坐标y=j+movedir.dy;if(mazexy=0)elem.x=i;elem.y=j;elem.d

20、ir=dir;f=push(s,elem);/如果可行将数据入栈if(f=false)/如果返回假，说明栈容量不足cout<<"栈长不足"i=x;j=y;dir=0;mazexy=-1;elseif (dir < 7)dir+;elseelem=pop(s); /8个方向都不行，回退if(elem.x!=NULL)i=elem.x;j=elem.y;dir=elem.dir+1;while(!(s->top=-1)&&(dir>=7)|(x=M)&&(y=N)&&(mazexy=-1); /循环i

21、f(s->top=-1)/若是入口，则无通路cout<<"此迷宫不通"elseelem.x=x; elem.y=y; elem.dir=dir;/将出口坐标入栈f=push(s,elem);cout<<"迷宫通路是："<<endl;i=0;while (i <= s->top)cout<<"("<<s->stacki.x<<","<<s->stacki.y<<")"/显示

22、迷宫通路if(i!=s->top)cout<<"->"if(i+1)%4=0)cout<<endl;i+; /void draw(int mazeN2,sqstktp *s) /在迷宫中绘制出通路 cout<<"逃逸路线为："<<endl;int i,j;elemtype elem;for(i=1;i<=M;i+) /将迷宫中全部的-1值回复为0值for(j=1;j<=N;j+)if(mazeij=-1)mazeij=0;while(s->top>-1) /根据栈中元素的

23、坐标，将通路的各个点的值改为8elem=pop(s);i=elem.x;j=elem.y;mazeij=8;for(i=1;i<=M;i+)for(j=1;j<=N;j+)printf("%3d",mazeij); /显示已标记通路的迷宫cout<<endl;void main() /寻找迷宫通路程序sqstktp *s;int mazeM2N2;struct moved move8;inimaze(maze); /初始化迷宫数组s=(sqstktp *)malloc(sizeof(sqstktp);inistack(s); /初始化栈inimove

24、(move); /初始化方向位移数组path(maze,move,s); /寻找迷宫通路cout<<endl;draw(maze,s); /绘制作出通路标记的迷宫3.4运行结果：图3-2 运行结果图4调试与操作说明本次课程设计的迷宫选题相对比较简单，在设计和调试阶段虽然也遇到了一些技术上的问题，但在老师同学的指导解答后都顺利解决了。本系统在使用时只需直接运行即可，这一结果虽然简便易懂但实用性就大大降低了，所以在以后的时间里该系统还需进一步完善以充分完成该系统的设计目的及应用范围。总结本次课程设计中，我利用Microsoft Visual c+ 通过对老鼠走迷宫这个古老而经典的问题进

25、行分析，设计并制作的了该迷宫系统。在设计时，加深了对Microsoft Visual c+ 语法以及算法设计的认识，而对于老鼠走迷宫的问题分解剖析从数学角度进行了转换从而让Microsoft Visual c+语句将之描述出来。从一定程度上说，编一个程序并不难，难的是要把这个程序完全调试正确。学过软件工程就知道，一个程序的执行分支是无法穷尽的。也就是说我们调试的话不可能把程序的每一条执行路径都执行一遍。也就是说，不可能保证我们的程序是百分之百的正确的。我们调试的目的是在程序没有语法错误的基础上保证我们的程序能达到我们所需要的主要的功能。我们在调试迷宫求解算法中知道，其实我们只是找到一条从入口点到出口点的路径，也许题目中还存在多条路径，更重要的是此路径还不一定是最短路径。我们在进行程序的调试前应该要先明白我们要输入些什么数据并且其应该得到些什么样的结果，这样我们才能更早的查找出错误并成功调试出结果。在设计中，利用move()函数来作为探索触角是该系统的一个亮点，在原坐标上加上步长，从而使该