摘要：
本文详细介绍了迷宫问题的设计与实现，该程序具有迷宫的设计生成、逃离迷宫的路线的寻找、打印逃离路线及标拄了逃离路线的迷宫等功能。在课程设计中，程序设计语言采用Visual C++，程序运行平台为Windows 98/2000/XP。对于迷宫逃离路线的产生及打印本系统采用了栈的结构，有利于数据的存储与输出。在设计该程序时采用了挨个试探的方法，简单易懂。程序通过调试运行，实现了最初的设计目标，并且经过适当完善后，可以求出迷宫逃离路线的最短行程，在实际中可以解决更多的问题。
关键词：c++；结构体；栈结构；链表
目录
1需求分析 (1)
2概要设计 (3)
3详细设计和实现 (5)
3.1软件设计几个方面： (5)
3.2功能模块设计： (6)
3.3详细代码设计： (8)
3.4运行结果： (16)
4调试与操作说明 (16)
总结 (17)
致谢 (18)
参考文献 (19)
1需求分析
迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
本次课程设计目的是巩固C++课程所学知识，特别加强数组，指针，结构体，栈结构的应用，熟悉面向过程的结构化序设计方法，通过本次课程设计的实践，锻炼程序设计的能力以及用C++解决实际问题的能力，为以后后续课程的学习打好基础。
在设计中，在Windows xp 操作系统下，利用Microsoft Visual c++语言对迷宫问题进行设计制作下面将对Microsoft Visual c++进行简要介绍：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++应用程序的开发主要有两种模式，一种是WIN API方式，另一种则是MFC方式，传统的WIN API开发方式比较繁琐，而MFC则是对WIN API再次封装，所以MFC相对于WIN API开发更具备效率优势，但为了对WINDOWS开发有一个较为全面细致的认识，笔者在这里还是以讲解WIN API的相关内容为主线。
话说到这里可能更多人关心的是学习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)打印通路迷宫图。
图2-1 功能结构图
当迷宫采用二维数组表示时，老鼠在迷宫任一时刻的位置可由数组的行列序号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
dx dy
图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-1 算法流程
图
3.3详细代码设计：
#define M2 12 /*M2*N2为实际使用迷宫数组的大小*/
#define N2 11
#define maxlen M2 // 栈长度
#include
#include
#include
int M=M2-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 maze[][N2])////初始化迷宫
{
int i,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 /////////////////////////////////////////////////////////////////////////////////////////////////////////////// void inimove(struct moved move[])//初始化方向位移数组 {//依次为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; }// void inistack(sqstktp *s) /*初始化栈*/ { s->top=-1; } /*inistack*/ int push(sqstktp*s,elemtype x) { if(s->top==maxlen-1) return(false); else { s->stack[++s->top]=x;/*栈不满，执行入栈操作*/ return(true); } }/*push*/ elemtype pop(sqstktp *s)/*栈顶元素出栈*/ { elemtype elem; 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 //////////////////////////////////////////////////////////////////////////////////// void path(int maze[][N2],struct moved move[],sqstktp *s) //寻找迷宫中的一条通路 { int i,j,dir,x,y,f; elemtype elem; 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<<"("< if(i!=s->top) cout<<"-->"; if((i+1)%4==0) cout< i++; } } } ////////////////////////////////////////////////////////////////////////////// void draw(int maze[][N2],sqstktp *s) //在迷宫中绘制出通路 { cout<<"逃逸路线为："< int i,j; elemtype elem; 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< } } } } void main() //寻找迷宫通路程序 { sqstktp *s; int maze[M2][N2]; struct moved move[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调试与操作说明 本次课程设计的迷宫选题相对比较简单，在设计和调试阶段虽然也遇到了一些技术上的问题，但在老师同学的指导解答后都顺利解决了。本系统在使用时只需直接运行即可，这一结果虽然简便易懂但实用性就大大降低了，所以在以后的时间里该系统还需进一步完善以充分完成该系统的设计目的及应用范围。 总结 本次课程设计中，我利用Microsoft Visual c++ 通过对老鼠走迷宫这个古老而经典的问题进行分析，设计并制作的了该迷宫系统。在设计时，加深了对Microsoft Visual c++ 语法以及算法设计的认识，而对于老鼠走迷宫的问题分解剖析从数学角度进行了转换从而让Microsoft Visual c++语句将之描述出来。 从一定程度上说，编一个程序并不难，难的是要把这个程序完全调试正确。学过软件工程就知道，一个程序的执行分支是无法穷尽的。也就是说我们调试的话不可能把程序的每一条执行路径都执行一遍。也就是说，不可能保证我们的程序是百分之百的正确的。我们调试的目的是在程序没有语法错误的基础上保证我们的程序能达到我们所需要的主要的功能。我们在调试迷宫求解算法中知道，其实我们只是找到一条从入口点到出口点的路径，也许题目中还存在多条路径，更重要的是此路径还不一定是最短路径。我们在进行程序的调试前应该要先明白我们要输入些什么数据并且其应该得到些什么样的结果，这样我们才能更早的查找出错误并成功调试出结果。 在设计中，利用move()函数来作为探索触角是该系统的一个亮点，在原坐标上加上步长，从而使该试探以原确定坐标为原点向八个方向探索出路；还有就是利用栈结构来处理搜索出来的路线坐标使其能够很形象的展现穷举算法得到结果的详细经过。 但从实用角度来说，本系统还不具备很好的拓展性，还需加以改进，例如在迷宫初始化时并不能想预想的一样产生随机的理想的迷宫原图。这一迷宫系统在穷举法的运用上淋漓尽致的表现出来，在为来对一些复杂却又没有规律可循的事件的处理时能够发挥很大的用处，只需对其搜索要求进行一定的改变及提高就能使之活用于各种穷举事件。 致谢 这次课程设计，从选题到定稿，从理论到实践，在为数几个星期的时间里，日子尽管过得很忙碌，但心里却是开心的，从中获得很难多的知识和经验。这期间，我复习和巩固了这一学期所学的知识，并将它们运用到这次课程设计中，理论实践相结合，提高自己动手和独立思考能力，最重要的是提高了解决困难的能力。 本次课程设计我要衷心感谢所有帮助过我的老师和同学，感谢他们从精神以及实践上的照顾、答疑；还要感谢学校为我提供一个有利的环境,实验室以及图书馆给了我信息的重要来源。借此机会，我还要特别感谢我的指导老师和院系各领导对我们这次课程设计的大力支持和极大关注。在此我尤其感谢老师在我遇到困难时耐心细致的给我解答，最终成功的得到了预想的结果。课程设计遇到了很多困难，在这个重要环节，通过查询资料，请教老师和同学，在大家的帮助下，加上自己的不断努力，最终解决并顺利完成了此次课程设计。 课程设计的过程，是学习的过程，也是锻炼的过程，更是教会我们同学之间相互帮助，共同克服困难的过程，这将是人生中一笔宝贵的财富，是我受用不尽的同时，我一定将之好好珍惜。 《数据结构与算法设计》迷宫问题实验报告 ——实验二 专业：物联网工程 班级：物联网1班 学号：15180118 ：刘沛航 一、实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1、概要设计 （1）设定栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={ StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack （2）设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL} ROW={ 1、课程设计目的 为了配合《数据结构》课程的开设，通过设计一完整的程序，掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法特进行题目为两个链表合并的课程设计。通过此次课程设计充分锻炼有关数据结构中链表的创建、合并等方法以及怎样通过转化成C语言在微机上运行实现等其他方面的能力。 2．课程设计的内容与要求 2.1问题描述： 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。 图A 2.2设计要求： 要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 3.2 概要设计 1.①构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵 ②自动或手动生成迷宫，即为二维数组maze[M+2][N+2]赋值 ③构建一个队列用于存储迷宫路径 ④建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况 ⑤实现搜索算法 ⑥屏幕上显示操作菜单 2.本程序包含10个函数： (1)主函数main() (2)手动生成迷宫函数shoudong_maze() 数据结构课程设计报告 设计题目：迷宫问题数据结构课程设计_ 班级：计科152 学号：19215225 姓名：徐昌港 南京农业大学计算机系 数据结构课程设计报告内容 一．课程设计题目 迷宫问题 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 二．算法设计思想 1.需求分析 （1）迷宫数据用一个二维数组int maze[row][col]来存储，在定义了迷宫的行列数后，用两个for循环来录入迷宫数据，并在迷宫周围加墙壁。 （2）迷宫的入口位置和出口位置可以由用户自己决定。 2.概要设计 （1）主程序模块： void main() { int maze[row][col]; struct mark start,end; //出入口的坐标 int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //方向，依次是东西南北 built_maze(maze); printf("请输入入口的横纵坐标："); scanf("%d,%d",&start.a,&start.b); printf("请输入出口的横纵坐标："); scanf("%d,%d",&end.a,&end.b); printf("0为东，1为南，2为西，3为北，-1为出路\n"); maze_path(maze,dir,start,end); getchar(); } （2）栈模块——实现栈抽象数据类型 （3）迷宫模块——实现迷宫抽象数据类型，建立迷宫，找出迷宫的一条通路 3.详细设计 （1）坐标位置类型 struct mark{ int a,b; //迷宫a行b列为位置 }; （2）迷宫类型 void built_maze(int maze[row][col]) //按照用户输入的row行和col列的二维数组（元素值为0和1） //设置迷宫maze的初值，包括边上边缘一圈的值 void maze_path(int maze[row][col],int dir[4][2],struct mark start,struct mark end) //求解迷宫maze中，从入口start到出口end的一条路径， //若存在，则返回TRUE；否则返回FALSE （3）栈类型 struct element{ int i,j,d; //坐标与方向 }; typedef struct Linkstack{ element elem; 目录第一部分需求分析 第二部分详细设计 第三部分调试分析 第四部分用户手册 第五部分测试结果 第六部分附录 第七部分参考文献 一、需求分析 1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没有这样通路的信息。 2、可以用一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j， d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。 4、由于迷宫是任意给定的，所以程序要能够对给定的迷宫生成对应的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。 二、详细设计 1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路 退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2、如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通。 3、所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路不能重复走第二次"，它包括"曾经走过而没有走通的路"。 显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。 4、若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。 所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的 云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 实验难度 A □ B □ C □ 承担任务 （难度为C时填写） 指导教师评分（签名） 【实验题目】 实验4.数组的表示极其应用 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d 表示走到下一坐标的方向。如；对于下列数据的迷宫，输出的一条通路为：(l，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，…。? （下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) （本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识） 本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。我们将其简化成具体实验内容如下：选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“→”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，输出信息。 可以二维数组存储迷宫数据，用户指定入口下标和出口下标。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。? 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1. 设定迷宫的抽象数据类型定义： ADT Maze { 数据对象：D = { a i, j | a i, j ∈ { ‘■’、‘□’、‘※’、‘→’、‘←’、 ‘↑’、‘↓’ } , 0≤ i≤row+1, 0≤j≤col+1, row, col≤18 } 数据关系：R = { ROW, COL } ROW = { < a i-1, j , a i, j > | a i-1, j , a i, j ∈D, i=1, … , row+1, j=0, … , col+1} COL = { < a i, j-1, a i, j > | a i, j-1 , a i, j ∈D, i=0, … , row+1, j=1, … , col+1} 基本操作： Init_hand_Maze( Maze, row, col) 初始条件：二维数组Maze[][]已存在。 迷宫求解 一．问题描述 对迷宫问题的求解过程实际就是从入口开始，一步一步地走到出口的过程。 基本要求： 输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。 二．设计思路 在本程序中用两种方法求解迷宫问题-非递归算法和递归算法。 对于非递归算法采用回溯的思想，即从入口出发，按某一方向向前探索，若能走通，并且未走过，则说明某处可以到达，即能到达新点，否则试探下一方向；若所有的方向均没有通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能到达的没一点的下标及该点前进的方向，然后通过对各个点的进出栈操作来求得迷宫通路。 对于递归算法，在当前位置按照一定的策略寻找下个位置，在下个位置又按照相同的策略寻找下下个位置…；直到当前位置就是出口点，每一步的走法都是这样的。随着一步一步的移动，求解的规模不断减小；如果起始位置是出口，说明路径找到，算法结束，如果起始位置的四个方向都走不通，说明迷宫没有路径，算法也结束。 另外，为了保证迷宫的每个点都有四个方向可以试探，简化求解 过程，将迷宫四周的值全部设为1，因此将m行n列的迷宫扩建为m+2行，n+2列，同时用数组来保存迷宫阵列。 三．数据结构设计 在迷宫阵列中每个点都有四个方向可以试探，假设当前点的坐标（x，y），与其相邻的四个点的坐标都可根据该点的相邻方位而得到，为了简化问题，方便求出新点的坐标，将从正东开始沿顺时针进行的这四个方向的坐标增量放在一个结构数组move[4]中，每个元素有两个域组成，其中x为横坐标增量，y为纵坐标增量，定义如下： typedef struct { int x,y; }item; 为到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，还要将从前一点到本点的方向压入栈中。栈中的元素由行、列、方向组成，定义如下： typedef struct { int x,y,d; }DataType; 由于在非递归算法求解迷宫的过程中用到栈，所以需定义栈的类型，本程序中用的是顺序栈，类型定义如下; typedef struct { DataType data[MAXSIZE]; int top; }SeqStack, *PSeqStack; 迷宫问题 ——王欣歆20080564 一．需求设计：以一个m*m 的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口的通道，或得出没有通路的结论。二．概要设计： 存储结构： 采用了数组以及结构体来存储数据，在探索迷宫的过程中用到的栈，属于顺序存储结构。 /*八个方向的数组表示形式*/ int move[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1, 0},{-1, 1}}; /*用结构体表示位置*/ struct position { int x,y; }; position stack[m*m+1]; 基本算法： 走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西南、西、西北、北、东北8个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果8个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。 每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。 用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,m）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。 二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的边界；第1行第1列元素和第m行第m列元素置成“0”，表示迷宫的入口和出口；其余元素值用随机函数产生。 假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有8个。 如果用二维数组move记录8个方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定： x=x+move[i][0] y=y+move[i][1] 从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。在搜索过程中，每前进一步，在所到位置处做标记“ ” （表示这个位置在通路上），并将该位置的坐标压入栈中。 每次后退的时候，先将当前所在位置处的通路标记“ ”改 成死路标记“×”（表示这个位置曾到达过但走不通，以后 不要重复进入），然后将该位置的坐标从栈顶弹出。 678 51 432 x y o 数据结构试验——迷宫问题 （一）基本问题 1.问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。 入口 出口 图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北(为了清晰，以下称“上下左右”)。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 2.数据结构设计 以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据，设置一个数组mg如下 int mg[M+2][N+2]= { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} };在算法中用到的栈采用顺序存储结构，将栈定义为 Struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一个相邻的可走的方位号 }st[MaxSize];// 定义栈 int top=-1 //初始化栈 3设计运算算法 要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。 方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、3.其增量数组move[4]如图3所示。 move[4] x y 0 -1 0 1 0 1 2 1 0 3 0 -1 图2数组move[4] 方位示意图如下： 通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di，表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。 （1）下面介绍求解迷宫（xi,yj）到终点（xe,ye）的路径的函数：先将入口进栈（其初始位置设置为—1），在栈不空时循环——取栈顶方块（不退栈）①若该方块为出口，输出所有的方块即为路径，其代码和相应解释如下： 实验报告 课程名：数据结构（C语言版）实验名：迷宫问题I 姓名： 班级： 学号： 撰写时间：2014/10/05 一实验目的与要求 1. 了解栈的应用 2. 利用栈在迷宫中找到一条路 二实验内容 ?一个迷宫如图1所示, 是由若干个方格构成的一个矩形, 其中有唯一的一个入口(用标示), 有唯一的一个出口(用△标示). 图中深色的方格无法到达, 浅色的方格都是可以到达的. 每一次只能从当前方格前进到与当前方格有公共边的方格中(因此前进方向最多有四个). ?本次实验的迷宫问题要求求解一条从入口到出口的路. 图1：迷宫 三实验结果与分析 程序： #include } } int Sx[Znum+1], Sy[Znum+1], p=0; for(i=0;i 信息工程学院 课程设计报告 课程名称《数据结构》 课题名称走迷宫游戏 专业 班级 学号 姓名 联系方式 指导教师 2015 年 12 月 27 日 目录 1、数据结构课程设计任务书............................................................... １ 1.1、题目........................................................................... １ 1.2、要求........................................................................... １ 2、总体设计............................................................................. １ 2.1、设计思路及总体组成框架......................................................... １ 2.2、操作流程图..................................................................... ２ 3、详细设计............................................................................. ５ 3.1、程序中所采用的数据结构及存储结构的说明......................................... ５ 3.2、函数功能模块说明............................................................... ５ 3.3、各函数的调用关系 ............................................................................................................................... ７ 4、调试与测试：......................................................................... ７ 4.1、调试方法与步骤：............................................................... ７ 4.2、测试结果的分析与讨论：......................................................... ８ 4.3、测试过程中遇到的主要问题及采取的解决措施：................................... １０ 6、源程序清单......................................................................... １０ 7、数据结构课程设计总结............................................................... １４ 8、参考文献........................................................................... １４ 实验报告 实验课名称：数据结构实验 实验名称：迷宫问题 班级：20130613 学号：16 姓名：施洋时间：2015-5-18 一、问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。 入口 出口 图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 二、数据结构设计 以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。根据题目中的数据，设置一个数组mg如下 int mg[M+2][N+2]= { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} };在算法中用到的栈采用顺序存储结构，将栈定义为 Struct { int i; //当前方块的行号 int j; //当前方块的列号 int di; //di是下一个相邻的可走的方位号 }st[MaxSize];// 定义栈 int top=-1 //初始化栈 三、算法设计 要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。 方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为0、1、2、3.其增量数组move[4]如图3所示。 move[4] x y 0 -1 0 1 0 1 2 1 0 3 0 -1 图2数组move[4] 方位示意图如下： 通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di，表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。 专业：计算机科学与技术 2008年10月20 日 数据结构课程设计 一、说明： 1、课程设计题目均选自《数据结构习题集》，请你根据所给页码及题目查阅相应内容，任选其一确定自己设计的题目； 2、题目一般分为基本要求和选做内容，选做内容将作为答优的基本要求； 3、课程设计的成绩分为两部分：系统演示+设计报告。 4、演示部分的检查在12教803室，在课程设计结束后一周。 5、时间：第8周周一无课时间，第8周周六、周日8:00-12:00,1:00-5:00，第9周周一无课时间。地点12教五楼机房。 二、题目： P77: 0.3-海龟作图； P80: 1.3-集合的并、交和差运算（或者1.4-长整数四则运算）； P105: 2.9-迷宫问题； P152: 5.7-表达式类型的实现； P153: 5.8-全国交通咨询模拟。 三、报告要求：完成以上实验内容并写出实验报告，报告应具有以下内容： 1、实验内容 2、概要设计 3、详细设计 4、测试数据及程序运行情况 5、实验过程中出现的问题及解决方法 6、实验体会 四、实验报告要求全部为打印稿，格式统一（见附件实验报告格式），在程序演示检查完成后一并教给老师。 五、课程设计期间有问题，请到12教803室找王永燕,周劲老师。 1、实验内容 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 【实现提示】 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通解。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可以迷宫的四周加一圈障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。 【选作内容】 （１）编写递归形式的算法，求得迷宫中所有可能的通路； 课程设计报告 课题名称：迷宫问题的求解及演示姓名： 学号： 专业：计算机与信息学院 班级： 指导教师： 数据结构课程设计任务书针对本课程设计，完成以下课程设计任务书： 1.熟悉系统实现工具和上机环境。 2.根据课程设计任务，查阅相关资料。 3.针对所选课题完成以下工作： （1）需求分析 （2）概要设计 （3）详细设计 （4）编写源程序 （5）静态走查程序和上机调试程序 4.书写上述文档和撰写课程设计报告 目录 第一部分课程设计任务书 (1) 第二部分课程设计报告 (2) 第一章课程设计内容和要求 (4) 2.1 问题描述 (4) 2.2 需求分析 (4) 第二章课程设计总体方案及分析 (4) 3.1 概要设计 (7) 3.2 详细设计 (7) 3.3 调试分析 (10) 3.4 测试结果 (10) 第三章设计总结 (13) 4.1课程设计总结 (13) 4.2参考文献………………………………………………… 4.3 附录(源代码) (14) 第二部分课程设计报告 第一章课程设计内容和要求 2.1问题描述： 迷宫以16*16的矩阵存储在数据文件中（迷宫中的障碍物要占到一定比例），编写非递归的程序，求出一条从入口到出口的路径并显示之（结果若能用C的绘图函数显示更好） 2.2需求分析： 1．要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏 幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 2.迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 3.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。 目录 摘要 .................................................................................... 错误！未定义书签。前言 . (1) 正文 (3) 1.采用类C语言定义相关的数据类型 (3) 2.各模块的伪码算法 (3) 3.搜索算法流程图 (6) 4.调试分析 (7) 5.测试结果 (7) 6.源程序（带注释） (10) 总结 (16) 参考文献 (17) 致谢 (18) 附件Ⅰ部分源程序代码 (19) 摘要 在现实生活中，会遇到很多很多关于迷宫这样很复杂、很难解决的问题的问题。如果人工去解决这些问题，会很麻烦，花很长的时间，甚至无法解决。假如用计算机去解决，可以通过手动生成迷宫，也可以通过计算机随机的产生迷宫，最终退出。而且可以很快的求解迷宫，找到从入口到出口的通路，或者当没有通路时，得出没有通路的结论。找出通路之后，会显示出通路路经，而且以图示的方式显示出通路，这样会使人一目了然的看清此迷宫的通路。迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。 关键词：迷宫；通路；二维数组；路径 前言 随着社会经济的发展，信息化程度的不断深入，传统的人工求解迷宫问题已不能满足生活的需要。近几年，随着迷宫问题越来越复杂、科技也越来越发达，人们逐渐的开始用计算机求解迷宫问题。迷宫问题很复杂，但是人们又不得不去研究这个问题，因为人们的生活中需要它，离不开它。在迷宫路径的搜索过程中，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。 数据结构栈求解迷宫问题(C语言版) /* 数据结构C语言版栈求解迷宫问题 P50-52 利用栈求解迷宫问题 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月12日 */ /***************头文件**********************/ // 迷宫坐标位置类型 typedef struct { int x; // 行值 int y; // 列值 }PosType; #define MAXLENGTH 25 // 设迷宫的最大行列为25 typedef int MazeType[MAXLENGTH][MAXLENGTH]; // 迷宫数组[行][列] typedef struct // 栈的元素类型 { int ord; // 通道块在路径上的＂序号＂ PosType seat; // 通道块在迷宫中的＂坐标位置＂ int di; // 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) }SElemType; // 全局变量 MazeType m; // 迷宫数组 int curstep=1; // 当前足迹,初值为1 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示P46 typedef struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 /****************实现************************/ // 构造一个空栈S int InitStack(SqStack *S) { // 为栈底分配一个指定大小的存储空间 (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if( !(*S).base ) exit(0); (*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE; return 1; } // 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S) { if(S.top == S.base) return 1; else return 0; } // 插入元素e为新的栈顶元素。 int Push(SqStack *S, SElemType e) { if((*S).top - (*S).base >= (*S).stacksize) // 栈满，追加存储空间{ (*S).base = (SElemType *)realloc((*S).base , ((*S).stacksize + STACKINCREMENT) * sizeof(SElemType)); if( !(*S).base ) exit(0); ##大学 数据结构课程设计报告题目：走迷宫游戏 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 2011-6-21 至 2011-6-30 指导教师: 2010—2011年度第 2 学期 一、需求分析 1 问题描述 走迷宫游戏 程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。 2 基本功能 1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2) 迷宫的墙足够结实，老鼠不能穿墙而过； 3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 5) 找出走出迷宫的所有路径，以及最短路径。 利用序列化功能实现迷宫地图文件的存盘和读出等功能 3 输入输出 输入为字符型： 1， 2， 3 分别实现功能选择 w(上),s(下),a(左),d(右)控制迷宫的走向 y表示确定 n表示否定 二、 概要设计 1. 设计思路： 实现走迷宫 game （） 对迷宫地图进行修改change （） 对修改的地图数组进行保存edit （） 对修改的地图进行保存 savemap （） 实现自动搜路 Mathpath （）对搜寻的路径进行输 出 print （） 2.数据结构设计： 采用的是栈来存储数据，进栈实际是在栈中插入三元组，出栈则只数组的个数进行操作 抽象数据类型线性表的定义如下： ADT SqStack{ 数据对象：D={a i | a i ∈SElemType,i=1,2,3……，n,n ≥0} 数据关系：R1={| a i-1,a i ∈D,i=1,2,3,……，n} 基本操作： SqStack *InitStack() 操作结果：创建一个空栈 void Push(SqStack *S,SElemType data) 初始条件：栈S 已存在 操作结果：插入一个元素，并且使数据个数加一(top++) void Pop(SqStack *S) 初始条件：栈S 已存在。 操作结果：栈中元素个数减一（top--） } 2. 软件结构设计： game （）模块 函数原型： void game(int map1[h][w])//游戏函数 { #define killtime 15 clock_t start, finish; double duration; int x=1,y=1,m=0,n=0,M,N,MAP[100][100];//x->colom y->row char cCtrl='\0'; 数据结构课程设计迷宫 问题 Document number【SA80SAB-SAA9SYT-SAATC-SA6UT-SA18】 数据结构课程设计 课程名称：数据结构 题目：迷宫设计 系别：软件学院 专业：移动设备应用开发 班级：15级移动1班 姓名：黄国峰 学期：2016-2017第一学期 指导教师：李博 时间：2016年12月 目录 第一部分需求分析 第二部分详细设计 第三部分调试分析 第四部分用户手册 第五部分测试结果 第六部分附录 第七部分参考文献 一、需求分析 1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没有这样通路的信息。 2、可以用一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。 4、手动设置迷宫是任意给定的，所以程序要能够对给定的迷宫生成对应的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。 5、自动生成的迷宫原理很简单，因为0和1分别代表通道和障碍物，所以只需要随机生成0和1然后再给最外围都赋值为1，就形成了新的迷宫。 二、详细设计 1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。 2、如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有
相关主题
文本预览