1、.利用棧實現(xiàn)迷宮的求解一、要解決的問題 ：以一個 m*n 的長方陣表示迷宮， 0 和 1 分別表示迷宮中的通路和障礙，設(shè)計一個程序，對任意設(shè)定的迷宮， 求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。二：算法基本思想描述:用一個字符類型的二維數(shù)組表示迷宮，數(shù)組中每個元素取值“0”（表示通路）或“1”（表示墻壁） 。二維數(shù)組的第 0 行、第 m+1行、第 0 列、第 m+1列元素全置成“ 1”， 表示迷宮的邊界；第 1 行第 1 列元素和第 m行第 n 列元素置成“ 0”， 表示迷宮的入口和出口走迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按東、南、西、北4 個方向順序試探下一個位置；

2、用二維數(shù)組move記錄 4 個方向上行下標(biāo)增量和列下標(biāo)增量，則沿第 i 個方向前進一步，可能到達的新位置坐標(biāo)可利用move數(shù)組確定：Px=x+movei0Py=y+movei1如果某方向可以通過，并且不曾到達，則前進一步，在新位置上繼續(xù)進行搜索；如果 4 個方向都走不通或曾經(jīng)到達過，則退回一步，在原來的位置上繼續(xù)試探下一位置。三：設(shè)計：1：數(shù)據(jù)結(jié)構(gòu)的設(shè)計：（ 1）定義三元數(shù)組元素的結(jié)構(gòu)typedef struct MazeDirectint Dx; /行標(biāo)int Dy; /列標(biāo)int direct; /走到下一個坐標(biāo)點的方向.MazeDirect;（ 2）定義鏈表節(jié)點的結(jié)構(gòu)組成typedef

3、struct LinkNodeelemtype data;/數(shù)據(jù)域struct LinkNode *next;/指針域LinkNode;（ 3）定義鏈棧的頭指針typedef structLinkNode *top;/棧的頭指針LinkStack;（ 4）移動數(shù)組結(jié)構(gòu)的定義typedef structint x,y;/x為行標(biāo)， y 為列標(biāo)Direction_increm;2：算法的設(shè)計：【1】迷宮圖的設(shè)計設(shè)迷宮為 m行 n 列，利用 mazemn 來表示一個迷宮， mazeij=0或 1;其中： 0 表示通路， 1 表示不通，當(dāng)從某點向下試探時，中間點有4 個方向可以試探， （見圖）而四個角

4、點有 2 個方向，其它邊緣點有3 個方向，為使問題簡單化我們用mazem+2n+2 來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個點的試探方向全部為4，不用再判斷當(dāng)前點的試探方向有幾個，同時與迷宮周圍是墻壁這一實際問題相一致。假設(shè)有 6 行 8 列的迷宮，如下圖為 maze810構(gòu)造的迷宮.11111111111011101111100101111110000000111001101111110001000110110001011111111111【 2】試探方向的設(shè)計 ：在上述表示迷宮的情況下，每個點有4 個方向去試探，如當(dāng)前點的坐標(biāo)( x , y) ，與其相鄰的 4 個點的

5、坐標(biāo)都可根據(jù)與該點的相鄰方位而得到，如圖2 所示。因為出口在（m， n），因此試探順序規(guī)定為： 從當(dāng)前位置向前試探的方向為從正東沿順時針方向進行。為了簡化問題，方便的求出新點的坐標(biāo)，將從正東開始沿順時針進行的這4 個方向（用0，1，2，3 表示東、南、西、北）的坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組move 4 中，在 move 數(shù)組中，每個元素有兩個域組成， x：橫坐標(biāo)增量，y：縱坐標(biāo)增量。Move數(shù)組如圖3 所示。 move 數(shù)組定義如下：typedef struct intx ; /行inty ; /列 item ; item move4 ;這樣對 move 的設(shè)計會很方便地求出從某點 ( x，y)

6、按某一方向 v (0 v 3) 到達的新點（ i ，j ）的坐標(biāo)： i =x + movev. x ， j = y + movev. y 。(x-1 ，y)xy.(x，y-1)(x，y)(x， y+1).00111020-13-10圖 3增量數(shù)組 move【 3】 棧的設(shè)計 ：當(dāng)?shù)竭_了某點而無路可走時需返回前一點，再從前一點開始向下一個方向繼續(xù)試探。因此， 壓入棧中的不僅是順序到達的各點的坐標(biāo)， 而且還要有從前一點到達本點的方向， 即每走一步棧中記下的內(nèi)容為 ( 行，列，來的方向 ) 。對于圖 1 所示迷宮，依次入棧為：top>3,4,03,3,03,2,12,2,02,1,11,1,0

7、棧中每一組數(shù)據(jù)是所到達的每點的坐標(biāo)及從該點沿哪個方向向下走的，對于圖3 迷宮，走的路線為：(1,1,0)(2,1,1)(2,2,0)(3,2,1)(3,3,0)(3,4,0)（下腳標(biāo)表示方向），當(dāng)無路可走，則應(yīng)回溯，對應(yīng)的操作是出棧，沿下一個方向即方向繼續(xù)試探。棧中元素是一個由行、列、方向組成的三元組，棧元素的設(shè)計如下：typedef structint x , y , d ;/*橫縱坐標(biāo)及方向*/datatype ;棧的定義為：SeqStack s ;【4】 .如何防止重復(fù)到達某點，以避免發(fā)生死循環(huán)：一種方法是另外設(shè)置一個標(biāo)志數(shù)組markmn，它的所有元素都初始化為0，一旦到達了某一點 (

8、i , j ) 之后，使 mark i j 置 1，下次再試探這個位置時就不能再走了。另一種方法是當(dāng)?shù)竭_某點（ i , j ）后使 maze i j 置 -1 ，以便區(qū)別未到達過的點，同樣也能起到防止走重復(fù)點的目的，此處采用后一方法，算法結(jié)束前可恢復(fù)原迷宮。.四：詳細(xì)設(shè)計；1.算法的設(shè)計思想及流程圖（ 1）主要函數(shù)的功能說明void ini_stack(LinkStack *)/*初始化鏈棧 */int empty_Stack(LinkStack *)/*判斷是否為空棧*/void push_Stack(LinkStack *,elemtype)/*入棧 */elemtype pop_Stac

9、k(LinkStack *) /*出棧 */int size_stack(LinkStack )/*棧的規(guī)模大小 */（ 2）算法描述【偽代碼描述】迷宮求解算法思想如下：(1) 棧初始化 ;(2)將入口點坐標(biāo)及到達該點的方向（設(shè)為-1 ）入棧(3) while ( 棧不空 ) 棧頂元素（ x , y , d） 出棧 ;求出下一個要試探的方向 d+ ;/ 當(dāng)遇到死路的時候就出棧，尋找原來點的下一個方向while（還有剩余試探方向時） if（ d 方向可走）則 （ x , y , d）入棧 ;求新點坐標(biāo)(i, j ) ;將新點（ i , j）切換為當(dāng)前點（x , y） ;if ( (x , )=

10、=( ,n) )結(jié)束 ;else重置 d=0 ;else d+ ;五：源程序清單 ；#include <stdio.h>#include <stdlib.h>int m,n;typedef struct MazeD Dx;int Dy;int direct;MazeDirect;/*定義三元數(shù)組元素的結(jié)構(gòu)*/typedef MazeDirect elemtype;typedef struct LinkNodeelemtype data;struct LinkNode *next;/*定義鏈表節(jié)點的結(jié)構(gòu)組成*/LinkNode;typedef struc

11、tLinkNode *top;/*定義鏈棧的頭指針*/LinkStack;void ini_stack(LinkStack *stack)/*初始化鏈棧 */stack->top=NULL;int empty_Stack(LinkStack *stack)/*判斷是否為空棧*/if (stack->top!=NULL)return 0;elsereturn 1;void push_Stack(LinkStack *stack,elemtype x)/*入棧 */LinkNode *s;s=(LinkNode *)malloc(sizeof(LinkNode);s->data=

12、x;s->next=stack->top;stack->top=s;elemtype pop_Stack(LinkStack *stack) /*出棧 */.elemtype x;LinkNode *p;elemtype tmpNull=0,0,0;if (stack->top=NULL)return tmpNull;/(NULL)elsex=stack->top->data;p=stack->top;stack->top=p->next;free(p);return (x);int size_stack(LinkStack stack)/

13、*棧的規(guī)模大小 */int i;LinkNode *Numb;i=0;Numb=stack.top;while(Numb!=NULL)Numb=Numb->next;i+;return i;int w,t,maze100100;typedef structint x,y;/x為行標(biāo)， y 為列標(biāo)Direction_increm;Direction_increm MazeMove4=0,1,1,0,0,-1,-1,0;typedef MazeDirect TmpType;.int Maze_path()MazeDirect tmp,path;LinkStack s;int x,y,Px,P

14、y,d,flag=0;ini_stack(&s);tmp.Dx=1;tmp.Dy=1;tmp.direct=-1;push_Stack(&s,tmp);while (!empty_Stack(&s)tmp=pop_Stack(&s);x=tmp.Dx;y=tmp.Dy;d=tmp.direct+1;/遇到死路的時候，回溯（通過出棧完成）while (d<4)Px=x+MazeMoved.x;Py=y+MazeMoved.y;if (mazePxPy=0)tmp.Dx=x;tmp.Dy=y;tmp.direct=d;push_Stack(&s,tmp

15、);x=Px;y=Py;mazexy=-1;/*標(biāo)記，防止重復(fù)點*/if(x=m&&y=n)flag=1;printf("n到達迷宮出口：%d,%d",x,y);printf("n經(jīng)過的節(jié)點有：%d個 ",size_stack(s);while(!empty_Stack(&s)path=pop_Stack(&s);printf("n(%d,%d,%d)",path.Dx,path.Dy,path.direct);break;else d=0;/結(jié)束 ifelse d+;./結(jié)束內(nèi)部 while/結(jié)束外部whilereturn flag;void main()printf(" 請輸入迷宮圖的行數(shù)和列數(shù) ( 輸入格