1、下載可編輯數據結構 課程設計迷宮求解班級：學號 ：姓名 ：指導老師 ：.專業 .整理 .下載可編輯迷宮求解1、問題描述輸入一個任意大小的迷宮數據，用遞歸和非遞歸兩種方法求出一條走出迷宮的路徑，并將路徑輸出。2、設計思路從入口出發 ，按某一方向向前探索 ，若能走通并且未走過 ，即某處可以到達 ，則到達新點 ，否則試探下一個方向 ；若所有的方向均沒有通路 ，則沿原路返回前一點 ，換下一個方向再繼續試探 ，直到找到一條通路 ，或無路可走又返回入口點 。在求解過程中 ，為了保證在到達某一點后不能向前繼續行走（無路）時，能正確返回前一點以便繼續從下一個方向向前試探 ，則需要用一個棧 （遞歸不需要 ）保存

2、所能夠到達的每一點的下標及從該點前進的方向 。設迷宮為 m 行 n 列，利用 mazemn 來表示一個迷宮，mazeij=0 或 1；其中：0 表示通路 ，1 表示不通 ，當從某點向下試探時 ，中間點有四個方向可以試探 ，而四個角點有兩個方向 ，其他邊緣點有三個方向 ，為使問題簡單化 ，用 mazem+2n+2 來表示迷宮 ，而迷宮的四周的值全部為 1 ，這樣做使問題簡單了 ，每個點的試探方向全部為 4，不用再判斷當前點的試探方向有幾個 。3、數據結構設計在上述表示迷宮的情況下 ，每個點有 4 個方向去試探 ，如當前點的坐標（x，y），與其相鄰的 4 個點的坐標都可根據與該點的相鄰方位而得到

3、。 因為出口在 （ m，n ），因此試探順序規定為 ：從當前.專業 .整理 .下載可編輯位置向前試探的方向為從正東沿順時針方向進行 。 為了簡化問題 ，方便求出新點的坐標 ，將從正東開始沿順時針進行的 4 個方向的坐標增量放在一個結構數組 move4 中，在 move 數組中，每個元素有兩個域組成 ，x 為橫坐標增量 ，y 為縱坐標增量 。這樣對 move 設計會很方便地求出從某點 （x，y）按某一方向 v(0<=v<=3) 到達的新點（ i，j）的坐標：i=x+movev.x;j=y+movev.y;當到達了某點而無路可走時需返回前一點 ，再從前一點開始向下一個方向繼續試探。因此

4、，壓入棧中的不僅是順序到達的各點的坐標，而且還要有從前一點到達本點的方向 。棧中元素是一個由行 、列、方向組成 。具體結構定義如下 ：#define m 3#define n 3typedef structint x,y;item;/* 路線移動的方向坐標,x 為橫向,y 縱向 */item move4; （遞歸只需定義到這里 ）typedef structint x,y,d;Datatype;/* 路線移動的方向坐標，x 為橫坐標，y 為總坐標 */typedef struct.專業 .整理 .下載可編輯Datatype dataMAXSIZE;/* 存儲路線移動的方向坐標*/int top

5、;SeqStack,*PSeqStack;4、功能函數設計迷宮棧的實現函數mazepath()迷宮遞歸的實現函數path()為了防止重復達到某點，以避免發生死循環 ，每次達到了某點 (i,j)后，改變 mazei j的值，迷宮棧的實現直接置 -1 ，算法結束前恢復原迷宮 ；而迷宮遞歸是將當前值置為已走的步驟，這樣輸出時對走過的路更顯而易見。（1）棧的函數設計 ：棧的初始化函數Init_SeqStack()判?？誆mpty_SeqStack()入棧函數Push_SeqStack()出棧函數Pop_SeqStack()取棧頂函數GetTop_SeqStack()銷毀棧Destroy_SeqStac

6、k()5、程序代碼迷宮棧：#include<stdio.h>#include<stdlib.h>.專業 .整理 .下載可編輯#define MAXSIZE 100#define m 3#define n 3/* 定義迷宮的行數和列數 ，可更改 */typedef structint x,y;item;item move4;/* 路線移動的方向坐標 */typedef structint x,y,d;Datatype;/* 橫縱坐標及方向 */typedef structDatatype dataMAXSIZE;int top;SeqStack,*PSeqStack;/*

7、 定義棧 */PSeqStack Init_SeqStack(void)/* 初始化棧 */PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack);.專業 .整理 .下載可編輯if(S)S->top=-1;return S;int Empty_SeqStack(PSeqStack S)/* 判?？?*/if(S->top=-1)return 1;elsereturn 0;int Push_SeqStack(PSeqStack S,Datatype x)/* 入棧 */if(S->top=MAXSIZE-1)return 0;elseS

8、->top+;S->dataS->top=x;return 1;.專業 .整理 .下載可編輯int Pop_SeqStack(PSeqStack S,Datatype *x)/* 出棧 */if(Empty_SeqStack(S)return 0;else*x=S->dataS->top;S->top-;return 1;void Destroy_SeqStack(PSeqStack *S)/* 毀棧 */if(*S)free(*S);*S=NULL;return;.專業 .整理 .下載可編輯int mazepath(int mazen+2,item mov

9、e4,int x0,int y0)/* 迷宮功能實現函數 */* 求迷宮路徑，入口參數 ：迷宮數組 ，下標移動的增量數組，開始點（ x0，y0）， 0（m,n ）是終點，返回值：1 表示求出路徑 ，0 表示無路徑 */ PSeqStack S;Datatype temp;int x,y,d,i,j;temp.x=x0;temp.y=y0;temp.d=-1;S=Init_SeqStack();/* 初始化棧 */if(!S)printf(" 棧初始化失敗 ");return 0;Push_SeqStack(S,temp);while(!Empty_SeqStack(S)Po

10、p_SeqStack(S,&temp);x=temp.x;.專業 .整理 .下載可編輯y=temp.y;d=temp.d+1;while(d<4)/* 存在剩余方向可以搜索 */i=x+moved.x;j=y+moved.y;if(mazeij=0)/* 此方向可以走 */temp.x=x;temp.y=y;temp.d=d;mazexy=-1;Push_SeqStack(S,temp); /* 點（x，y）可以走 ，用棧保存可以走的路徑 */x=i;y=j;if(x=m&&y=n)/* 迷宮有路 */while(!Empty_SeqStack(S)Pop_Seq

11、Stack(S,&temp);printf("(%d,%d)<-",temp.x,temp.y);/* 打印可以走的路徑 */.專業 .整理 .下載可編輯Destroy_SeqStack(&S);/* 銷毀棧 */return 1;else d=0;/* 方向復位 ，從第一個方向開始試探 */else d+;/* 試探下一個方向 */ /*while(d<4)*/*while*/Destroy_SeqStack(&S);/* 銷毀棧 */printf(" 迷宮無路徑 n");return 0;/* 迷宮無路 */voi

12、d main()item move4;int mazem+2n+2;int i,j;for(i=0;i<m+2;i+)/* 輸入迷宮 ，四周為 1*/.專業 .整理 .下載可編輯for(j=0;j<n+2;j+)scanf("%d",&mazeij);move0.x=1;move0.y=0;move1.x=0;move1.y=1;move2.x=-1;move2.y=0;move3.x=0;move3.y=-1;/* 給方向坐標賦值 */mazepath(maze,move,1,1);getch();迷宮遞歸 :#include<stdio.h&g

13、t;#include<stdlib.h>#define m 3#define n 3typedef structint x,y;item;item move4;int path(int mazen+2,item move,int x,int y,int step).專業 .整理 .下載可編輯/* 求迷宮路徑 ，入口參數 ：迷宮數組 ，下標移動的增量數組，開始點 （ x，y），以及開始點對應的步數step ，（ m,n ）是終點，返回值：1 表示求出路徑，0 表示無路徑 */int i;step+;mazexy=step;if(x=m&&y=n)return 1;/*

14、 起始位置是出口 ，找到路徑 ，結束 */for(i=0;i<4;i+)if(mazex+movei.xy+movei.y=0)if(path(maze,move,x+movei.x,y+movei.y,step)return 1;/* 下一個是出口 ，則返回 */step-;mazexy=0;return 0;void main().專業 .整理 .下載可編輯item move4;int mazem+2n+2;int i,j;for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)scanf("%d",&mazeij);printf(

15、"n");move0.x=1;move0.y=0;move1.x=0;move1.y=1;move2.x=-1;move2.y=0;move3.x=0;move3.y=-1;if(path(maze,move,1,1,1)for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)printf("%d ",mazeij);printf("n");/* 輸出有路迷宮的路線 */.專業 .整理 .下載可編輯else printf(迷宮無“路徑 n ” );getch();6、運行與測試迷宮棧（無路徑）：有路徑：迷宮遞歸 （無路徑）：.專業 .整理 .下載可編輯有路徑：7、設計心得迷宮這個問題也是老師經常講的例子 ，是加深對棧運用的好程序。這個程序又加了個遞歸的算法 ，相同的程序不同的算法 。我結合老師提過的