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

1、<p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　題目： 迷宮設(shè)計(jì) </p><p>　　學(xué) 號(hào)： </p><p>　　姓 名： </p&

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

3、;　　完成時(shí)間： 2013年 12 月----2014 年 1 月</p><p><b>　　年 月 日</b></p><p>　　課程設(shè)計(jì)任務(wù)書(shū)及成績(jī)?cè)u(píng)定</p><p><b>　　目 錄</b></p><p>　　迷宮求解····

4、3;···························</p><p>　　問(wèn)題描述·····

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

6、83;·</p><p>　　需求分析及設(shè)計(jì)思路······························

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

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

9、#183;················</p><p>　?。?）源代碼···············

10、·······························</p><p>　?。?）運(yùn)行結(jié)果及調(diào)試分

11、析 ································</p><p>　　（7）

12、課程設(shè)計(jì)總結(jié) ·····························</p><p><b>　　一．迷宮求解&

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

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

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

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

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

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

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

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

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

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

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

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

25、b>　　輸出可走的路徑</b></p><p><b>　　}</b></p><p><b>　　（5）源代碼</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p>

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

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

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

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

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

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

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

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

34、><p><b>　　return 1;</b></p><p><b>　　else </b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int Push_S

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

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

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

38、/</p><p>　　if (Empty_SeqStack ( S ) )</p><p>　　return 0; /*棧空不能出棧 */</p><p><b>　　else</b></p><p><b>　　{ </b></p><p>　　*x= S->d

39、ata[S->top];</p><p><b>　　S->top--;</b></p><p><b>　　return 1;</b></p><p><b>　　} </b></p><p><b>　　}</b></p>&

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

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

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

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

44、;</p><p>　　return(0);</p><p><b>　　}</b></p><p>　　Push_SeqStack (S,temp) ; /* 迷宮入口點(diǎn)入棧 */</p><p>　　while (! Empty_SeqStack (S ) )</p><p><b>

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

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

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

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

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

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

51、*銷(xiāo)毀棧*/</p><p>　　return 0 ;/*迷宮無(wú)路*/</p><p><b>　　} </b></p><p><b>　　/*遞歸算法*/</b></p><p>　　int mazepath1(int maze[][n+2],item move[],int x,int y)&

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

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

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

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

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

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

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

59、><b>　　}</b></p><p>　　printf("****");</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("*********************

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

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

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

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

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

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

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