數(shù)據(jù)結(jié)構(gòu)實驗-迷宮問題匯總

1、實驗報告實驗課名稱：數(shù)據(jù)結(jié)構(gòu)實驗實驗名稱：迷宮問題姓名：施洋時間：2015-5-18班級：20130613學號：16一、問題描述這是心理學中的一個經(jīng)典問題。心理學家把一只老鼠從一個無頂蓋的大盒子的入口處放入，讓老鼠自行找到出口出來。迷宮中設置很多障礙阻止老鼠前行，迷宮唯一的出口處放有一塊奶酪，吸引老鼠找到出口。簡而言之，迷宮問題是解決從布置了許多障礙的通道中尋找出路的問題。本題設置的迷宮如圖1所示。入圖1迷宮示意圖迷宮為可通處。設每個點有四個可通方向，分別為東、右下角為出四周設為墻；無填充處，南、口。迷宮有一個入口，一個出口。設計西、北。左上角為入口。程序求解迷宮的一條通路。二、數(shù)據(jù)結(jié)構(gòu)設計以

2、一個mKn的數(shù)組mg表示迷宮，每個元素表示一個方塊狀態(tài)，數(shù)組元素。和1分別表示迷宮中的通路和障礙。迷宮四周為墻，對應的迷宮數(shù)組的邊界元素均為lo根據(jù)題目中的數(shù)據(jù),設置一個數(shù)組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:在算法中用到的棧采用順序存儲結(jié)構(gòu)，將棧定義為Structinti;/當前方塊的行號intj；intdi;當前方塊的列號distMaxSize;是下一個相鄰的可走的方位號定義棧inttop-l初始化棧、算

3、法設計要尋找一條通過迷宮的路徑，就必須進行試探性搜索，只要有路可走就前進步，無路可進，換一個方向進行嘗試；當所有方向均不可走時，則沿原路退回步（稱為回溯），重新選擇未走過可走的路，如此繼續(xù)，直至到達出口或返回入口（沒有通路）。在探索前進路徑時，需要將搜索的蹤跡記錄下來，以便走不通時，可沿原路返回到前一個點換一個方向再進行新的探索。后退的嘗試路徑與前進路徑正好相反，因此可以借用一個棧來記錄前進路徑。方向：每一個可通點有4個可嘗試的方向，向不同的方向前進時，目的地的坐標不同。預先把4個方向上的位移存在一個數(shù)組中。如把上、右、下、左（即順時針方向）依次編號為。、1、2、3.其增量數(shù)組move如圖3所

4、示。moveE401圖2數(shù)組move4Ci-lJ）方位0方位1方位示意圖如下:（i + U J> 方 位2圖3,方位圖通路：通路上的每一個點有3個屬性：一個橫坐標屬性i、一個列坐標屬性j和一個方向?qū)傩詃i,表示其下一點的位置。如果約定嘗試的順序為上、右、下、左（即順時針方向），則每嘗試一個方向不通時，di值增1,當d增至4時，表示此位置一定不是通路上的點，從棧中去除。在找到出口時，棧中保存的就是一條迷宮通路。下面介紹求解迷宮（xi,yj）到終點（xe,ye）的路徑的函數(shù)：先將入口進棧（其初始位置設置為-1），在棧不空時循環(huán)一一取棧頂方塊（不退棧）若該方塊為出口，輸出所有的方塊即為路徑，其

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是下一可走方位的方位號定義棧初始化櫛指針初始方塊進棧棧不空時循環(huán)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)已經(jīng)進棧，在試探從前一個方塊找到相鄰可走方塊之后，再從當前方塊找在、的方快，說明當前方塊不可能是從入口路徑到出口路徑的一個方塊，一個方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值塊，繼續(xù)從前一個方塊找可走的方塊。為了保證試探的可走的相鄰方塊不是已走路徑上的方塊，如（i+1,j）的下一方塊時，又試探道（i,j），這樣會很悲劇的引起死循環(huán)，為此，在一個方塊進棧后，將對應的mg數(shù)組元素的值改為（變?yōu)椴豢勺叩南噜彿綁K），當退棧時（表示該方塊沒有相鄰的可走方塊），將其值恢復。，其算法代碼和相應的解釋如下：sttop.i=i;sttop.j=j;sttop.di=-l;mgij=-l；/避免重復走到

9、該方塊）else沒有路徑可走，則退棧mgLstEtop.isttop.j=0;/讓該位置變?yōu)槠渌窂娇勺叻綁KtoP一一；將該方塊退棧)return(O);表示沒有可走路徑,返回0(2)求解主程序建立主函數(shù)調(diào)用上面的算法，將1ng和st棧指針定義為全局變量voidmain()mgpath(l,LM,N);四、界面設計設計很簡單的界面，輸出路徑。五、運行測試與分析圖5.基本運行結(jié)果六、實驗收獲與思考思考：8個方向的問題1設計思想設置一個迷宮節(jié)點的數(shù)據(jù)結(jié)構(gòu)。建立迷宮圖形。對迷宮進行處理找出一條從入口點到出口點的路徑。輸出該路徑。打印通路迷宮圖。初始化迷宮結(jié)束圖6功能結(jié)構(gòu)圖當迷宮采用二維數(shù)組表示時，老

10、鼠在迷宮任一時刻的位置可由數(shù)組的行列序7.如果，周圍的位均為。值,號i,j來表示。而從，位置出發(fā)可能進行的方向見下圖則老鼠可以選擇這8個位置中的任一個作為它的下一位置。將這個方向分別記作：E（東八SE（東南）、S（南）SW（西南）W（西八NW（西北）、N（北）和NE（東北）。但是并非每一個位置都有8個相鄰位置。如果,j位于邊界上，即或i二m,或尸1，或Fn,則相鄰位置可能是3個或5個為了避免檢查邊界條件，將數(shù)組四周圍用值為1的邊框包圍起來，這樣二維數(shù)組maze應該聲明為mazem+2,n+2在迷宮行進時，可能有多個行進方向可選，我們可以規(guī)定方向搜索的次序是從東（E）沿順時針方向進行。為了簡化問

11、題，規(guī)定田,5的下一步位置的坐標是區(qū),日，并將這8個方位傷的x和y坐標的增量預先放在一個結(jié)構(gòu)數(shù)組move同中（見圖8）。該數(shù)組的每個分量有兩個域dx和dy。例如要向東走，只要在j值上加上dy,就可以得到下一步位置的,y值為Jj+dyo于是搜索方向的變化只要令方向值dir從。增至7,便可以從move數(shù)組中得到從田,卬點出發(fā)搜索到的每一個相鄰點田,5。x=i+moveEdir.dx0-22220<20<44小 2-b,圖7方向位移圖圖8向量差圖為了防止重走原路，我們規(guī)定對已經(jīng)走過的位置，將原值為。改為-1,這既可以區(qū)別該位置是否已經(jīng)走到過，又可以與邊界值1相區(qū)別。當整個搜索過程結(jié)束后可

12、以將所有的改回到0,從而恢復迷宮原樣。這樣計算機走迷宮的方法是：采取一步一步試探的方法。每一步都從（E）開始，按順時針對8個方向進行探測，若某個方位上的mazex,y二0,表示可以通行，則走一步；若maze氐Jykl,表示此方向不可通行須換方向再試。直至個方向都試過，mazex,y均為1說明此步已無路可走，需退回一步，在上一步的下一個方向重新dir) o開始探測。為此需要設置一個棧，用來記錄所走過的位置和方向（一當退回一步時，就從棧中退出一個元素，以便在上一個位置的下一個方向上探測，如又找到一個行進方向，則把當前位置和新的方向重新進棧，并走到新的位置。如果探測到x二m,y=n,則已經(jīng)到達迷宮的

13、出口，可以停止檢測，輸出存在棧中的路徑；若在某一位置的8個方向上都堵塞，則退回一步，繼續(xù)探測，如果已經(jīng)退到迷宮的入口（棧中無元素），則表示此迷宮無路徑可通行。2系統(tǒng)算法（偽代碼描述）：建立迷宮節(jié)點的結(jié)構(gòu)類型stack口。入迷宮圖形。表示可以通1表示不可以通。用二維數(shù)組mazem+2n+2進行存儲。數(shù)組四周用I表示墻壁，其中入口點（1，1）與出口點（m.n）固定。函數(shù)Path（）對迷宮進行處理，從入口開始：WhileC!（s->top=-l）&&（dir>=7）11（x=M）&&（y=N）&&（maze-y=T）For（掃描八個可以走的

14、方向）If（找到一個可以走的方向）進入棧標志在當前點可以找到一個可以走的方向避免重復選擇mazeLxy="l不再對當前節(jié)點掃描f（八個方向已經(jīng)被全部掃描過，無可以通的路）標志當前節(jié)點沒有往前的路后退一個節(jié)點搜索If（找到了目的地）輸出路徑退出循環(huán)未找到路徑輸出從入口點到出口點的一條路徑O(5)輸出標行通路的迷官圖。3算法流程圖:圖9算法流程圖開始b.4.程序代碼:#defineM212/*M2*N2為實際使川迷宮數(shù)組的大小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定義方向位移數(shù)組的元素類型對于存儲坐標增量的方向位移數(shù)組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;/根據(jù)MN的值產(chǎn)生迷宮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位移數(shù)組/依次為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;/*棧不滿，執(zhí)行入棧操作*/return(true);)/*push*/elemtypepop(sqstktp*s)/*棧頂兀素出棧*/elemtypeelem;if(s->top<0)如果?？眨祷乜罩礶lem.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-*步可仃的到達點的坐標產(chǎn)j+movedir.dy;if(mazeLxy=0)elem.x=i;elem.y=j;elem.dir=dir;f=Push(s,elem);如果可行將數(shù)據(jù)入棧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循環(huán)無通路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