《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告迷宮求解

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

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告迷宮求解_第1頁

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

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

文檔簡介

1、　　課程設(shè)計任務(wù)書　　題目：迷宮設(shè)計 　　學(xué) 號： 　　姓名： </p&

2、gt;　　專業(yè)：網(wǎng)絡(luò)技術(shù) 　　課程：數(shù)據(jù)結(jié)構(gòu) 　　指導(dǎo)教師：職稱：講師

3、;　　完成時間： 2013年 12 月----2014 年 1 月　　年月日　　課程設(shè)計任務(wù)書及成績評定　　目錄　　迷宮求解····

4、3;···························　　問題描述·····

5、;····································

6、83;·　　需求分析及設(shè)計思路······························

7、;···　?。?）數(shù)據(jù)結(jié)構(gòu)定義····························&

8、#183;···········　?。?）系統(tǒng)功能模塊介紹···················&

9、#183;················　?。?）源代碼···············

10、·······························　?。?）運行結(jié)果及調(diào)試分

11、析 ································　?。?）

12、課程設(shè)計總結(jié) ·····························　　一．迷宮求解&

13、lt;/b>　　問題描述　　輸入一個任意大小的迷宮數(shù)據(jù)，用遞歸和非遞歸兩種方法求出一條走出迷宮的路徑，并將路徑輸出。　?。?）需求分析及設(shè)計思路　　從入口出發(fā)，按某一方向向前探索，若能走通并且未走過，即某處可以到達，則到達新點，

14、否則試探下一個方向；若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續(xù)試探，直到找到一條通路，或無路可走又返回入口點。　　在求解過程中，為了保證在到達某一點后不能向前繼續(xù)行走（無路）時，能正確返回前一點以便繼續(xù)從下一個方向向前試探，則需要用一個棧（遞歸不需要）保存所能夠到達的每一點的下標(biāo)及從該點前進的方向。設(shè)迷宮為m行n列，利用maze[m][n]來表示一個迷宮，maze[i][j]

15、=0或1；其中：0表示通路，1表示不通，當(dāng)從某點向下試探時，中間點有四個方向可以試探，而四個角點有兩個方向，其他邊緣點有三個方向，為使問題簡單化，用maze[m+2][n+2]來表示迷宮，而迷宮的四周的值全部為1，這樣做使問題簡單了，每個點的試探方向全部為4，不用再判斷當(dāng)前點的試探方向有幾個。　?。?）數(shù)據(jù)結(jié)構(gòu)定義

16、　#define m 6　　#define n 8　　#define MAXSIZE 100　　//四周為1代表圍墻,0為可走路徑　　int maze[m+2][n+2]={ 　　{1,1,1,1,1,1,1,1,1,1}, &l

17、t;/p>　　{1,0,1,1,1,0,1,1,1,1},　　{1,0,0,0,0,1,1,1,1,1},　　{1,0,1,0,0,0,0,0,1,1},　　{1,0,1,1,1,0,0,1,1,1},　　{1,1,0,0,1,1,0,0,0,

18、1},　　{1,0,1,1,0,0,1,1,0,1},　　{1,1,1,1,1,1,1,1,1,1}　　}; //入口坐標(biāo)為（1，1），出口坐標(biāo)為（6，8）　　typedef struct　　{ int x,y;/*試探方向*

19、/　　}item;　　item move[4]={{0,1},{1,0},{0,-1},{-1,0}};　　typedef struct/*棧的設(shè)計*/　　{int x,y,d; /*縱橫坐標(biāo)及方向*/<

20、p>　　}DataType;　　系統(tǒng)功能模塊介紹　　創(chuàng)建一順序棧：　　PSeqStack Init_SeqStack(void) 　　判斷棧是否為空：

21、　　int Empty_SeqStack(PSeqStack S) 　　在棧頂插入一新元素x：　　int Push_SeqStack (PSeqStack S, DataType x) 　　刪除棧頂元素并保存在*x ：　　i

22、nt Pop_SeqStack(PSeqStack S ,DataType *x) 　　銷毀棧：　　void Destroy_SeqStack(PSeqStack *S) 　　利用棧的非遞歸算法求迷宮路徑：　　int maz

23、epath(int maze [ ][n+2] ,item move[ ],int x0,int y0)　　遞歸算法求迷宮路徑： 　　int mazepath1(int maze[][n+2],item move[],int x,int y)　　主函數(shù)：

24、　　int main()　　{ 出口坐標(biāo)已定，　　利用while循環(huán)多次輸入入點坐標(biāo)，　　調(diào)用mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0) <

25、b>　　輸出可走的路徑　　}　?。?）源代碼　　#include <stdio.h>　　#include <stdlib.h>

26、　　#define m 6　　#define n 8　　#define MAXSIZE 100　　int maze[m+2][n+2]={ 　　{1,1,1,1,1,1,1,1,1,1},//四周為1代表圍墻,0為可走路徑 &

27、lt;p>　　{1,0,1,1,1,0,1,1,1,1},　　{1,0,0,0,0,1,1,1,1,1},　　{1,0,1,0,0,0,0,0,1,1},　　{1,0,1,1,1,0,0,1,1,1},　　{1,1,0,0,1,1,0,0,0,1},</p&g

28、t;　　{1,0,1,1,0,0,1,1,0,1},　　{1,1,1,1,1,1,1,1,1,1}　　}; //入口坐標(biāo)為（1，1），出口坐標(biāo)為（6，8）　　typedef struct　　{ </p&

29、gt;　　int x,y;/*試探方向*/　　}item;　　item move[4]={{0,1},{1,0},{0,-1},{-1,0}};　　typedef struct/*棧的設(shè)計*/

30、　{　　int x,y,d; /*縱橫坐標(biāo)及方向*/　　}DataType;　　typedef struct/*棧*/　　{　　DataType data[MAXSIZE]

31、;　　int top;　　}SeqStack,*PSeqStack;　　PSeqStack Init_SeqStack(void)　　{ /*創(chuàng)建一順序棧，入口參數(shù)無，返回一個指向順序棧的指針，為零表示分配空間失敗*/</

32、p>　　PSeqStack S;　　S=(PSeqStack)malloc(sizeof(SeqStack));　　if (S)　　S->top= -1; 　　return S;

33、　　}　　int Empty_SeqStack(PSeqStack S)　　{ /*判斷棧是否為空，入口參數(shù)：順序棧，返回值：1表示為空，0表示非空*/　　if (S->top== -1) </p

34、>　　return 1;　　else 　　return 0;　　}　　int Push_S

35、eqStack (PSeqStack S, DataType x)　　{ /*在棧頂插入一新元素x，入口參數(shù)：順序棧，返回值：1表示入棧成功，0表示失敗。*/　　if (S->top==MAXSIZE-1)　　return 0; /*棧滿不能入棧*/<

36、b>　　else 　　{　　S->top++;　　S->data[S->top]=x;　　return 1;<

37、;/p>　　}　　}　　int Pop_SeqStack(PSeqStack S ,DataType *x)　　{ /*刪除棧頂元素并保存在*x，入口參數(shù)：順序棧，返回值：1表示出棧成功，0表示失敗。*

38、/　　if (Empty_SeqStack ( S ) )　　return 0; /*?？詹荒艹鰲?*/　　else　　{ 　　*x= S->d

39、ata[S->top];　　S->top--;　　return 1;　　} 　　}&

40、lt;p>　　void Destroy_SeqStack(PSeqStack *S)　　{　　if(*S)　　free(*S);

41、*S=NULL;　　return; 　　} 　　/*利用棧的非遞歸算法*/　　int mazepath(int maze [ ][n+2] ,item move[ ],int

42、 x0,int y0)　　{ /*求迷宮路徑, 入口參數(shù)：指向迷宮數(shù)組的指針，下標(biāo)移動的增量數(shù)組，開始點（x0，y0），到達點（m，n）, 返回值：1表示求出路徑，0表示無路徑*/　　PSeqStack S ;　　DataType temp ;　　int x, y

43、, d, i, j ;　　temp.x=x0 ;temp.y=y0 ; temp.d=-1 ;　　S=Init_SeqStack(); /*初始化棧*/　　if (!S)　　{ printf("棧初始化失敗")

44、;　　return(0);　　}　　Push_SeqStack (S,temp) ; /* 迷宮入口點入棧 */　　while (! Empty_SeqStack (S ) )

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

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

47、>　　Push_SeqStack ( S, temp ) ;/*點{x,y}可以走，用棧保存可以走的路徑*/　　x=i; y=j; maze[x][y]= -1;　　if (x==m&&y==n) /*迷宮有路*/　　{&l

48、t;p>　　while( !Empty_SeqStack(S) )　　{　　Pop_SeqStack (S,&temp) ;　　printf("(%d,%d)<- ",temp.x,temp.y) ;/*打印可走的路徑*/</p&

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

50、*/　　}　　else d++ ;/*試探下一個方向*/　　} /*while (d<4)*/　　} /*while */　　Destroy_SeqStack(&S); /

51、*銷毀棧*/　　return 0 ;/*迷宮無路*/　　} 　　/*遞歸算法*/　　int mazepath1(int maze[][n+2],item move[],int x,int y)&

52、lt;/p>　　{/*求迷宮路徑，入口參數(shù)：迷宮數(shù)組，下標(biāo)移動的增量數(shù)組，開始點（x，y），　　以及開始點對應(yīng)的步數(shù)step，（m,n）是終點，返回值：1表示求出路徑，0表示無路徑*/　　int i;　　int step=0;

53、　　step++;　　maze[x][y]=step;　　if(x==m&&y==n)　　return 1; /*起始位置是出口，找到路徑，結(jié)束*/　　f

54、or(i=0;i<4;i++)　　{　　if(maze[x+move[i].x][y+move[i].y]==0)　　if(mazepath(maze,move,x+move[i].x,y+move[i].y))　　return

55、 1; /*下一個是出口，則返回*/　　}　　step--;　　maze[x][y]=0;　　return 0;</p&

56、gt;　　}　　int main()　　{ int i,j,k;　　char u;　　int x,y; <

57、;p>　　printf("*****歡迎進入迷宮游戲*****\n");　　printf("下圖為一個6*8的迷宮：\n");　　printf("****************************\n");　　for(i=0;i<m+2

58、;i++)　　{ printf("****");　　for(j=0;j<n+2;j++)　　{ 　　printf("%-2d",maze[i][j]);<p

59、>　　}　　printf("****");　　printf("\n");　　}　　printf("*********************

60、*******\n");　　printf("現(xiàn)在開始游戲？（y/n）:");　　scanf("%c",&u); 　　while(u!='n')　　{</p

61、>　　printf("請輸入迷宮入口坐標(biāo)(x,y)：");　　scanf("%d,%d",&x,&y);　　printf("出口：(6,8)<-");　　k=mazepath(maze,move,x,y)

62、;　　printf("：入口\n");　　if(k==1)printf("恭喜！走出迷宮\n\n"); 　　else printf("迷宮無路\n\n");　　printf("繼續(xù)游戲:");

63、　　scanf("%c",&u); 　　printf("\n"); 　　} 　　return 0;<

64、;b>　　}　?。?）運行結(jié)果及調(diào)試分析　　運行結(jié)果達到預(yù)期結(jié)果達到，遞歸和非遞歸兩種方法求出一條走出迷宮的路徑，并將路徑輸出，并實現(xiàn)多次輸入入口點來驗證程序的可行性。　?。?）課程設(shè)計總結(jié)　　在這次實踐中遇

65、到了各種問題，碰到問題有時總是百思不得其解經(jīng)過反復(fù)測試，最終確定原因，導(dǎo)致數(shù)據(jù)無法更新。　　迷宮問題：是加深對棧運用的好程序。這個程序又加了個遞歸的算法，相同的程序不同的算法。我結(jié)合老師提過的思想與教材上的例子，很順利的完成了這個程序。其實在寫完這個程序后。　　皇天不負有心人，按照步驟，忙碌了兩周，在不斷地努力下，總算將此程序設(shè)計出來。盡管不完全是自己獨

66、立完成，但仍然很欣慰，因為在設(shè)計的過程中，讓我了解到要設(shè)計一個大型程序，查找資料是至關(guān)重要的，在他人的基礎(chǔ)上，再根據(jù)自己所學(xué)進行修改與調(diào)試，最后設(shè)計出自己想要的程序，這過程艱辛，但只要你持之以恒，定可將問題解決。通過本次實驗鞏固了課本的基本知識，熟練運用課程知識。提高我的組織數(shù)據(jù)及編寫程序的能力，使我能夠根據(jù)問題要求和數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，把現(xiàn)實世界中的問題在計算機內(nèi)部表示出來并用軟件解決問題，本次實驗大大提高了對編程的

眾賞文庫> 全部分類> 畢業(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)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告迷宮求解

文檔簡介

溫馨提示

最新文檔

評論

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告迷宮求解

文檔簡介

溫馨提示

最新文檔

評論

免費下載