.數(shù)據(jù)結(jié)構(gòu)試驗迷宮問題（一）基本問題1.問題描述這是心理學(xué)中的一個經(jīng)典問題。心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口處放入，讓老鼠自行找到出口出來。迷宮中設(shè)置很多障礙阻止老鼠前行，迷宮唯一的出口處放有一塊奶酪，吸引老鼠找到出口。簡而言之，迷宮問題是解決從布置了許多障礙的通道中尋找出路的問題。本題設(shè)置的迷宮如圖1所示。圖1 迷宮示意圖迷宮四周設(shè)為墻；無填充處，為可通處。設(shè)每個點有四個可通方向，分別為東、南、西、北(為了清晰，以下稱“上下左右”)。左上角為入口。右下角為出口。迷宮有一個入口，一個出口。設(shè)計程序求解迷宮的一條通路。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計以一個mn的數(shù)組mg表示迷宮，每個元素表示一個方塊狀態(tài)，數(shù)組元素0和1分別表示迷宮中的通路和障礙。迷宮四周為墻，對應(yīng)的迷宮數(shù)組的邊界元素均為1。根據(jù)題目中的數(shù)據(jù)，設(shè)置一個數(shù)組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;在算法中用到的棧采用順序存儲結(jié)構(gòu)，將棧定義為Struct int i; /當(dāng)前方塊的行號 int j; /當(dāng)前方塊的列號 int di; /di是下一個相鄰的可走的方位號stMaxSize;/ 定義棧int top=-1 /初始化棧3設(shè)計運算算法要尋找一條通過迷宮的路徑，就必須進(jìn)行試探性搜索，只要有路可走就前進(jìn)一步，無路可進(jìn)，換一個方向進(jìn)行嘗試；當(dāng)所有方向均不可走時，則沿原路退回一步（稱為回溯），重新選擇未走過可走的路，如此繼續(xù)，直至到達(dá)出口或返回入口（沒有通路）。在探索前進(jìn)路徑時，需要將搜索的蹤跡記錄下來，以便走不通時，可沿原路返回到前一個點換一個方向再進(jìn)行新的探索。后退的嘗試路徑與前進(jìn)路徑正好相反，因此可以借用一個棧來記錄前進(jìn)路徑。方向：每一個可通點有4個可嘗試的方向，向不同的方向前進(jìn)時，目的地的坐標(biāo)不同。預(yù)先把4個方向上的位移存在一個數(shù)組中。如把上、右、下、左（即順時針方向）依次編號為0、1、2、3.其增量數(shù)組move4如圖3所示。move4xy0-1010121030-1圖2數(shù)組move4方位示意圖如下： 通路：通路上的每一個點有3個屬性：一個橫坐標(biāo)屬性i、一個列坐標(biāo)屬性j和一個方向?qū)傩詃i，表示其下一點的位置。如果約定嘗試的順序為上、右、下、左（即順時針方向），則每嘗試一個方向不通時，di值增1，當(dāng)d增至4時，表示此位置一定不是通路上的點，從棧中去除。在找到出口時，棧中保存的就是一條迷宮通路。（1）下面介紹求解迷宮（xi,yj）到終點（xe,ye）的路徑的函數(shù)：先將入口進(jìn)棧（其初始位置設(shè)置為1），在棧不空時循環(huán)取棧頂方塊（不退棧）若該方塊為出口，輸出所有的方塊即為路徑，其代碼和相應(yīng)解釋如下：int mgpath(int xi,int yi,int xe,int ye)/求解路徑為:(xi,yi)->(xe,ye)struct int i;/當(dāng)前方塊的行號int j;/當(dāng)前方塊的列號int di;/di是下一可走方位的方位號 stMaxSize;/定義棧int top=-1;/初始化棧指針int i,j,k,di,find;top+; /初始方塊進(jìn)棧sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1; while (top>-1)/棧不空時循環(huán)i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe && j=ye)/找到了出口,輸出路徑 printf("迷宮路徑如下:n");for (k=0;k<=top;k+)printf("t(%d,%d)",stk.i,stk.j);if (k+1)%5=0)/每輸出每5個方塊后換一行printf("n"); printf("n");return(1);/找到一條路徑后返回1否則，找下一個可走的相鄰方塊若不存在這樣的路徑，說明當(dāng)前的路徑不可能走通，也就是恢復(fù)當(dāng)前方塊為0后退棧。若存在這樣的方塊，則其方位保存在棧頂元素中，并將這個可走的相鄰方塊進(jìn)棧（其初始位置設(shè)置為-1） 求迷宮回溯過程如圖4所示從前一個方塊找到相鄰可走方塊之后，再從當(dāng)前方塊找在、相鄰可走方塊，若沒有這樣的方快，說明當(dāng)前方塊不可能是從入口路徑到出口路徑的一個方塊，則從當(dāng)前方塊回溯到前一個方塊，繼續(xù)從前一個方塊找可走的方塊。 為了保證試探的可走的相鄰方塊不是已走路徑上的方塊，如（i,j）已經(jīng)進(jìn)棧，在試探（i+1，j）的下一方塊時，又試探道（i，j），這樣會很悲劇的引起死循環(huán)，為此，在一個方塊進(jìn)棧后，將對應(yīng)的mg數(shù)組元素的值改為-1（變?yōu)椴豢勺叩南噜彿綁K），當(dāng)退棧時（表示該方塊沒有相鄰的可走方塊），將其值恢復(fù)0，其算法代碼和相應(yīng)的解釋如下：find=0;while (di<4 && find=0)/找下一個可走方塊di+;switch(di)case 0:i=sttop.i-1;j=sttop.j;break;case 1:i=sttop.i;j=sttop.j+1;break;case 2:i=sttop.i+1;j=sttop.j;break;case 3:i=sttop.i,j=sttop.j-1;break;if (mgij=0) find=1;/找到下一個可走相鄰方塊if (find=1)/找到了下一個可走方塊sttop.di=di;/修改原棧頂元素的di值top+;/下一個可走方塊進(jìn)棧sttop.i=i;sttop.j=j;sttop.di=-1;mgij=-1;/避免重復(fù)走到該方塊else/沒有路徑可走,則退棧mgsttop.isttop.j=0;/讓該位置變?yōu)槠渌窂娇勺叻綁Ktop-;/將該方塊退棧return(0);/表示沒有可走路徑,返回0（2）求解主程序 建立主函數(shù)調(diào)用上面的算法，將mg和st棧指針定義為全局變量void main()mgpath(1,1,M,N);3界面設(shè)計設(shè)計很簡單的界面，輸出路徑4運行結(jié)果圖5。基本運行結(jié)果（二）8個方向的問題 1.設(shè)計思想(1)設(shè)置一個迷宮節(jié)點的數(shù)據(jù)結(jié)構(gòu)。(2)建立迷宮圖形。(3)對迷宮進(jìn)行處理找出一條從入口點到出口點的路徑。(4)輸出該路徑。(5)打印通路迷宮圖。初始化迷宮通過隨機方法設(shè)置迷宮布局建立并輸出迷宮原圖搜索迷宮通路輸出迷宮通路及路線圖結(jié)束圖6功能結(jié)構(gòu)圖當(dāng)迷宮采用二維數(shù)組表示時，老鼠在迷宮任一時刻的位置可由數(shù)組的行列序號i，j來表示。而從 i,j位置出發(fā)可能進(jìn)行的方向見下圖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個為了避免檢查邊界條件，將數(shù)組四周圍用值為1的邊框包圍起來，這樣二維數(shù)組maze應(yīng)該聲明為mazem+2,n+2在迷宮行進(jìn)時，可能有多個行進(jìn)方向可選，我們可以規(guī)定方向搜索的次序是從東（E）沿順時針方向進(jìn)行。為了簡化問題，規(guī)定i,j的下一步位置的坐標(biāo)是x,y，并將這8個方位傷的x和y坐標(biāo)的增量預(yù)先放在一個結(jié)構(gòu)數(shù)組move8中（見圖8）。該數(shù)組的每個分量有兩個域dx和dy。例如 要向東走，只要在j值上加上dy，就可以得到下一步位置的x,y值為i,j+dy。于是搜索方向的變化只要令方向值dir從0增至7，便可以從move數(shù)組中得到從i,j點出發(fā)搜索到的每一個相鄰點x,y。x=i+movedir.dxy=j+movedir.dy dx dy 圖7 方向位移圖 圖8向量差圖為了防止重走原路，我們規(guī)定對已經(jīng)走過的位置，將原值為0改為-1，這既可以區(qū)別該位置是否已經(jīng)走到過，又可以與邊界值1相區(qū)別。當(dāng)整個搜索過程結(jié)束后可以將所有的-1改回到0，從而恢復(fù)迷宮原樣。這樣計算機走迷宮的方法是：采取一步一步試探的方法。每一步都從（E）開始，按順時針對8個方向進(jìn)行探測，若某個方位上的mazex,y=0，表示可以通行，則走一步；若mazex,y=1，表示此方向不可通行須換方向再試。直至8個方向都試過，mazex,y均為1，說明此步已無路可走，需退回一步，在上一步的下一個方向重新開始探測。為此需要設(shè)置一個棧，用來記錄所走過的位置和方向（i，j，dir）。當(dāng)退回一步時，就從棧中退出一個元素，以便在上一個位置的下一個方向上探測，如又找到一個行進(jìn)方向，則把當(dāng)前位置和新的方向重新進(jìn)棧，并走到新的位置。如果探測到x=m，y=n，則已經(jīng)到達(dá)迷宮的出口，可以停止檢測，輸出存在棧中的路徑；若在某一位置的8個方向上都堵塞，則退回一步，繼續(xù)探測，如果已經(jīng)退到迷宮的入口（棧中無元素），則表示此迷宮無路徑可通行。2系統(tǒng)算法（偽代碼描述）：(1)建立迷宮節(jié)點的結(jié)構(gòu)類型stack。(2)入迷宮圖形 0表示可以通 1表示不可以通。 用二維數(shù)組mazem+2n+2進(jìn)行存儲。數(shù)組四周用1表示墻壁，其中入口點（1，1）與出口點（m，n）固定。 (3)函數(shù)path()對迷宮進(jìn)行處理，從入口開始：While(!(s->top=-1)&&(dir>=7)|(x=M)&&(y=N)&&(mazexy=-1) For(掃描八個可以走的方向) If(找到一個可以走的方向)進(jìn)入棧標(biāo)志在當(dāng)前點可以找到一個可以走的方向避免重復(fù)選擇mazexy=-1不再對當(dāng)前節(jié)點掃描 If(八個方向已經(jīng)被全部掃描過，無可以通的路) 標(biāo)志當(dāng)前節(jié)點沒有往前的路 后退一個節(jié)點搜索If(找到了目的地) 輸出路徑退出循環(huán) 未找到路徑 (4)輸出從入口點到出口點的一條路徑。 (5)輸出標(biāo)有通路的迷宮圖。3.算法流程圖：開始初始化迷宮，顯示迷宮初始化方向位移數(shù)組尋找迷宮中的一條出路If mazexy=0設(shè)1，1為出口該點數(shù)據(jù)入棧TFWhile 棧不空且dir<7doelseIf dir<7dir+TF回退一步出口或入口dir>=7 或?？诊@示通路結(jié)束圖9 算法流程圖4.程序代碼：#define M2 12 /*M2*N2為實際使用迷宮數(shù)組的大小*/#define N2 11#define maxlen M2 / 棧長度#include <stdio.h>#include<iostream.h>#include <malloc.h>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 /定義方向位移數(shù)組的元素類型對于存儲坐標(biāo)增量的方向位移數(shù)組move int dx,dy;/ void inimaze(int mazeN2)/初始化迷宮 int i,j,num; for(i=0,j=0;i<=M+1;i+)/設(shè)置迷宮邊界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; cout<<"原始迷宮為："<<endl; for(i=1;i<=M;i+) for (j=1;j<=N;j+) num=(800*(i+j)+1500) % 327;/根據(jù)MN的值產(chǎn)生迷宮 if (num<150)&&(i!=M|j!=N) mazeij=1; else mazeij=0; cout<<mazeij<<" "/顯示迷宮 cout<<endl; cout<<endl; /inimaze/void inimove(struct moved move)/初始化方向位移數(shù)組/依次為East，Southeast，south，southwest，west，northwest，north，northeastmove0.dx=0;move0.dy=1;move1.dx=1;move1.dy=1;move2.dx=1;move2.dy=0;move3.dx=1;move3.dy=-1;move4.dx=0;move4.dy=-1;move5.dx=-1;move5.dy-=1;move6.dx=-1;move6.dy=0;move7.dx=-1;move7.dy=1;/void inistack(sqstktp *s) /*初始化棧*/s->top=-1; /*inistack*/int push(sqstktp*s,elemtype x)if(s->top=maxlen-1)return(false);elses->stack+s->top=x;/*棧不滿，執(zhí)行入棧操作*/return(true);/*push*/elemtype pop(sqstktp *s)/*棧頂元素出棧*/elemtype elem;if(s->top<0) /如果?？?，返回空值elem.x=NULL;elem.y=NULL;elem.dir=NULL;return(elem);elses->top-;return(s->stacks->top+1); /棧不空，返回棧頂元素 /pop/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; /設(shè)11為入口處do x=i+movedir.dx;/球下一步可行的到達(dá)點的坐標(biāo)y=j+movedir.dy;if(mazexy=0)elem.x=i;elem.y=j;elem.dir=dir;f=push(s,elem);/如果可行將數(shù)據(jù)入棧if(f=false)/如果返回假，說明棧容量不足cout<<"棧長不足"i=x;j=y;dir=0;mazexy=-1;elseif (dir < 7)dir+;elseelem=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)&&(mazexy=-1); /循環(huán)if(s->top=-1)/若是入口，則無通路cout<<"此迷宮不通"elseelem.x=x; elem.y=y; elem.dir=dir;/將出口坐標(biāo)入棧f=push(s,elem);cout<<"迷宮通路是："<<endl;i=0;while (i <= s->top)cout<<"("<<s->stacki.x<<","<<s->stacki.y<<")"/顯示迷宮通路if(i!=s->top)cout<<"->"if(i+1)%4=0)cout<<endl;i+; /void draw(int mazeN2,sqstktp *s) /在迷宮中繪制出通路 cout<<"逃逸路線為："<<endl;int i,j;elemtype elem;for(i=1;i<=M;i+) /將迷宮中全部的-1值回復(fù)為0值for(j=1;j<=N;j+)if(mazeij=-1)mazeij=0;while(s->top>-1) /根據(jù)棧中元素的坐標(biāo)，將通路的各個點的值改為8elem=pop(s);i=elem.x;j=elem.y;mazeij=8;for(i=1;i<=M;i+)for(j=1;j<=N;j+)printf("%3d",mazeij); /顯示已標(biāo)記通路的迷宮cout<<endl;void main() /尋找迷宮通路程序sqstktp *s;int mazeM2N2;struct moved move8;inimaze(maze); /初始化迷宮數(shù)組s=(sqstktp *)malloc(sizeof(sqstktp);inistack(s); /初始化棧inimove(move); /初始化方向位移數(shù)組path(maze,move,s); /尋找迷宮通路cout<<endl;draw(maze,s); /繪制作出通路標(biāo)記的迷宮5.運行結(jié)果（三）求所有通路和最短路徑的算法1.源代碼（用原題的數(shù)據(jù)）#include <stdio.h>#define M 5/*行數(shù)*/#define N 7/*列數(shù)*/#define MaxSize 100/*棧最多元素個數(shù)*/int mgM+1N+1=/*一個迷宮,其四周要加上均為1的外框*/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; StackMaxSize,PathMaxSize;/*定義棧和存放最短路徑的數(shù)組*/int top=-1;/*棧指針*/int count=1;/*路徑數(shù)計數(shù)*/int minlen=MaxSize;/*最短路徑長度*/void mgpath()/*路徑為:(1,1)->(M-2,N-2)*/int i,j,di,find,k;top+;/*進(jìn)棧*/Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1; /*初始結(jié)點進(jìn)棧*/while (top>-1)/*棧不空時循環(huán)*/i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if (i=M-2 && j=N-2)/*找到了出口,輸出路徑*/ printf("%4d: ",count+);for (k=0;k<=top;k+)printf("(%d,%d) ",Stackk.i,Stackk.j);if (k+1)%5=0) printf("nt"); /*輸出時每5個結(jié)點換一行*/printf("n");if (top+1<minlen)/*比較找最短路徑*/for (k=0;k<=top;k+)Pathk=Stackk;minlen=top+1;mgStacktop.iStacktop.j=0; /*讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點*/top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;find=0;while (di<4 && find=0) /*找下一個可走結(jié)點*/di+;switch(di)case 0:i=Stacktop.i-1;j=Stacktop.j;break;case 1:i=Stacktop.i;j=Stacktop.j+1;break;case 2:i=Stacktop.i+1;j=Stacktop.j;break;case 3:i=Stacktop.i,j=Stacktop.j-1;break;if (mgij=0) find=1;if (find=1)/*找到了下一個可走結(jié)點*/Stacktop.di=di;/*修改原棧頂元素的di值*/top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;/*下一個可走結(jié)點進(jìn)棧*/mgij=-1;/*避免重復(fù)走到該結(jié)點*/else/*沒有路徑可走,則退棧*/mgStacktop.iStacktop.j=0; /*讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點*/top-;printf("最短路徑如下:n");printf("長度: %dn",minlen);printf("路徑: ");for (k=0;k<minlen;k+)printf("(%d,%d) ",Pathk.i,Pathk.j);if (k+1)%5=0) printf("nt"); /*輸出時每5個結(jié)點換一行*/printf("n");void main()printf("迷宮所有路徑如下:n");mgpath();2求解結(jié)果6.實驗收獲及思考 這次試驗總體來說還是比較簡單的，因為幾個思考問題都是在基本問題的源代碼上進(jìn)行改進(jìn)和補充。有了第一次數(shù)據(jù)結(jié)構(gòu)編程和測試的經(jīng)驗，這次試驗減少了很多困難，相對來說容易多了。附錄基本問題換代碼(思考問題源代碼在上文中已經(jīng)全部給出)#define M 4#define N 6#define MaxSize 100#include <stdio.h>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;int mgpath(int xi,int yi,int xe,int ye)/求解路徑為:(xi,yi)->(xe,ye)struct int i;/當(dāng)前方塊的行號int j;/當(dāng)前方塊的列號int di;/di是下一可走方位的方位號 stMaxSize;/定義棧int top=-1;/初始化棧指針int i,j,k,di,find;top+; /初始方塊進(jìn)棧sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1; while (top>-1)/棧不空時循環(huán)i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe && j=ye)/找到了出口,輸出路徑 printf("迷宮路徑如下:n");for (k=0;k<=top;k+)printf("t(%d,%d)",stk.i,stk.j);if (k+1)%5=0)/每輸出每5個方塊后換一行printf("n"); printf("n");return(1);/找到一條路徑后返回1find=0;while (di<4 && find=0)/找下一個可走方塊di+;switch(di)case 0:i=sttop.i-1;j=sttop.j;break;case 1:i=sttop.i;j=sttop.j+1;break;case 2:i=sttop.i+1;j=sttop.j;break;case 3:i=sttop.i,j=sttop.j-1;break;if (mgij=0) find=1;/找到下一個可走相鄰方塊if (find=1)/找到了下一個可走方塊sttop.di=di;/修改原棧頂元素的di值top+;/下一個可走方塊進(jìn)棧sttop.i=i;sttop.j=j;sttop.di=-1;mgij=-1;/避免重復(fù)走到該方塊else/沒有路徑可走,則退棧mgsttop.isttop.j=0;/讓該位置變?yōu)槠渌窂娇勺叻綁Ktop-;/將該方塊退棧return(0);/表示沒有可走路徑,返回0void main()mgpath(1,1,M,N);.