數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-迷宮求解(遞歸與非遞歸)

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)</p><p><b>　　迷宮求解</b></p><p><b>　　班級： </b></p><p><b>　　學(xué)號： </b></p><p><b>　　姓名： </b></p&g

2、t;<p><b>　　指導(dǎo)老師： </b></p><p><b>　　迷宮求解</b></p><p><b>　　問題描述</b></p><p>　　輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用遞歸和非遞歸兩種方法求出一條走出迷宮的路徑，并將路徑輸出。</p><p>

3、<b>　　設(shè)計(jì)思路</b></p><p>　　從入口出發(fā)，按某一方向向前探索，若能走通并且未走過，即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一個(gè)方向；若所有的方向均沒有通路，則沿原路返回前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到找到一條通路，或無路可走又返回入口點(diǎn)。</p><p>　　在求解過程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無路）時(shí)，能正確返回前一點(diǎn)以便繼續(xù)

4、從下一個(gè)方向向前試探，則需要用一個(gè)棧（遞歸不需要）保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。設(shè)迷宮為m行n列，利用maze[m][n]來表示一個(gè)迷宮，maze[i][j]=0或1；其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時(shí)，中間點(diǎn)有四個(gè)方向可以試探，而四個(gè)角點(diǎn)有兩個(gè)方向，其他邊緣點(diǎn)有三個(gè)方向，為使問題簡單化，用maze[m+2][n+2]來表示迷宮，而迷宮的四周的值全部為1，這樣做使問題簡單了，每個(gè)點(diǎn)的試探方向全部為4，不用

5、再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè)。</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</b></p><p>　　在上述表示迷宮的情況下，每個(gè)點(diǎn)有4個(gè)方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)（x，y），與其相鄰的4個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到。因?yàn)槌隹谠冢╩，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿順時(shí)針方向進(jìn)行。為了簡化問題，方便求出新點(diǎn)的坐標(biāo)，將從正東開始沿

6、順時(shí)針進(jìn)行的4個(gè)方向的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組move[4]中，在move數(shù)組中，每個(gè)元素有兩個(gè)域組成，x為橫坐標(biāo)增量，y為縱坐標(biāo)增量。這樣對move設(shè)計(jì)會很方便地求出從某點(diǎn)（x，y）按某一方向v(0<=v<=3)到達(dá)的新點(diǎn)（i，j）的坐標(biāo)：i=x+move[v].x;j=y+move[v].y;</p><p>　　當(dāng)?shù)竭_(dá)了某點(diǎn)而無路可走時(shí)需返回前一點(diǎn)，再從前一點(diǎn)開始向下一個(gè)方向繼續(xù)試探。因此，壓入

7、棧中的不僅是順序到達(dá)的各點(diǎn)的坐標(biāo)，而且還要有從前一點(diǎn)到達(dá)本點(diǎn)的方向。棧中元素是一個(gè)由行、列、方向組成。具體結(jié)構(gòu)定義如下：</p><p>　　#define m 3</p><p>　　#define n 3</p><p>　　typedef struct{</p><p>　　int x,y; </p>&

8、lt;p>　　}item; /*路線移動的方向坐標(biāo),x為橫向,y縱向*/</p><p>　　item move[4];（遞歸只需定義到這里）</p><p>　　typedef struct{</p><p>　　int x,y,d;</p><p>　　}Datatype;

9、 /*路線移動的方向坐標(biāo)，x為橫坐標(biāo)，y為總坐標(biāo)*/</p><p>　　typedef struct{</p><p>　　Datatype data[MAXSIZE]; /*存儲路線移動的方向坐標(biāo)*/</p><p><b>　　int top;</b></p><p>　　}

10、SeqStack,*PSeqStack;</p><p><b>　　功能函數(shù)設(shè)計(jì)</b></p><p>　　迷宮棧的實(shí)現(xiàn)函數(shù)mazepath()</p><p>　　迷宮遞歸的實(shí)現(xiàn)函數(shù)path()</p><p>　　為了防止重復(fù)達(dá)到某點(diǎn)，以避免發(fā)生死循環(huán)，每次達(dá)到了某點(diǎn)(i,j)后，改變maze[i][j]的值，迷

11、宮棧的實(shí)現(xiàn)直接置-1，算法結(jié)束前恢復(fù)原迷宮；而迷宮遞歸是將當(dāng)前值置為已走的步驟，這樣輸出時(shí)對走過的路更顯而易見。</p><p><b>　　棧的函數(shù)設(shè)計(jì)：</b></p><p>　　棧的初始化函數(shù) Init_SeqStack()</p><p>　　判棧空 Empty_SeqStack()</p><p

12、>　　入棧函數(shù) Push_SeqStack()</p><p>　　出棧函數(shù) Pop_SeqStack()</p><p>　　取棧頂函數(shù) GetTop_SeqStack()</p><p>　　銷毀棧 Destroy_SeqStack()</p><p><b>　　程序代碼&

13、lt;/b></p><p><b>　　迷宮棧：</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define MAXSIZE 100</p><p>　　#define

14、 m 3 </p><p>　　#define n 3 /*定義迷宮的行數(shù)和列數(shù)，可更改*/</p><p>　　typedef struct{</p><p><b>　　int x,y;</b></p><p><b&g

15、t;　　}item;</b></p><p>　　item move[4]; /*路線移動的方向坐標(biāo)*/</p><p>　　typedef struct{</p><p>　　int x,y,d;</p><p>　　}Datatype;

16、 /*橫縱坐標(biāo)及方向*/</p><p>　　typedef struct{</p><p>　　Datatype data[MAXSIZE];</p><p><b>　　int top;</b></p><p>　　}SeqStack,*PSeqStack; /*定義棧*/<

17、/p><p>　　PSeqStack Init_SeqStack(void) /*初始化棧*/</p><p><b>　　{</b></p><p>　　PSeqStack S;</p><p>　　S=(PSeqStack)malloc(sizeof(SeqStack));</p>&l

18、t;p><b>　　if(S)</b></p><p>　　S->top=-1;</p><p><b>　　return S;</b></p><p><b>　　}</b></p><p>　　int Empty_SeqStack(PSeqStack S)

19、 /*判棧空*/</p><p><b>　　{</b></p><p>　　if(S->top==-1)</p><p><b>　　return 1;</b></p><p><b>　　else</b></p><p><b&

20、gt;　　return 0;</b></p><p><b>　　}</b></p><p>　　int Push_SeqStack(PSeqStack S,Datatype x) /*入棧*/</p><p><b>　　{</b></p><p>　　if(S->top==

21、MAXSIZE-1)</p><p><b>　　return 0;</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　S->top++;</b></p><

22、p>　　S->data[S->top]=x;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int Pop_SeqStack(PSeqStack S,

23、Datatype *x) /*出棧*/</p><p><b>　　{</b></p><p>　　if(Empty_SeqStack(S))</p><p><b>　　return 0;</b></p><p><b>　　else</b></p>&

24、lt;p><b>　　{</b></p><p>　　*x=S->data[S->top];</p><p><b>　　S->top--;</b></p><p><b>　　return 1;</b></p><p><b>　　}<

25、/b></p><p><b>　　}</b></p><p>　　void Destroy_SeqStack(PSeqStack *S) /*毀棧*/</p><p><b>　　{</b></p><p><b>　　if(*S)</b></p&g

26、t;<p><b>　　free(*S);</b></p><p><b>　　*S=NULL;</b></p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　int mazepath

27、(int maze[][n+2],item move[4],int x0,int y0) /*迷宮功能實(shí)現(xiàn)函數(shù)*/</p><p>　　{/*求迷宮路徑，入口參數(shù)：迷宮數(shù)組，下標(biāo)移動的增量數(shù)組，開始點(diǎn)（x0，y0），0（m,n）是終點(diǎn)，返回值：1表示求出路徑，0表示無路徑*/</p><p>　　PSeqStack S;</p><p>　　Datatype t

28、emp;</p><p>　　int x,y,d,i,j;</p><p>　　temp.x=x0;</p><p>　　temp.y=y0;</p><p>　　temp.d=-1;</p><p>　　S=Init_SeqStack(); /*初始化棧*/</p>

29、<p><b>　　if(!S)</b></p><p><b>　　{</b></p><p>　　printf("棧初始化失敗");</p><p><b>　　return 0;</b></p><p><b>　　}</

30、b></p><p>　　Push_SeqStack(S,temp);</p><p>　　while(!Empty_SeqStack(S))</p><p><b>　　{</b></p><p>　　Pop_SeqStack(S,&temp);</p><p><b>

31、　　x=temp.x;</b></p><p><b>　　y=temp.y;</b></p><p>　　d=temp.d+1;</p><p>　　while(d<4) /*存在剩余方向可以搜索*/</p><p><b>　　{</b

32、></p><p>　　i=x+move[d].x;</p><p>　　j=y+move[d].y;</p><p>　　if(maze[i][j]==0) /*此方向可以走*/</p><p><b>　　{</b></p><p><b>　　t

33、emp.x=x;</b></p><p><b>　　temp.y=y;</b></p><p><b>　　temp.d=d;</b></p><p>　　maze[x][y]=-1;</p><p>　　Push_SeqStack(S,temp); /*點(diǎn)（x，y）可以走，用棧保存可

34、以走的路徑*/</p><p><b>　　x=i;y=j;</b></p><p>　　if(x==m&&y==n) /*迷宮有路*/</p><p><b>　　{</b></p><p>　　while(!Empty_SeqStack(S))</

35、p><p><b>　　{</b></p><p>　　Pop_SeqStack(S,&temp);</p><p>　　printf("(%d,%d)<-",temp.x,temp.y); /*打印可以走的路徑*/</p><p><b>　　}</b></p&

36、gt;<p>　　Destroy_SeqStack(&S); /*銷毀棧*/</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　else d=0; /*方向復(fù)位，從第一個(gè)方向開始試探*/&l

37、t;/p><p><b>　　}</b></p><p>　　else d++; /*試探下一個(gè)方向*/</p><p>　　} /*while(d<4)*/</p><p>　　} /*while*/</p><p>　　Destroy_S

38、eqStack(&S); /*銷毀棧*/</p><p>　　printf("迷宮無路徑\n"); </p><p>　　return 0; /*迷宮無路*/</p><p><b>　　}</b></p><p>

39、　　void main()</p><p><b>　　{</b></p><p>　　item move[4];</p><p>　　int maze[m+2][n+2];</p><p><b>　　int i,j;</b></p><p>　　for(i=0;i<

40、m+2;i++) /*輸入迷宮，四周為1*/</p><p><b>　　{</b></p><p>　　for(j=0;j<n+2;j++)</p><p>　　scanf("%d",&maze[i][j]);</p><p><b

41、>　　}</b></p><p>　　move[0].x=1;move[0].y=0;</p><p>　　move[1].x=0;move[1].y=1;</p><p>　　move[2].x=-1;move[2].y=0;</p><p>　　move[3].x=0;move[3].y=-1;

42、 /*給方向坐標(biāo)賦值*/</p><p>　　mazepath(maze,move,1,1);</p><p><b>　　getch();</b></p><p><b>　　}</b></p><p><b>　　迷宮遞歸:</b></p><p&g

43、t;　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define m 3</p><p>　　#define n 3</p><p>　　typedef struct{</p><p><b>　　int x,y;

44、</b></p><p><b>　　}item;</b></p><p>　　item move[4];</p><p>　　int path(int maze[][n+2],item move[],int x,int y,int step)</p><p>　　{/*求迷宮路徑，入口參數(shù)：迷宮數(shù)組，下標(biāo)移

45、動的增量數(shù)組，開始點(diǎn)（x，y），以及開始點(diǎn)對應(yīng)的步數(shù)step，（m,n）是終點(diǎn)，返回值：1表示求出路徑，0表示無路徑*/</p><p><b>　　int i;</b></p><p><b>　　step++;</b></p><p>　　maze[x][y]=step;</p><p>　　i

46、f(x==m&&y==n)</p><p>　　return 1; /*起始位置是出口，找到路徑，結(jié)束*/</p><p>　　for(i=0;i<4;i++)</p><p><b>　　{</b></p><p>　　if(maze[x+mov

47、e[i].x][y+move[i].y]==0)</p><p>　　if(path(maze,move,x+move[i].x,y+move[i].y,step))</p><p>　　return 1; /*下一個(gè)是出口，則返回*/</p><p><b>　　}</b></p><p&g

48、t;<b>　　step--;</b></p><p>　　maze[x][y]=0;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b

49、>　　{</b></p><p>　　item move[4];</p><p>　　int maze[m+2][n+2];</p><p><b>　　int i,j;</b></p><p>　　for(i=0;i<m+2;i++)</p><p><b>　

50、　{</b></p><p>　　for(j=0;j<n+2;j++)</p><p>　　scanf("%d",&maze[i][j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p>&l

51、t;p>　　move[0].x=1;move[0].y=0;</p><p>　　move[1].x=0;move[1].y=1;</p><p>　　move[2].x=-1;move[2].y=0;</p><p>　　move[3].x=0;move[3].y=-1;</p><p>　　if(path(maze,move,1,1

52、,1))</p><p><b>　　{</b></p><p>　　for(i=0;i<m+2;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<n+2;j++)</p><p>　　printf("%d &qu

53、ot;,maze[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　} /*輸出有路迷宮的路線*/</p><p>　　else printf(“迷宮

54、無路徑\n”);</p><p><b>　　getch();</b></p><p><b>　　}</b></p><p><b>　　運(yùn)行與測試</b></p><p><b>　　迷宮棧（無路徑）：</b></p><p>

55、<b>　　有路徑：</b></p><p>　　迷宮遞歸（無路徑）：</p><p><b>　　有路徑：</b></p><p><b>　　設(shè)計(jì)心得</b></p><p>　　迷宮這個(gè)問題也是老師經(jīng)常講的例子，是加深對棧運(yùn)用的好程序。這個(gè)程序又加了個(gè)遞歸的算法，相同的程

56、序不同的算法。我結(jié)合老師提過的思想與教材上的例子，很順利的完成了這個(gè)程序。其實(shí)在寫完這個(gè)程序后，我又想到了馬的遍歷，這兩個(gè)程序的設(shè)計(jì)思想極其相似，所以我很快又寫出馬的遍歷棧與遞歸的算法，并且運(yùn)行成功。</p><p>　　至此，三個(gè)題目設(shè)計(jì)都完成了，每次上機(jī)都會遇到題目，這次也不例外，經(jīng)過我的不懈努力，解決了部分，還有的現(xiàn)在不能解決，只能留著日后思考和解決了，例如簡化代碼，可視化調(diào)試。這次的程序設(shè)計(jì)也讓我意識到，