数据结构实验迷宫问题.docx
《数据结构实验迷宫问题.docx》由会员分享，可在线阅读，更多相关《数据结构实验迷宫问题.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构实验迷宫问题
实验报告
实验课名称：
数据构造实验
实验名称：
迷宫问题
班级：
20130613
学号：
16
：
施洋
时间：
2015-5-18
一、问题描述
这是心理学中的一个经典问题。
心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。
迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。
简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。
此题设置的迷宫如图1所示。
图1迷宫示意图
迷宫四周设为墙；无填充处，为可通处。
设每个点有四个可通方向，分别为东、南、西、北。
左上角为入口。
右下角为出口。
迷宫有一个入口，一个出口。
设计程序求解迷宫的一条通路。
二、数据构造设计
以一个m×n的数组mg表示迷宫，每个元素表示一个方块状态，数组元素0和1分别表示迷宫中的通路和障碍。
迷宫四周为墙，对应的迷宫数组的边界元素均为1。
根据题目中的数据，设置一个数组mg如下
intmg[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
{inti;//当前方块的行号
intj;//当前方块的列号
intdi;//di是下一个相邻的可走的方位号
}st[MaxSize];//定义栈
inttop=-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时，表示此位置一定不是通路上的点，从栈中去除。
在找到出口时，栈中保存的就是一条迷宫通路。
〔1〕下面介绍求解迷宫〔xi,yj〕到终点〔xe,ye〕的路径的函数：
先将入口进栈〔其初始位置设置为—1〕，在栈不空时循环——取栈顶方块〔不退栈〕①假设该方块为出口，输出所有的方块即为路径，其代码和相应解释如下：
intmgpath（intxi,intyi,intxe,intye）//求解路径为:
（xi,yi）->（xe,ye）
{
struct
{
inti;//当前方块的行号
intj;//当前方块的列号
intdi;//di是下一可走方位的方位号
}st[MaxSize];//定义栈
inttop=-1;//初始化栈指针
inti,j,k,di,find;
top++;//初始方块进栈
st[top].i=xi;st[top].j=yi;
st[top].di=-1;mg[1][1]=-1;
while（top>-1）//栈不空时循环
{
i=st[top].i;j=st[top].j;di=st[top].di;//取栈顶方块
if（i==xe&&j==ye）//找到了出口,输出路径
{
printf（"迷宫路径如下:
\n"）;
for（k=0;k<=top;k++）
{
printf（"\t（%d,%d）",st[k].i,st[k].j）;
if（（k+1）%5==0）//每输出每5个方块后换一行
printf（"\n"）;
}
printf（"\n"）;
return
（1）;//找到一条路径后返回1
}
②否那么，找下一个可走的相邻方块假设不存在这样的路径，说明当前的路径不可能走通，也就是恢复当前方块为0后退栈。
假设存在这样的方块，那么其方位保存在栈顶元素中，并将这个可走的相邻方块进栈〔其初始位置设置为-1〕
求迷宫回溯过程如图4所示
}
从前一个方块找到相邻可走方块之后，再从当前方块找在、相邻可走方块，假设没有这样的方快，说明当前方块不可能是从入口路径到出口路径的一个方块，那么从当前方块回溯到前一个方块，继续从前一个方块找可走的方块。
为了保证试探的可走的相邻方块不是已走路径上的方块，如〔i,j〕已经进栈，在试探〔i+1，j〕的下一方块时，又试探道〔i，j〕，这样会很悲剧的引起死循环，为此，在一个方块进栈后，将对应的mg数组元素的值改为-1〔变为不可走的相邻方块〕，当退栈时〔表示该方块没有相邻的可走方块〕，将其值恢复0，其算法代码和相应的解释如下：
find=0;
while（di<4&&find==0）//找下一个可走方块
{
di++;
switch（di）
{
case0:
i=st[top].i-1;j=st[top].j;break;
case1:
i=st[top].i;j=st[top].j+1;break;
case2:
i=st[top].i+1;j=st[top].j;break;
case3:
i=st[top].i,j=st[top].j-1;break;
}
if（mg[i][j]==0）find=1;//找到下一个可走相邻方块
}
if（find==1）//找到了下一个可走方块
{
st[top].di=di;//修改原栈顶元素的di值
top++;//下一个可走方块进栈
st[top].i=i;st[top].j=j;st[top].di=-1;
mg[i][j]=-1;//防止重复走到该方块
}
else//没有路径可走,那么退栈
{
mg[st[top].i][st[top].j]=0;//让该位置变为其他路径可走方块
top--;//将该方块退栈
}
}
return（0）;//表示没有可走路径,返回0
〔2〕求解主程序
建立主函数调用上面的算法，将mg和st栈指针定义为全局变量
voidmain（）
{
mgpath（1,1,M,N）;
四、界面设计
设计很简单的界面，输出路径。
五、运行测试与分析
图5.根本运行结果
六、实验收获与思考
思考：
8个方向的问题
1.设计思想
（1）设置一个迷宫节点的数据构造。
（2）建立迷宫图形。
（3）对迷宫进展处理找出一条从入口点到出口点的路径。
（4）输出该路径。
（5）打印通路迷宫图。
当迷宫采用二维数组表示时，老鼠在迷宫任一时刻的位置可由数组的行列序号i，j来表示。
而从[i],[j]位置出发可能进展的方向见下列图7.如果[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]中〔见图8〕。
该数组的每个分量有两个域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
图7方向位移图图8向量差图
为了防止重走原路，我们规定对已经走过的位置，将原值为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个方向上都堵塞，那么退回一步，继续探测，如果已经退到迷宫的入口〔栈中无元素〕，那么表示此迷宫无路径可通行。
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.算法流程图：
4.程序代码：
#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）;//绘制作出通路标记的迷宫
}
5.运行结果
收获:
这次试验总体来说还是比拟简单的，因为几个思考问题都是在根本问题的源代码上进展改良和补充。
有了第一次数据构造编程和测试的经历，这次试验减少了很多困难，相对来说容易多了。
这次实验让我对栈和队列有了更好的理解和运用。
教师评分：
教师签字：
升级会员 