数据结构实验-迷宫问题汇总

1、实验报告实验课名称：数据结构实验实验名称：迷宫问题姓名：施洋时间：2015-5-18班级：20130613学号：16一、问题描述这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。入图1迷宫示意图迷宫为可通处。设每个点有四个可通方向，分别为东、右下角为出四周设为墙；无填充处，南、口。迷宫有一个入口，一个出口。设计西、北。左上角为入口。程序求解迷宫的一条通路。二、数据结构设计以

2、一个mKn的数组mg表示迷宫，每个元素表示一个方块状态，数组元素。和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为lo根据题目中的数据,设置一个数组mg如卜intmgM+2N+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:在算法中用到的栈采用顺序存储结构，将栈定义为Structinti;/当前方块的行号intj；intdi;当前方块的列号distMaxSize;是下一个相邻的可走的方位号定义栈inttop-l初始化栈、算

3、法设计要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为。、1、2、3.其增量数组move如图3所

4、示。moveE401图2数组move4Ci-lJ）方位0方位1方位示意图如下:（i + U J> 方 位2图3,方位图通路：通路上的每一个点有3个属性：一个横坐标属性i、一个列坐标属性j和一个方向属性di,表示其下一点的位置。如果约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di值增1,当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。下面介绍求解迷宫（xi,yj）到终点（xe,ye）的路径的函数：先将入口进栈（其初始位置设置为-1），在栈不空时循环一一取栈顶方块（不退栈）若该方块为出口，输出所有的方块即为路径，其

5、代码和相应解释如下：int mgp ath(i nt xi, i nt yi, i nt xe, i nt ye) 为：(xi,yi)->(xe, ye)(struct(int i;int j;int di; stMaxSizeJ;int top=l;int i, j, k, di, f i nd;top+;st to p.i=xi;stEt op L j=yi;st to p.while (to p>-l)/求解路径当前方块的行号当前方块的列号di是下一可走方位的方位号定义栈初始化栉指针初始方块进栈栈不空时循环i=sttop.i;j=stEtop.j;di=sttop.di;/取

6、栈顶方块if(i=xe&&j=ye)/找到了出口，输出路径(printf迷宫路径如下:n");for(k=0;k<=top;k+)(printf("t(%d,/d)”,stk.i,stk.j);if(k+l)%5=0)/每输出每5个方块后换一行printf("n");printf("n");return(1);找到一条路径后返回1否则，找下一个可走的相邻方块若不存在这样的路径，说明当前的路径不可能走通，也就是恢复当前方块为。后退栈。若存在这样的方块，则其方位保存在栈顶元素中，并将这个可走的相邻方块进栈（其初始位置

7、设置为T）求迷宫回溯过程如图4所示的一个方块当前方块(itj)回用没找到维婪直找耳fe路侨图斗,堆宫回罔过;程示意图相邻可走方块，若没有这样则从当前方块回溯到前i,j)已经进栈，在试探从前一个方块找到相邻可走方块之后，再从当前方块找在、的方快，说明当前方块不可能是从入口路径到出口路径的一个方块，一个方find=0;while(di<4&&find=0)di+;switch(di)case0:i=sttop.i-1;j=sttop.j;break;casel:i=sttop.i;j=sttop,j+l;bre强找下一个可走方块case2:i=sttop.i+1;j=stto

8、p.j;break;case3:i=sttop.i,j=sttop.j-1;break;找到下一个可走相邻方块if(find=l)sttopdi=di;top+;修改原栈顶元素的di值块，继续从前一个方块找可走的方块。为了保证试探的可走的相邻方块不是已走路径上的方块，如（i+1,j）的下一方块时，又试探道（i,j），这样会很悲剧的引起死循环，为此，在一个方块进栈后，将对应的mg数组元素的值改为（变为不可走的相邻方块），当退栈时（表示该方块没有相邻的可走方块），将其值恢复。，其算法代码和相应的解释如下：sttop.i=i;sttop.j=j;sttop.di=-l;mgij=-l；/避免重复走到

9、该方块）else没有路径可走，则退栈mgLstEtop.isttop.j=0;/让该位置变为其他路径可走方块toP一一；将该方块退栈)return(O);表示没有可走路径,返回0(2)求解主程序建立主函数调用上面的算法，将1ng和st栈指针定义为全局变量voidmain()mgpath(l,LM,N);四、界面设计设计很简单的界面，输出路径。五、运行测试与分析图5.基本运行结果六、实验收获与思考思考：8个方向的问题1设计思想设置一个迷宫节点的数据结构。建立迷宫图形。对迷宫进行处理找出一条从入口点到出口点的路径。输出该路径。打印通路迷宫图。初始化迷宫结束图6功能结构图当迷宫采用二维数组表示时，老

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

11、题，规定田,5的下一步位置的坐标是区,日，并将这8个方位伤的x和y坐标的增量预先放在一个结构数组move同中（见图8）。该数组的每个分量有两个域dx和dy。例如要向东走，只要在j值上加上dy,就可以得到下一步位置的,y值为Jj+dyo于是搜索方向的变化只要令方向值dir从。增至7,便可以从move数组中得到从田,卬点出发搜索到的每一个相邻点田,5。x=i+moveEdir.dx0-22220<20<44小 2-b,图7方向位移图图8向量差图为了防止重走原路，我们规定对已经走过的位置，将原值为。改为-1,这既可以区别该位置是否已经走到过，又可以与边界值1相区别。当整个搜索过程结束后可

12、以将所有的改回到0,从而恢复迷宫原样。这样计算机走迷宫的方法是：采取一步一步试探的方法。每一步都从（E）开始，按顺时针对8个方向进行探测，若某个方位上的mazex,y二0,表示可以通行，则走一步；若maze氐Jykl,表示此方向不可通行须换方向再试。直至个方向都试过，mazex,y均为1说明此步已无路可走，需退回一步，在上一步的下一个方向重新dir) o开始探测。为此需要设置一个栈，用来记录所走过的位置和方向（一当退回一步时，就从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到一个行进方向，则把当前位置和新的方向重新进栈，并走到新的位置。如果探测到x二m,y=n,则已经到达迷宫的

13、出口，可以停止检测，输出存在栈中的路径；若在某一位置的8个方向上都堵塞，则退回一步，继续探测，如果已经退到迷宫的入口（栈中无元素），则表示此迷宫无路径可通行。2系统算法（伪代码描述）：建立迷宫节点的结构类型stack口。入迷宫图形。表示可以通1表示不可以通。用二维数组mazem+2n+2进行存储。数组四周用I表示墙壁，其中入口点（1，1）与出口点（m.n）固定。函数Path（）对迷宫进行处理，从入口开始：WhileC!（s->top=-l）&&（dir>=7）11（x=M）&&（y=N）&&（maze-y=T）For（扫描八个可以走的

14、方向）If（找到一个可以走的方向）进入栈标志在当前点可以找到一个可以走的方向避免重复选择mazeLxy="l不再对当前节点扫描f（八个方向已经被全部扫描过，无可以通的路）标志当前节点没有往前的路后退一个节点搜索If（找到了目的地）输出路径退出循环未找到路径输出从入口点到出口点的一条路径O(5)输出标行通路的迷官图。3算法流程图:图9算法流程图开始b.4.程序代码:#defineM212/*M2*N2为实际使川迷宫数组的大小7#defineN211?definemaxlenM2/栈长度# include<stdio.h># include<iostream.h>

15、# include<malloc.h>intM=M2-2,N=N2-2;/M*N迷宫的大小typedefstruct定义栈元素的类型(intx,y,dir;Jelemtype;typedefstruct/定义顺序栈(elemtypestackmaxlen;inttop;Jsqstktp;structmoved定义方向位移数组的元素类型对于存储坐标增量的方向位移数组intdx,dy;/voidinimaze(intmazeN2)/初始化迷宫inti,j,num;for(i：0,j=0;i+)设置迷宫边界mazetifor(i=0,j=O;j<=N+l;j+)mazeij=l;f

16、or(i=M+l,j=0;j<=N+l;j+)mazetij=l;cout<X"原始迷宫为：*«endl;for(i=l;i<=M;i+)for(j=l;j<=N;j+)num=(800*(i+j)+1500)%327;/根据MN的值产生迷宫if(num<150)&&(i!=Mj!=N)mazetij=l;elsemazetij=0;cout«mazei"；"显示迷宫cout«endl;)cout«endl;. 1 dx=l;moveLlJ. dy=l;/*初始化栈*/*i ni

17、stack*/voidinimove(structmovedmove)/初始化方|口J位移数组/依次为East9Southeast>south，southwest>west，northwestsnorth，northeastmove0.dx=0;move0.dy=l;movemove2.dx=l;move2.dy=O;move3.dx=l;move3.dy=-l;move4.dx=0;move4.dy=-l;move5.dx=-l;move5.dy-=l;move6dx=-l;move6.dy=0;move7.dx=-l;move7.dy=l;/voidinistack(sqstk

18、tp*s)(s->top=-l;intpush(sqstktp*s,elemtypex)(if(s->top=maxlen-1)return(false);elses-stack+s->top=x;/*栈不满，执行入栈操作*/return(true);)/*push*/elemtypepop(sqstktp*s)/*栈顶兀素出栈*/elemtypeelem;if(s->top<0)如果栈空，返回空值elem.x=NULL;elem.y=NULL;elem.dir=XULL;return(elem);elses->top-;return(s->stack

19、s->top+1);栈不空，返回栈顶元素/pop寻找迷宫中的一条通路/voidpath(intmazelN2,structmovedmoveLl,sqstktp*s)inti,j,dir,x,y,f;elemtypeelem;设为入口处i=l;j=l;dir=O;mazeLlx=i+movedir.dx;/球F-*步可仃的到达点的坐标产j+movedir.dy;if(mazeLxy=0)elem.x=i;elem.y=j;elem.dir=dir;f=Push(s,elem);如果可行将数据入栈if(f=false)如果返回假，说明栈容量不足cout«栈长不足"；i=

20、x;j=y;dir=O;mazexy=-l;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=-l)&&(dir>=7)i(x=M)&&(y=N)&&(mazexy=-l);if(s->top=T)若是入口，则7循环无通路COUt«此迷宫不通”;elseelem.x=x;elem.y=y;elem.dir=dir;/将出口坐标入栈f=push(s,ele

21、m);cout<<"迷宫通路是："<<endl;while(i<=s->top)(cout«(«s->stacki.x«","<<s->stacki.y<<")"显不迷宫通路if(i!=s->top)cout«z,一>”;if(i+l)%4=0)cout«endl;i+;IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIvoiddraw(intmazeN2rsqstktp*s)/在迷宫中绘制出通路cou