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

2、路。二、數據結構設計以一個 m n 的數組 mg表示迷宮，每個元素表示一個方塊狀態(tài)，數組元素 0 和 1 分別表示迷宮中的通路和障礙。迷宮四周為墻，對應的迷宮數組的邊界元素均為1。根據題目中的數據，設置一個數組 mg如下int mgM+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; 在算法中用到的棧采用順序存儲結構，將棧定義為Struct當前方塊的行號 int i; /int j; /int di; /distMaxSize;/int to

3、p=-1/當前方塊的列號是下一個相鄰的可走的方位號定義棧初始化棧三、算法設計要尋找一條通過迷宮的路徑， 就必須進行試探性搜索， 只要有路可走就前進一步，無路可進，換一個方向進行嘗試； 當所有方向均不可走時， 則沿原路退回一步 （稱為回溯），重新選擇未走過可走的路，如此繼續(xù)，直至到達出口或返回入口（沒有通路）。在探索前進路徑時，需要將搜索的蹤跡記錄下來，以便走不通時，可沿原路返回到前一個點換一個方向再進行新的探索。 后退的嘗試路徑與前進路徑正好相反，因此可以借用一個棧來記錄前進路徑。方向：每一個可通點有 4 個可嘗試的方向，向不同的方向前進時，目的地的坐標不同。預先把 4 個方向上的位移存在一個

4、數組中。如把上、右、下、左（即順時針方向）依次編號為 0、1、2、3. 其增量數組 move4 如圖 3 所示。move4x y0-101 1 00 2 1-130圖 2 數組 move4方位示意圖如下：通路：通路上的每一個點有 3 個屬性：一個橫坐標屬性 i 、一個列坐標屬性 j 和一個方向屬性 di ，表示其下一點的位置。如果約定嘗試的順序為上、右、下、左（即順時針方向），則每嘗試一個方向不通時， di 值增 1，當 d 增至 4 時，表示此位置一定不是通路上的點， 從棧中去除。 在找到出口時， 棧中保存的就是一條迷宮通路。（ 1）下面介紹求解迷宮（ xi,yj ）到終點（ xe,ye ）

5、的路徑的函數：先將入口進棧（其初始位置設置為 1），在棧不空時循環(huán)取棧頂方塊（不退棧）若該方塊為出口，輸出所有的方塊即為路徑，其代碼和相應解釋如下：int mgpath(int xi,int yi,int xe,int ye) /求解路徑為 :(xi,yi)-(xe,ye)structint i;/當前方塊的行號int j;/當前方塊的列號int di;/di是下一可走方位的方位號 stMaxSize;/定義棧int top=-1;/初始化棧指針int i,j,k,di,find;top+;/初始方塊進棧sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1;whi

6、le (top-1)/棧不空時循環(huán)i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe & j=ye) /找到了出口, 輸出路徑牰湩晴尨迷宮路徑如下 :n);for (k=0;k=top;k+)printf(%d,%d),stk.i,stk.j);if (k+1)%5=0) /每輸出每 5 個方塊后換一行printf();printf();return(1); /找到一條路徑后返回1否則，找下一個可走的相鄰方塊若不存在這樣的路徑，說明當前的路徑不可能走通，也就是恢復當前方塊為 0 后退棧。若存在這樣的方塊，則其方位保存在棧頂元素中，并將這個可走的相鄰方

7、塊進棧（其初始位置設置為-1 ）求迷宮回溯過程如圖4 所示從前一個方塊找到相鄰可走方塊之后，再從當前方塊找在、相鄰可走方塊，若沒有這樣的方快，說明當前方塊不可能是從入口路徑到出口路徑的一個方塊，則從當前方塊回溯到前一個方塊，繼續(xù)從前一個方塊找可走的方塊。為了保證試探的可走的相鄰方塊不是已走路徑上的方塊，如（ i,j ）已經進棧， 在試探（ i+1 ，j ）的下一方塊時，又試探道（i， j），這樣會很悲劇的引起死循環(huán)，為此，在一個方塊進棧后，將對應的mg 數組元素的值改為-1（變?yōu)椴豢勺叩南噜彿綁K），當退棧時（表示該方塊沒有相鄰的可走方塊） ，將其值恢復0，其算法代碼和相應的解釋如下：find=

8、0;while (ditop=-1)&(dir=7)|(x=M)&(y=N)&(mazexy=-1)For(掃描八個可以走的方向)If( 找到一個可以走的方向)進入棧標志在當前點可以找到一個可以走的方向避免重復選擇 mazexy= -1不再對當前節(jié)點掃描If( 八個方向已經被全部掃描過，無可以通的路)標志當前節(jié)點沒有往前的路后退一個節(jié)點搜索If( 找到了目的地 )輸出路徑退出循環(huán)未找到路徑(4)輸出從入口點到出口點的一條路徑。(5)輸出標有通路的迷宮圖。3.算法流程圖：開始初始化迷宮，顯示迷宮初始化方向位移數組尋找迷宮中的一條出路dir=7 或棧空While 棧不空且dir7do1 為出口，設

9、1FFIf mazexy=0elseIfT T該點數據入棧dir+回退一步 出口或入口顯示通路結束圖 9 算法流程圖4.程序代碼：*/為實際使用迷宮數組的大小#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;struc

10、t moved/定義方向位移數組的元素類型對于存儲坐標增量的方向位移數組move int dx,dy;/void inimaze(int mazeN2)/初始化迷宮int i,j,num;for(i=0,j=0;i=M+1;i+)/設置迷宮邊界mazeij=1;for(i=0,j=0;j=N+1;j+)mazeij=1;for(i=M+1,j=0;j=N+1;j+)mazeij=1;潣瑵 ?原始迷宮為：endl;for(i=1;i=M;i+)for (j=1;j=N;j+)num=(800*(i+j)+1500) % 327;/根據 MN 的值產生迷宮if (num150)&(i!=M|j!=

11、N)mazeij=1;elsemazeij=0;coutmazeij;/ 顯示迷宮coutendl;couttop= -1;int push(sqstktp*s,elemtype x)/*inistack*/if(s -top=maxlen -1)return(false);elses-stack+s -top=x;/* 棧不滿，執(zhí)行入棧操作*/return(true);/*push*/elemtype pop(sqstktp *s)/* 棧頂元素出棧*/elemtype elem;if(s -toptop - ;return(s -stacks -top+1);/棧不空，返回棧頂元素 /po

12、p/尋找迷宮中的一條通路/void path(int mazeN2,struct moved move,sqstktp *s)int i,j,dir,x,y,f;elemtype elem;i=1;j=1;dir=0;maze11= -1;/ 設 11 為入口處dox=i+movedir.dx;/球下一步可行的到達點的坐標y=j+movedir.dy;if(mazexy=0)elem.x=i;elem.y=j;elem.dir=dir;f=push(s,elem);/ 如果可行將數據入棧if(f=false)/ 如果返回假，說明棧容量不足潣瑵 ?棧長不足 ;i=x;j=y;dir=0;maze

13、xy=-1;elseif (dir top= -1)&(dir=7)|(x=M)&(y=N)&(mazexy= -1); / 循環(huán) if(s -top= -1)/ 若是入口，則無通路潣瑵 ?此迷宮不通;elseelem.x=x;elem.y=y;elem.dir=dir;/ 將出口坐標入棧f=push(s,elem);潣瑵 ?迷宮通路是：endl;i=0;while (i top)cout(stacki.x,stacki.ytop)cout;if(i+1)%4=0)coutendl;i+;/void draw(int mazeN2,sqstktp *s)/在迷宮中繪制出通路潣瑵 ?逃逸路線為：

14、 endl;int i,j;elemtype elem;for(i=1;i=M;i+)/ 將迷宮中全部的-1 值回復為0 值for(j=1;jtop -1)/ 根據棧中元素的坐標，將通路的各個點的值改為8elem=pop(s);i=elem.x;j=elem.y;mazeij=8;for(i=1;i=M;i+)for(j=1;j=N;j+)printf(=,mazeij);/顯示已標記通路的迷宮coutendl;void main()/ 尋找迷宮通路程序sqstktp *s;int mazeM2N2;struct moved move8;inimaze(maze); /初始化迷宮數組 s=(sqstktp *)malloc(sizeof(sqstktp);初始化棧