迷宫问题数据结构.docx

迷宫问题数据结构.docx

《迷宫问题数据结构.docx》由会员分享，可在线阅读，更多相关《迷宫问题数据结构.docx（19页珍藏版）》请在冰点文库上搜索。

迷宫问题数据结构

摘要：

本文详细介绍了迷宫问题的设计与实现，该程序具有迷宫的设计生成、逃离迷宫的路线的寻找、打印逃离路线及标拄了逃离路线的迷宫等功能。

在课程设计中，程序设计语言采用VisualC++，程序运行平台为Windows98/2000/XP。

对于迷宫逃离路线的产生及打印本系统采用了栈的结构，有利于数据的存储与输出。

在设计该程序时采用了挨个试探的方法，简单易懂。

程序通过调试运行，实现了最初的设计目标，并且经过适当完善后，可以求出迷宫逃离路线的最短行程，在实际中可以解决更多的问题。

关键词：

c++；结构体；栈结构；链表

1需求分析

迷宫实验是取自心理学的一个古典实验。

在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。

盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。

对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。

老鼠经多次试验终于得到它学习走迷宫的路线。

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

本次课程设计目的是巩固C++课程所学知识，特别加强数组，指针，结构体，栈结构的应用，熟悉面向过程的结构化序设计方法，通过本次课程设计的实践，锻炼程序设计的能力以及用C++解决实际问题的能力，为以后后续课程的学习打好基础。

在设计中，在Windowsxp操作系统下，利用MicrosoftVisualc++语言对迷宫问题进行设计制作下面将对MicrosoftVisualc++进行简要介绍：

VC++是微软公司开发的一个IDE（集成开发环境）,换句话说,就是使用VC++的一个开发平台.有些软件就是这个编出来的...另外还有VB,VF.只是使用不同语言...但是,

VC++是Windows平台上的C++编程环境，学习VC要了解很多Windows平台的特性并且还要掌握MFC、ATL、COM等的知识，难度比较大。

Windows下编程需要了解Windows的消息机制以及回调（callback）函数的原理；MFC是Win32API的包装类，需要理解文档视图类的结构，窗口类的结构，消息流向等等；COM是代码共享的二进制标准，需要掌握其基本原理等等。

VC作为一个主流的开发平台一直深受编程爱好者的喜爱，但是很多人却对它的入门感到难于上青天，究其原因主要是大家对他错误的认识造成的，严格的来说VC++不是门语言，虽然它和C++之间有密切的关系,如果形象点比喻的话，可以把C++看作为一种“工业标准”，而VC++则是某种操作系统平台下的“厂商标准”,而“厂商标准”是在遵循“工业标准”的前提下扩展而来的。

VC++应用程序的开发主要有两种模式，一种是WINAPI方式，另一种则是MFC方式，传统的WINAPI开发方式比较繁琐，而MFC则是对WINAPI再次封装，所以MFC相对于WINAPI开发更具备效率优势，但为了对WINDOWS开发有一个较为全面细致的认识，笔者在这里还是以讲解WINAPI的相关内容为主线。

话说到这里可能更多人关心的是学习VC++需要具备什么条件，为什么对于这扇门屡攻不破呢？

要想学习好VC必须具备良好的C/C++的基础，必要的英语阅读能力也是必不可少的，因为大量的技术文档多以英文形式发布。

VC基于C，C++语言，主要由是MFC组成，是与系统联系非常紧密的编程工具，它兼有高级，和低级语言的双重性，功能强大，灵活，执行效率高，几乎可说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可以开发高效灵活的文件操作程序。

9、VC可以开发灵活高效的数据库操作程序。

10、VC是编CAD软件的唯一选择包括AUTOCAD，UG的二次开发。

11、VC在多线程、网络通信、分布应用方面，VC++有不可比拟的优势。

2概要设计

总体功能设计：

（1）设置一个迷宫节点的数据结构。

（2）建立迷宫图形。

（3）对迷宫进行处理找出一条从入口点到出口点的路径。

（4）输出该路径。

（5）打印通路迷宫图。

当迷宫采用二维数组表示时，老鼠在迷宫任一时刻的位置可由数组的行列序号i，j来表示。

而从[i],[j]位置出发可能进行的方向见下图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应该声明为maze[m+2],[n+2]在迷宫行进时，可能有多个行进方向可选，我们可以规定方向搜索的次序是从东（E）沿顺时针方向进行。

为了简化问题，规定[i],[j]的下一步位置的坐标是[x],[y]，并将这8个方位伤的x和y坐标的增量预先放在一个结构数组move[8]中（见图2）。

该数组的每个分量有两个域dx和dy。

例如要向东走，只要在j值上加上dy，就可以得到下一步位置的[x],[y]值为[i],[j+dy]。

于是搜索方向的变化只要令方向值dir从0增至7，便可以从move数组中得到从[i],[j]点出发搜索到的每一个相邻点[x],[y]。

x=i+move[dir].dx

y=j+move[dir].dy

dxdy

图2-2方向位移图图2-3向量差图

为了防止重走原路，我们规定对已经走过的位置，将原值为0改为-1，这既可以区别该位置是否已经走到过，又可以与边界值1相区别。

当整个搜索过程结束后可以将所有的-1改回到0，从而恢复迷宫原样。

这样计算机走迷宫的方法是：

采取一步一步试探的方法。

每一步都从（E）开始，按顺时针对8个方向进行探测，若某个方位上的maze[x],[y]=0，表示可以通行，则走一步；若maze[x],[y]=1，表示此方向不可通行须换方向再试。

直至8个方向都试过，maze[x],[y]均为1，说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。

为此需要设置一个栈，用来记录所走过的位置和方向（i，j，dir）。

当退回一步时，就从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到一个行进方向，则把当前位置和新的方向重新进栈，并走到新的位置。

如果探测到x=m，y=n，则已经到达迷宫的出口，可以停止检测，输出存在栈中的路径；若在某一位置的8个方向上都堵塞，则退回一步，继续探测，如果已经退到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。

3详细设计和实现

3.1软件设计几个方面：

一、抽象：

我们把迷宫问题抽象化，把迷宫看作一个矩阵，对于矩阵中的任意个位置都有八个方向可以进行下一步，而路径的保存则可以利用栈结构保存矩阵在该点的坐标即可。

二、模块化：

将整个系统根据功能作用划分为多个部分以方便程序的读写及修改，增加程序的可读性友好性，也使整个系统的设计更具条理。

三、软件的设计原则应遵循以下几个方面：

1、设计对于分析模型应该是可跟踪的：

软件的模块可能被映射到多个需求上。

2、设计结构应该尽可能的模拟实际问题。

3、设计应该表现出一致性。

4、不要把设计当成编写代码。

5、在创建设计时就应该能够评估质量。

6、评审设计以减少语义性的错误。

软件设计包括软件的结构设计，数据设计，接口设计和过程设计．

结构设计是指：

定义软件系统各主要部件之间的关系

数据设计是指：

将模型转换成数据结构的定义

接口设计是指：

软件内部，软件和操作系统间以及软件和人之间如何通信

过程设计是指：

系统结构部件转换成软件的过程描述

3.2功能模块设计：

系统算法：

（1）建立迷宫节点的结构类型stack[]。

（2）入迷宫图形0表示可以通1表示不可以通。

用二维数组maze[m+2][n+2]进行存储。

数组四周用1表示墙壁，其中入口点（1，1）与出口点（m，n）固定。

（3）函数path（）对迷宫进行处理，从入口开始：

While（!

（（s->top==-1）&&（dir>=7）||（x==M）&&（y==N）&&（maze[x][y]==-1）））

{

For（扫描八个可以走的方向）

{

If（找到一个可以走的方向）

{

进入栈

标志在当前点可以找到一个可以走的方向

避免重复选择maze[x][y]=-1

不再对当前节点扫描

}

If（八个方向已经被全部扫描过，无可以通的路）

{

标志当前节点没有往前的路

后退一个节点搜索

}

}

If（找到了目的地）

{

输出路径退出循环

}

}

未找到路径

（4）输出从入口点到出口点的一条路径。

（5）输出标有通路的迷宫图。

算法流程图：

3.3详细代码设计：

#defineM212/*M2*N2为实际使用迷宫数组的大小*/

#defineN211

#definemaxlenM2//栈长度

#include

#include

#include

intM=M2-2,N=N2-2;//M*N迷宫的大小

typedefstruct//定义栈元素的类型

{

intx,y,dir;

}elemtype;

typedefstruct//定义顺序栈

{

elemtypestack[maxlen];

inttop;

}sqstktp;

structmoved

//定义方向位移数组的元素类型对于存储坐标增量的方向位移数组move

{intdx,dy;};

////////////////////////////////////////////////////////////////////////////////////////////////////

voidinimaze（intmaze[][N2]）////初始化迷宫

{

inti,j,num;

for（i=0,j=0;i<=M+1;i++）//设置迷宫边界

maze[i][j]=1;

for（i=0,j=0;j<=N+1;j++）

maze[i][j]=1;

for（i=M+1,j=0;j<=N+1;j++）

maze[i][j]=1;

cout<<"原始迷宫为：

"<

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））

maze[i][j]=1;

else

maze[i][j]=0;

cout<

}

cout<

}

cout<

}//inimaze

///////////////////////////////////////////////////////////////////////////////////////////////////////////////

voidinimove（structmovedmove[]）//初始化方向位移数组

{//依次为East，Southeast，south，southwest，west，northwest，north，northeast

move[0].dx=0;move[0].dy=1;

move[1].dx=1;move[1].dy=1;

move[2].dx=1;move[2].dy=0;

move[3].dx=1;move[3].dy=-1;

move[4].dx=0;move[4].dy=-1;

move[5].dx=-1;move[5].dy-=1;

move[6].dx=-1;move[6].dy=0;

move[7].dx=-1;move[7].dy=1;

}//

voidinistack（sqstktp*s）/*初始化栈*/

{

s->top=-1;

}/*inistack*/

intpush（sqstktp*s,elemtypex）

{

if（s->top==maxlen-1）

return（false）;

else

{

s->stack[++s->top]=x;/*栈不满，执行入栈操作*/

return（true）;

}

}/*push*/

elemtypepop（sqstktp*s）/*栈顶元素出栈*/

{

elemtypeelem;

if（s->top<0）//如果栈空，返回空值

{

elem.x=NULL;

elem.y=NULL;

elem.dir=NULL;

return（elem）;

}

else

{

s->top--;

return（s->stack[s->top+1]）;//栈不空，返回栈顶元素

}

}//pop

////////////////////////////////////////////////////////////////////////////////////

voidpath（intmaze[][N2],structmovedmove[],sqstktp*s）//寻找迷宫中的一条通路

{

inti,j,dir,x,y,f;

elemtypeelem;

i=1;j=1;dir=0;

maze[1][1]=-1;//设[1][1]为入口处

do

{

x=i+move[dir].dx;//球下一步可行的到达点的坐标

y=j+move[dir].dy;

if（maze[x][y]==0）

{

elem.x=i;elem.y=j;elem.dir=dir;

f=push（s,elem）;//如果可行将数据入栈

if（f==false）//如果返回假，说明栈容量不足

cout<<"栈长不足";

i=x;j=y;dir=0;maze[x][y]=-1;

}

else

if（dir<7）

dir++;

else

{

elem=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）&&（maze[x][y]==-1）））;//循环

if（s->top==-1）//若是入口，则无通路

cout<<"此迷宫不通";

else

{

elem.x=x;elem.y=y;elem.dir=dir;//将出口坐标入栈

f=push（s,elem）;

cout<<"迷宫通路是：

"<

i=0;

while（i<=s->top）

{

cout<<"（"<stack[i].x<<","<stack[i].y<<"）";//显示迷宫通路

if（i!

=s->top）

cout<<"-->";

if（（i+1）%4==0）

cout<

i++;

}

}

}

//////////////////////////////////////////////////////////////////////////////

voiddraw（intmaze[][N2],sqstktp*s）//在迷宫中绘制出通路

{

cout<<"逃逸路线为：

"<

inti,j;

elemtypeelem;

for（i=1;i<=M;i++）//将迷宫中全部的-1值回复为0值

{

for（j=1;j<=N;j++）

{

if（maze[i][j]==-1）

maze[i][j]=0;

while（s->top>-1）//根据栈中元素的坐标，将通路的各个点的值改为8

{

elem=pop（s）;

i=elem.x;j=elem.y;

maze[i][j]=8;

}

for（i=1;i<=M;i++）

{

for（j=1;j<=N;j++）

{

printf（"%3d",maze[i][j]）;//显示已标记通路的迷宫

}

cout<

}

}

}

}

voidmain（）//寻找迷宫通路程序

{

sqstktp*s;

intmaze[M2][N2];

structmovedmove[8];

inimaze（maze）;//初始化迷宫数组

s=（sqstktp*）malloc（sizeof（sqstktp））;

inistack（s）;//初始化栈

inimove（move）;//初始化方向位移数组

path（maze,move,s）;//寻找迷宫通路

cout<

draw（maze,s）;//绘制作出通路标记的迷宫

}

3.4运行结果：

图3-2运行结果图

4调试与操作说明

本次课程设计的迷宫选题相对比较简单，在设计和调试阶段虽然也遇到了一些技术上的问题，但在老师同学的指导解答后都顺利解决了。

本系统在使用时只需直接运行即可，这一结果虽然简便易懂但实用性就大大降低了，所以在以后的时间里该系统还需进一步完善以充分完成该系统的设计目的及应用范围。

总结

本次课程设计中，我利用MicrosoftVisualc++通过对老鼠走迷宫这个古老而经典的问题进行分析，设计并制作的了该迷宫系统。

在设计时，加深了对MicrosoftVisualc++语法以及算法设计的认识，而对于老鼠走迷宫的问题分解剖析从数学角度进行了转换从而让MicrosoftVisualc++语句将之描述出来。

从一定程度上说，编一个程序并不难，难的是要把这个程序完全调试正确。

学过软件工程就知道，一个程序的执行分支是无法穷尽的。

也就是说我们调试的话不可能把程序的每一条执行路径都执行一遍。

也就是说，不可能保证我们的程序是百分之百的正确的。

我们调试的目的是在程序没有语法错误的基础上保证我们的程序能达到我们所需要的主要的功能。

我们在调试迷宫求解算法中知道，其实我们只是找到一条从入口点到出口点的路径，也许题目中还存在多条路径，更重要的是此路径还不一定是最短路径。

我们在进行程序的调试前应该要先明白我们要输入些什么数据并且其应该得到些什么样的结果，这样我们才能更早的查找出错误并成功调试出结果。

在设计中，利用move（）函数来作为探索触角是该系统的一个亮点，在原坐标上加上步长，从而使该试探以原确定坐标为原点向八个方向探索出路；还有就是利用栈结构来处理搜索出来的路线坐标使其能够很形象的展现穷举算法得到结果的详细经过。

但从实用角度来说，本系统还不具备很好的拓展性，还需加以改进，例如在迷宫初始化时并不能想预想的一样产生随机的理想的迷宫原图。

这一迷宫系统在穷举法的运用上淋漓尽致的表现出来，在为来对一些复杂却又没有规律可循的事件的处理时能够发挥很大的用处，只需对其搜索要求进行一定的改变及提高就能使之活用于各种穷举事件。

致谢

这次课程设计，从选题到定稿，从理论到实践，在为数几个星期的时间里，日子尽管过得很忙碌，但心里却是开心的，从中获得很难多的知识和经验。

这期间，我复习和巩固了这一学期所学的知识，并将它们运用到这次课程设计中，理论实践相结合，提高自己动手和独立思考能力，最重要的是提高了解决困难的能力。

本次课程设计我要衷心感谢所有帮助过我的老师和同学，感谢他们从精神以及实践上的照顾、答疑；还要感谢学校为我提供一个有利的环境,实验室以及图书馆给了我信息的重要来源。

借此机会，我还要特别感谢我的指导老师和院系各领导对我们这次课程设计的大力支持和极大关注。

在此我尤其感谢老师在我遇到困难时耐心细致的给我解答，最终成功的得到了预想的结果。

课程设计遇到了很多困难，在这个重要环节，通过查询资料，请教老师和同学，在大家的帮助下，加上自己的不断努力，最终解决并顺利完成了此次课程设计。

课程设计的过程，是学习的过程，也是锻炼的过程，更是教会我们同学之间相互帮助，共同克服困难的过程，这将是人生中一笔宝贵的财富，是我受用不尽的同时，我一定将之好好珍惜。

参考文献

1殷人昆主编.数据结构（用面向对象方法与c++语言描述）.第2版.北京：

清华大学出版社，2007

2宁正元，易金聪.数据结构习题解析与上机实验指导.北京：

中国水利水电出版社，2000

3吴乃陵，况迎辉.c++程序设计.第2版.北京：

高等教育出版社，2006

4揣锦华.面向对象程序设计与vc++实践.西安：

西安电子科技大学出版社，2005

5