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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：10 大小：92.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩9頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

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

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

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

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

5、再判斷當前點的試探方向有幾個。　　數(shù)據(jù)結(jié)構(gòu)設(shè)計　　在上述表示迷宮的情況下，每個點有4個方向去試探，如當前點的坐標（x，y），與其相鄰的4個點的坐標都可根據(jù)與該點的相鄰方位而得到。因為出口在（m，n），因此試探順序規(guī)定為：從當前位置向前試探的方向為從正東沿順時針方向進行。為了簡化問題，方便求出新點的坐標，將從正東開始沿

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

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

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

9、 /*路線移動的方向坐標，x為橫坐標，y為總坐標*/　　typedef struct{　　Datatype data[MAXSIZE]; /*存儲路線移動的方向坐標*/　　int top;　　}

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

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

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

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

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

15、t;　　}item;　　item move[4]; /*路線移動的方向坐標*/　　typedef struct{　　int x,y,d;　　}Datatype;

16、 /*橫縱坐標及方向*/　　typedef struct{　　Datatype data[MAXSIZE];　　int top;　　}SeqStack,*PSeqStack; /*定義棧*/<

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

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

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

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

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

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

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

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

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

26、t;　　free(*S);　　*S=NULL;　　return;　　}　　int mazepath

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

54、無路徑\n”);　　getch();　　}　　運行與測試　　迷宮棧（無路徑）：

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

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

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載