課程設(shè)計(jì)迷宮求解

1、<p><b>　　目 錄</b></p><p><b>　　1 前言1</b></p><p><b>　　2 需求分析1</b></p><p>　　2.1課程設(shè)計(jì)目的1</p><p>　　2.2課程設(shè)計(jì)任務(wù)1</p><p>

2、;<b>　　2.3設(shè)計(jì)環(huán)境1</b></p><p><b>　　3 概要設(shè)計(jì)1</b></p><p>　　3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1</p><p><b>　　3.2模塊設(shè)計(jì)3</b></p><p><b>　　4 詳細(xì)設(shè)計(jì)3</b><

3、/p><p><b>　　5 測(cè)試分析8</b></p><p>　　6 課程設(shè)計(jì)總結(jié)10</p><p><b>　　參考文獻(xiàn)10</b></p><p><b>　　致 謝11</b></p><p><b>　　附 錄12<

4、;/b></p><p><b>　　程序代碼實(shí)現(xiàn)12</b></p><p><b>　　1 前言</b></p><p>　　設(shè)計(jì)一個(gè)簡(jiǎn)單迷宮程序，從入口出發(fā)，按某一方向向前探索，若能走通（未走過(guò)的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向；若所有方向均沒(méi)有通路，則沿原點(diǎn)返回前一點(diǎn)，換下一個(gè)方向在繼續(xù)試探

5、，直到所有可能的通路都探索到，或找到一條通路，或無(wú)路可走又返回到入口點(diǎn)。并利用兩種方法實(shí)現(xiàn)：一種用棧實(shí)現(xiàn)，另一種用隊(duì)列實(shí)現(xiàn)。</p><p><b>　　2 需求分析</b></p><p><b>　　2.1課程設(shè)計(jì)目的</b></p><p>　　學(xué)生在教師指導(dǎo)下運(yùn)用所學(xué)課程的知識(shí)來(lái)研究、解決一些具有一定綜合性問(wèn)題的專(zhuān)

6、業(yè)課題。通過(guò)課程設(shè)計(jì)（論文），提高學(xué)生綜合運(yùn)用所學(xué)知識(shí)來(lái)解決實(shí)際問(wèn)題、使用文獻(xiàn)資料、及進(jìn)行科學(xué)實(shí)驗(yàn)或技術(shù)設(shè)計(jì)的初步能力，為畢業(yè)設(shè)計(jì)（論文）打基礎(chǔ)。</p><p><b>　　2.2課程設(shè)計(jì)任務(wù)</b></p><p>　　給出一個(gè)任意大小的迷宮數(shù)據(jù)，求出一條走出迷宮的路徑，輸出迷宮并將所求路徑輸出。</p><p>　　要求用兩種方法實(shí)現(xiàn)：一

7、種用棧實(shí)現(xiàn)，另一種用隊(duì)列實(shí)現(xiàn)。</p><p><b>　　2.3設(shè)計(jì)環(huán)境</b></p><p>　?。?）WINDOWS 2000/2003/XP/7/Vista系統(tǒng)</p><p>　?。?）Visual C++或TC集成開(kāi)發(fā)環(huán)境</p><p><b>　　3 概要設(shè)計(jì)</b></p&

8、gt;<p><b>　　3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</b></p><p><b>　?。?）迷宮類(lèi)型</b></p><p>　　設(shè)迷宮為M行N列，利用maze[M][N]來(lái)表示一個(gè)迷宮，maze=0或1，其中0表示通路，1表示不通。當(dāng)從某點(diǎn)試探是，中間點(diǎn)有8個(gè)不同點(diǎn)可以試探，而四個(gè)角有3個(gè)方向，其他邊緣點(diǎn)有5個(gè)方向，為使問(wèn)題更容易分析

9、我們用maze[M+2][N+2]來(lái)表示迷宮，而迷宮四周的值全部為1。定義如下：</p><p>　　#define M 6 /*迷宮的實(shí)際行*/</p><p>　　#define N 8 /*迷宮的實(shí)際列*/</p><p>　　int maze[M+2][N+2];</p><p><b>　　（2）棧

10、的類(lèi)型定義</b></p><p>　　入口坐標(biāo)從（1,1），每個(gè)點(diǎn)有8個(gè)方向可以試探，若當(dāng)前點(diǎn)的坐標(biāo)為（x,y）,則與其相鄰的8個(gè)點(diǎn)坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到。因?yàn)槌隹谠赱M][N],因此規(guī)定試探順序?yàn)?從正東沿順時(shí)針?lè)较蜻M(jìn)行。為簡(jiǎn)化問(wèn)題，方便地求出新點(diǎn)的坐標(biāo)，將從正東方開(kāi)始沿順時(shí)針進(jìn)行的這8個(gè)方向的坐標(biāo)增量放一個(gè)結(jié)構(gòu)體數(shù)組move[8]中，在move數(shù)組中，每個(gè)元素有橫坐標(biāo)增量：x，縱坐標(biāo)

11、增量：y組成。定義如下：</p><p>　　Typedef struct </p><p><b>　　{</b></p><p><b>　　int x,y;</b></p><p><b>　　}item;</b></p><p>　　Item m

12、ove[8];</p><p>　　當(dāng)?shù)竭_(dá)了某點(diǎn)五路可走時(shí)需返回前一點(diǎn)，再?gòu)那耙稽c(diǎn)開(kāi)始向下一方向繼續(xù)試探，因此，壓入棧中的不僅是順序到達(dá)的個(gè)點(diǎn)坐標(biāo)，而且還要有從當(dāng)前點(diǎn)到下一個(gè)點(diǎn)的方向序號(hào)。因此定義棧棧中元素類(lèi)型有行、列、方向組成的三元組。定義如下：</p><p>　　typedef struct </p><p><b>　　{</b

13、></p><p>　　int x,y,d; //d 下一步方向</p><p>　　}elemtype;</p><p>　　Typedef struct </p><p><b>　　{ </b></p><p>　　elemtype data[MAXSIZE];&

14、lt;/p><p><b>　　int top;</b></p><p><b>　　}Sqstack;</b></p><p>　?。?）隊(duì)列的類(lèi)型定義</p><p>　　隊(duì)列的有關(guān)數(shù)據(jù)結(jié)構(gòu)、試探方向等和棧的求解方法處理基本相同。不同的是：如何存儲(chǔ)搜索路徑。在搜索過(guò)程中必須幾下每一個(gè)可到達(dá)的坐標(biāo)點(diǎn)，

15、以便從這些點(diǎn)出發(fā)繼續(xù)向四周搜索。到達(dá)迷宮的出口點(diǎn)（m,n）后，為能夠從出口沿搜索路徑回溯直至入口，對(duì)于每一點(diǎn)，記下坐標(biāo)點(diǎn)的同時(shí)，還要記下到達(dá)該點(diǎn)的前驅(qū)點(diǎn)，因此用一個(gè)結(jié)構(gòu)體數(shù)組ele[MAX]作為隊(duì)列的存儲(chǔ)空間，因?yàn)槊恳稽c(diǎn)至少被訪問(wèn)一次，所以MAX至多等于m*n。該結(jié)構(gòu)體有三個(gè)域：x、y和pre。其中x、y分別為所到達(dá)點(diǎn)的坐標(biāo)，pre為前驅(qū)點(diǎn)在elem中的下標(biāo)。除此之外，還需設(shè)定頭、尾指針，分別指向隊(duì)頭，隊(duì)尾。類(lèi)型定義如下：</p&

16、gt;<p>　　typedef struct //隊(duì)的相關(guān)類(lèi)型定義</p><p>　　{ int x,y;</p><p><b>　　int pre;</b></p><p>　　}Elemtype; </p><p>　　typedef str

17、uct //隊(duì)列的類(lèi)型定義</p><p>　　{ Elemtype elem[MAXSIZE];</p><p>　　int front,rear;</p><p><b>　　int len;</b></p><p><b>　　}SqQueue;</b></p><p

18、><b>　　3.2模塊設(shè)計(jì)</b></p><p>　　定義函數(shù)Zprintpath( ) 利用棧實(shí)現(xiàn)迷宮求解，用二維數(shù)組Maze[M+2][N+2]表示迷宮，move[8]表示坐標(biāo)增量數(shù)組。</p><p>　　定義函數(shù)DLmazepath( )，利用隊(duì)列實(shí)現(xiàn)迷宮求。</p><p>　　定義函數(shù)Zprintpath( )實(shí)現(xiàn)棧的迷宮

19、路徑輸出，棧中保存的就是一條迷宮的通路。</p><p>　　定義函數(shù)DLmazepath( )，實(shí)現(xiàn)隊(duì)列的迷宮路徑輸出。</p><p>　　定義函數(shù)InitStack( )實(shí)現(xiàn)棧的初始化。</p><p>　　定義函數(shù)Stackempty( )，判斷棧是否為空。為空返回1，否則返回0。 </p><p>　　定義函數(shù)Push( )，實(shí)現(xiàn)入

20、棧操作。</p><p>　　定義函數(shù)Pop( ),實(shí)現(xiàn)出棧操作。</p><p>　　定義函數(shù)InitQueue（），實(shí)現(xiàn)隊(duì)列的初始化。</p><p>　　定義函數(shù)QueueEmpty( )，判斷隊(duì)列是否為空，為空返回1，否則返回0.</p><p>　　定義函數(shù)GetHead (SqQueue q,Elemtype *e)，實(shí)現(xiàn)隊(duì)頭元素

21、的讀取。</p><p>　　定義函數(shù)EnQueue(SqQueue *q,Elemtype e)，實(shí)現(xiàn)入隊(duì)操作。</p><p>　　定義函數(shù)DeQueue(SqQueue *q,Elemtype *e)，實(shí)現(xiàn)出隊(duì)操作。</p><p>　　定義函數(shù)Sprint(int a[M+2][N+2])，實(shí)現(xiàn)，迷宮的輸出。</p><p><

22、b>　　4 詳細(xì)設(shè)計(jì)</b></p><p><b>　?。?）主函數(shù)</b></p><p>　　void main() </p><p><b>　　{</b></p><p>　　int a,i,j,maze2[M+2][N+2];</p><p>　

23、　int maze[M+2][N+2]={</p><p>　　{1,1,1,1,1,1,1,1,1,1},</p><p>　　{1,0,1,1,1,0,1,1,1,1},</p><p>　　{1,1,0,1,0,1,1,1,1,1},</p><p>　　{1,0,1,0,0,0,0,0,1,1},</p><p&g

24、t;　　{1,0,1,1,1,0,1,1,1,1},</p><p>　　{1,1,0,0,1,1,0,0,0,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}}; /*構(gòu)造一個(gè)迷宮*/ </p><p>　　item move[8]={{0,1},{1,

25、1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; /*坐標(biāo)增量數(shù)組move的初始化*/</p><p>　　為使得程序更加人性化，更加友好，因此可將系統(tǒng)輸出界面設(shè)置如下：</p><p>　　printf(" |*****************迷宮求解系統(tǒng)*****************|\n");</p>

26、<p>　　printf(" | 1 、棧方法 求解迷宮的路徑 |\n");</p><p>　　printf(" | 2 、隊(duì)列 求解的迷宮路徑 |\n");</p><p>　　printf(" | 3、 退出系統(tǒng)

27、 |\n");</p><p>　　printf("|**********************************************|\n");</p><p>　　printf("\t\n\n請(qǐng)選擇(0-3):"); scanf("%d",&a);</p>

28、<p>　　while(a!=3)</p><p><b>　　{</b></p><p><b>　　switch(a)</b></p><p><b>　　{</b></p><p>　　Case 1:Sprint(maze);printf(“路徑為：\n&q

29、uot;);Zmazepath(maze,move);break;</p><p>　　Case2:Sprint(maze2);printf("路徑：\n");DLmazepath(maze2,move);break;</p><p>　　default : printf("\t\t選擇錯(cuò)誤?。n");</p><p>&l

30、t;b>　　} </b></p><p>　　printf("\t\n請(qǐng)選擇(0-3).....\n"); scanf("%d",&a);</p><p><b>　　}</b></p><p>　　printf("\n\t\t非常感謝您的使用!\n");&l

31、t;/p><p><b>　　}</b></p><p>　　(2）利用棧實(shí)現(xiàn)迷宮求解算法的偽碼描述如下：</p><p>　　int Zmazepath_(int maze[M+2][N+2],item move[8])</p><p>　　/*若迷宮maze中存在從入口(1,1)到出口(M,N)的通道，則求得一條存放在棧

32、中，并返回1；否則返回0*/</p><p><b>　　{</b></p><p><b>　　棧初始化；</b></p><p>　　將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為-1）入棧；</p><p>　　while（棧不空）</p><p><b>　　{ 棧頂元

33、素出棧；</b></p><p>　　求出下一個(gè)要試探的方向d++；</p><p>　　while（還有剩余試探方向）</p><p>　　{ if（d方向可走）</p><p>　　則{ （x，y，d）入棧；</p><p>　　求新點(diǎn)坐標(biāo)（i，j）；</p><p>　　將新點(diǎn)

34、（i，j）切換為當(dāng)前點(diǎn)（x，y）；</p><p>　　if （點(diǎn)（x，y）為出口點(diǎn)）結(jié)束；</p><p>　　else 重置d=0；</p><p><b>　　}</b></p><p>　　else d++；</p><p><b>　　}</b></p>

35、;<p><b>　　}</b></p><p>　　Zprintpath(Sqstack s)//輸出迷宮路徑，棧中保存的就是一條迷宮的通路</p><p>　　{ elemtype temp;</p><p>　　printf("(%d,%d)<--",M,N);</p><

36、p>　　while(!Stackempty(s))</p><p>　　{ pop(&s,&temp);</p><p>　　printf("(%d,%d)<--",temp.x,temp.y);</p><p><b>　　}</b></p><p>　　printf(

37、"\n");</p><p><b>　　}</b></p><p><b>　　（3）棧的操作</b></p><p>　　void InitStack(SqStack *s) /*棧的初始化*/</p><p>　　{ 棧的成員top賦值為-1；}</p>&l

38、t;p>　　int StackEmpty(SqStack s) /*判?？?/</p><p>　　{ if（棧s成員為-1）返回 1；</p><p>　　Else 返回 0； }</p><p>　　int Pop(sqstack *s,Elemtype *e)/*實(shí)現(xiàn)出棧*/</p><p>　　{if(棧為空) {</p&

39、gt;<p>　　輸出提示棧為空；返回；</p><p>　　} 將棧內(nèi)成員賦值給e；</p><p><b>　　}</b></p><p>　?。?）利用隊(duì)列實(shí)現(xiàn)迷宮求解偽代碼如下：</p><p>　　int DLmazepath_(int maze[M+2][N+2],item move[8])&

40、lt;/p><p>　　/*采用隊(duì)列的迷宮算法。Maze[M+2][N+2]表示迷宮數(shù)組，move[8]表示坐標(biāo)增量數(shù)組*/</p><p><b>　　{</b></p><p><b>　　隊(duì)的初始化；</b></p><p>　　將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為-1）入隊(duì)；</p>

41、<p>　　While(隊(duì)不為空)</p><p><b>　　{ </b></p><p>　　For( 從1到8個(gè)方向) </p><p>　　求新坐標(biāo)點(diǎn)坐標(biāo)，并將可到達(dá)點(diǎn)分別入隊(duì)；</p><p>　　If（點(diǎn)（x,y）為出口點(diǎn)）結(jié)束輸出路徑，迷宮有路；</p><p>　　

42、當(dāng)前點(diǎn)搜索完8個(gè)方向后出隊(duì)；</p><p><b>　　}</b></p><p>　　Return o /*迷宮五路*/</p><p><b>　　}</b></p><p>　　void DLprintpath(SqQueue q)//輸出迷宮路徑，隊(duì)列中保存的就是一條迷宮的通路</p

43、><p>　　{ int i;</p><p>　　i=q.rear-1;</p><p><b>　　do</b></p><p>　　{printf("(%d,%d)<--",(q.elem[i]).x,(q.elem[i]).y);</p><p>　　i=(q.e

44、lem[i]).pre;</p><p>　　}while(i!=-1)</p><p>　　利用棧方法和隊(duì)列方法用到的是同一個(gè)迷宮數(shù)組，</p><p>　　在使用棧方法實(shí)現(xiàn)迷宮求解時(shí)，為避免死循環(huán)改變了原來(lái)的迷宮數(shù)組的個(gè)別路徑值，因此使用隊(duì)列求解時(shí)不能得到相應(yīng)的路徑解，為避免此，我們可在用棧方法求解迷宮路徑之前將數(shù)組賦值給另一個(gè)數(shù)組，這樣隊(duì)列求解迷宮時(shí)可以再原來(lái)

45、不改變的迷宮數(shù)組下進(jìn)行。具體實(shí)現(xiàn)代碼如下：</p><p>　　for(i=0;i<M+2;i++)</p><p>　　for(j=0;j<N+2;j++)</p><p>　　{ maze2[i][j]=maze[i][j];}</p><p><b>　?。?）隊(duì)列的操作</b></p>

46、<p>　　void InitQueue(SqQueue *q) /*隊(duì)列的初始化*/</p><p>　　{ 將隊(duì)中元素賦值為0；}</p><p>　　int QueueEmpty(SqQueue q) /*判隊(duì)空*/</p><p>　　{if（隊(duì)長(zhǎng)度為0） 返回 1；</p><p>　　Else 返回 0； }</p

47、><p>　　void GetHead (SqQueue q,ElemType *e)/*讀隊(duì)頭元素*/</p><p>　　{if（隊(duì)的長(zhǎng)度為0） 輸出提示隊(duì)列為空；</p><p>　　else 將隊(duì)中值賦給e；}</p><p>　　void EnQueue(SqQueue *q,ElemType e)/*入隊(duì)*/</p>

48、<p>　　{if（隊(duì)列長(zhǎng)度已滿(mǎn)）輸出提示；</p><p><b>　　else {</b></p><p>　　將e中元素賦給隊(duì)列；</p><p>　　隊(duì)尾指針指向下一個(gè)元素；隊(duì)長(zhǎng)加1；</p><p><b>　　}</b></p><p><b>

49、;　　}</b></p><p>　　void DeQueue(SqQueue *q,ElemType *e)/*出隊(duì)*/</p><p>　　{ if（判隊(duì)空） 輸出提示；</p><p><b>　　else</b></p><p>　　{將隊(duì)中元素賦給e；隊(duì)頭指向下一個(gè)元素；隊(duì)長(zhǎng)減1；} </

50、p><p><b>　　}</b></p><p><b>　　5 測(cè)試分析</b></p><p>　　測(cè)試數(shù)據(jù)及結(jié)果如下：</p><p>　　（1）系統(tǒng)友好界面輸出</p><p>　　圖5.1 進(jìn)入系統(tǒng)界面運(yùn)行結(jié)果</p><p>　?。?）分別選

51、擇1和2。運(yùn)行結(jié)果輸出如下：</p><p>　　圖5.2 迷宮以及使用棧和隊(duì)列求解迷宮路徑的輸出</p><p>　?。?）選擇3 運(yùn)行結(jié)果如下：</p><p>　　圖5.3 退出系統(tǒng)的運(yùn)行圖</p><p>　　根據(jù)結(jié)果分析：利用棧求得的路徑不一定是最短路徑，而用隊(duì)列求得的路徑是最短路徑。</p><p><

52、;b>　　6 課程設(shè)計(jì)總結(jié)</b></p><p>　　課程設(shè)計(jì)終于在本組組員共同的努力下完成了。通過(guò)本次課程設(shè)計(jì)讓我對(duì)棧和隊(duì)列這一章的知識(shí)有了進(jìn)一步了解，也讓我知道了用棧和隊(duì)列實(shí)現(xiàn)迷宮問(wèn)題的基本原理，知道了棧和隊(duì)列的不同存儲(chǔ)結(jié)構(gòu)的定義和算法描述，同時(shí)也學(xué)會(huì)了編寫(xiě)簡(jiǎn)單的迷宮問(wèn)題的程序。</p><p>　　說(shuō)實(shí)話(huà)，剛開(kāi)始看到題目時(shí)很茫然，根本不知道從何下手，但經(jīng)過(guò)本組組員

53、的探討和翻閱了一些相關(guān)資料問(wèn)題漸漸的清晰化了。通過(guò)這，讓我認(rèn)識(shí)到，問(wèn)題不是一下就能得到的，而是要通過(guò)探討和思考，問(wèn)題的解決需要通過(guò)一個(gè)這樣循序漸進(jìn)的過(guò)程。</p><p>　　此次程序也讓我更加意識(shí)到自己的不足，我所知道的，所懂的太少太少，需要我學(xué)習(xí)的還太多太多，雖然此次的程序不是很完美，但是總體還是一個(gè)比較能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)能力的程序了，當(dāng)然只是相對(duì)于我這個(gè)初學(xué)者來(lái)說(shuō)。在剛開(kāi)始編程的時(shí)候，我感到很力不從心，雖

54、然懂得了其相應(yīng)的算法和思想，但是卻不知道要怎樣安排程序的結(jié)構(gòu)、以及什么方法將其功能實(shí)現(xiàn)，更不知道要從哪里開(kāi)始著手進(jìn)行。申壽云老師說(shuō)的沒(méi)錯(cuò)，我們平時(shí)的學(xué)習(xí)中程序練習(xí)太少，寫(xiě)的太少，什么事不可能一蹴而就，都是通過(guò)一點(diǎn)一滴的鍛煉慢慢積累起來(lái)的。我想，在以后的學(xué)習(xí)中，我會(huì)更加注重實(shí)踐，注重多練，多積累，為自己的以后工作打下結(jié)實(shí)的基礎(chǔ)。</p><p><b>　　參考文獻(xiàn)</b></p>

55、<p>　　[1] 黃同成，黃俊民，董建寅．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國(guó)電力出版社，2008</p><p>　　[2] 董建寅，黃俊民，黃同成．?dāng)?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解[M]．北京：中國(guó)電力出版社，2008</p><p>　　[3] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 北京：清華大學(xué)出版社，2002</p><p>　　[4] 劉振鵬，張曉

56、莉，郝杰．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國(guó)鐵道出版社，2003</p><p><b>　　致 謝</b></p><p>　　在這次課程設(shè)計(jì)的撰寫(xiě)過(guò)程中，我得到了許多人的鼓勵(lì)和幫助，在此，我表示衷心的感謝。</p><p>　　首先，我要感謝我的指導(dǎo)老師申老師在課程設(shè)計(jì)上給予我的指導(dǎo)、和讓我知道了程序要多練多寫(xiě)才能出真知。更重要的是老師幫我解決了

57、很多算法上的難題，讓我把此次課程設(shè)計(jì)做得更加完善。在此期間，我不僅學(xué)到了新的知識(shí)，而且也開(kāi)闊了視野，提高了自己的設(shè)計(jì)能力。</p><p>　　然后，我要感謝我們組員們和給予過(guò)我?guī)椭淖钣H愛(ài)的同學(xué)們，依然記得，他們給我講程序的解題思路時(shí)專(zhuān)注的表情，依然記得我們組員一起探討問(wèn)題爭(zhēng)論著你對(duì)我錯(cuò)時(shí)的情景……因有了你們我才可以不斷進(jìn)步，不斷的讓自己更加完美。我的世界因?yàn)橛辛四銈兌迂S富，更加多彩。謝謝有你們。</

58、p><p>　　最后感謝我的母?！坳?yáng)學(xué)院，謝謝母校為我們提供了這樣一個(gè)環(huán)境，讓我們來(lái)自五湖四海的同學(xué)能相聚在一起，讓我們有課程設(shè)計(jì)這樣的經(jīng)歷。</p><p><b>　　謝謝你們 ！</b></p><p><b>　　附錄</b></p><p><b>　　具體程序代碼實(shí)現(xiàn)<

59、/b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h> </p><p>　　#define M 6</p><p>　　#define N 8</p><p>　　#define MAXSIZE 100</p>

60、<p>　　#define MAX M*N</p><p>　　typedef struct //棧的相關(guān)類(lèi)型定義 </p><p><b>　　{</b></p><p>　　int x,y,d; //d 下一步方向</p><p>　　}elemtype;</p><

61、;p>　　typedef struct </p><p><b>　　{ </b></p><p>　　elemtype data[MAXSIZE];</p><p><b>　　int top;</b></p><p><b>　　}Sqstack;</b>&

62、lt;/p><p>　　typedef struct </p><p><b>　　{</b></p><p><b>　　int x,y;</b></p><p><b>　　}item;</b></p><p>　　typedef struct

63、 //隊(duì)的相關(guān)類(lèi)型定義</p><p>　　{ int x,y;</p><p><b>　　int pre;</b></p><p>　　}Elemtype; </p><p>　　typedef struct //隊(duì)列的類(lèi)型定義</p><p&g

64、t;　　{ Elemtype elem[MAXSIZE];</p><p>　　int front,rear;</p><p><b>　　int len;</b></p><p>　　}SqQueue; </p><p>　　/* 棧函數(shù) */</p><p>　　void InitStac

65、k(Sqstack *s) //構(gòu)造空棧 </p><p><b>　　{ </b></p><p>　　s->top=-1; </p><p><b>　　} </b></p><p>　　int Stackempty(Sqstack s) //判斷棧是否為空 </p

66、><p><b>　　{ </b></p><p>　　if(s.top==-1) </p><p>　　return 1; </p><p><b>　　else </b></p><p>　　return 0; </p><p><b>　　

67、}</b></p><p>　　void push(Sqstack *s,elemtype e) //入棧</p><p><b>　　{ </b></p><p>　　if(s->top==MAXSIZE-1)</p><p>　　{ printf("Stack is

68、full\n");</p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　s->top++;</b></p><p>　　s->data[s->top].x=e.x;</p>

69、;<p>　　s->data[s->top].y=e.y;</p><p>　　s->data[s->top].d=e.d;</p><p><b>　　}</b></p><p>　　void pop (Sqstack *s,elemtype *e) // 出棧算法</p><p&

70、gt;<b>　　{ </b></p><p>　　if(s->top==-1)</p><p>　　{ printf("Stack is empty\n");</p><p><b>　　return;</b></p><p><b>　　}&

71、lt;/b></p><p>　　e->x=s->data[s->top].x;</p><p>　　e->y=s->data[s->top].y;</p><p>　　e->d=s->data[s->top].d;</p><p><b>　　s->top--;&l

72、t;/b></p><p><b>　　}</b></p><p>　　/* 隊(duì)函數(shù) */</p><p>　　void InitQueue(SqQueue *q) //隊(duì)的初始化</p><p>　　{ q->front=q->rear=0;</p><p><b&

73、gt;　　q->len=0;</b></p><p><b>　　}</b></p><p>　　int QueueEmpty(SqQueue q) //判斷隊(duì)空</p><p>　　{ if (q.len==0)</p><p><b>　　return 1;</b></

74、p><p>　　else return 0;</p><p><b>　　} </b></p><p>　　void GetHead (SqQueue q,Elemtype *e)//讀隊(duì)頭元素</p><p>　　{ if (q.len==0)</p><p>　　printf("Qu

75、eue is empty\n");</p><p><b>　　else</b></p><p>　　*e=q.elem[q.front];</p><p><b>　　}</b></p><p>　　void EnQueue(SqQueue *q,Elemtype e) //入隊(duì)<

76、;/p><p>　　{ if(q->len==MAXSIZE)</p><p>　　printf("Queue is full\n");</p><p><b>　　else </b></p><p>　　{q->elem[q->rear].x=e.x;q->elem[q->

77、;rear].y=e.y;q->elem[q->rear].pre=e.pre;</p><p>　　q->rear=q->rear+1;</p><p><b>　　q->len++;</b></p><p><b>　　}</b></p><p><b>

78、　　}</b></p><p>　　void DeQueue(SqQueue *q,Elemtype *e) //出隊(duì)</p><p>　　{ if(q->len==0)</p><p>　　printf("Queue is empty\n");</p><p><b>　　else <

79、;/b></p><p>　　{e->x=q->elem[q->rear].x;e->y=q->elem[q->rear].y;e->pre=q->elem[q->rear].pre;</p><p>　　q->front=q->front+1;</p><p><b>　　q->

80、;len--;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Sprint(int a[M+2][N+2])</p><p><b>　　{</b></p><p>&l

81、t;b>　　int i,j;</b></p><p>　　printf("迷宮為：\n");</p><p>　　for(i=0;i<M+2;i++)</p><p>　　{for(j=0;j<N+2;j++)</p><p>　　printf("%2d",a[i][j]

82、);</p><p>　　printf("\n");}</p><p><b>　　}</b></p><p>　　void Zprintpath(Sqstack s)//輸出迷宮路徑，棧中保存的就是一條迷宮的通路</p><p>　　{ elemtype temp;</p>&l

83、t;p>　　printf("(%d,%d)<--",M,N);</p><p>　　while(!Stackempty(s))</p><p>　　{ pop(&s,&temp);</p><p>　　printf("(%d,%d)<--",temp.x,temp.y);</p>

84、<p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void Zmazepath(int maze[M+2][N+2],item move[8]) //棧的迷宮求解輸出</p><p

85、><b>　　{ </b></p><p>　　Sqstack s;</p><p>　　elemtype temp;int x,y,d,i,j;</p><p>　　InitStack(&s);//棧的初始化</p><p>　　temp.x=1;temp.y=1;temp.d=-1;</p>

86、;<p>　　push(&s,temp);</p><p>　　while(!Stackempty (s))</p><p>　　{ pop(&s,&temp);</p><p>　　x=temp.x;y=temp.y;d=temp.d+1;</p><p>　　while(d<8)</p

87、><p>　　{ i=x+move[d].x;</p><p>　　j=y+move[d].y;</p><p>　　if(maze[i][j]==0)</p><p>　　{ temp.x=x;temp.y=y;temp.d=d;</p><p>　　push(&s,temp);</p>&l

88、t;p><b>　　x=i;y=j;</b></p><p>　　maze[x][y]=-1;</p><p>　　if(x==M&&y==N)</p><p>　　{ Zprintpath(s);</p><p><b>　　return;</b></p>

89、<p><b>　　}</b></p><p><b>　　else d=0;</b></p><p><b>　　}//if</b></p><p><b>　　else d++;</b></p><p><b>　　}//while

90、</b></p><p><b>　　} //while</b></p><p><b>　　return;</b></p><p>　　printf("迷宮無(wú)路\n");return;</p><p><b>　　}</b></p>

91、<p>　　void DLprintpath(SqQueue q)//輸出迷宮路徑，隊(duì)列中保存的就是一條迷宮的通路</p><p>　　{ int i;</p><p>　　i=q.rear-1;</p><p><b>　　do</b></p><p>　　{printf("(%d,%d)&

92、lt;--",(q.elem[i]).x,(q.elem[i]).y);</p><p>　　i=(q.elem[i]).pre;} while(i!=-1);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void DLmaze

93、path(int maze1[M+2][N+2],item move[8]) //隊(duì)列的迷宮求解</p><p>　　{ SqQueue q;</p><p>　　Elemtype head,e;</p><p>　　int x,y,v,i,j;</p><p>　　InitQueue(&q); //隊(duì)列的初始化</p&g

94、t;<p>　　e.x=1;e.y=1;e.pre=-1;</p><p>　　EnQueue (&q,e);</p><p>　　maze1[1][1]=-1;</p><p>　　while(!QueueEmpty (q))</p><p>　　{ GetHead(q,&head);</p>

95、<p>　　x=head.x;y=head.y;</p><p>　　for(v=0;v<8;v++)</p><p>　　{ i=x+move[v].x;</p><p>　　j=y+move[v].y;</p><p>　　if(maze1[i][j]==0)</p><p>　　{ e.x=

96、i;e.y=j;e.pre=q.front;</p><p>　　EnQueue(&q,e);</p><p>　　maze1[x][y]=-1;</p><p>　　} //if</p><p>　　if(i==M&&j==N)</p><p>　　{ DLprintpath(

97、q);</p><p><b>　　return ;</b></p><p><b>　　}</b></p><p><b>　　} //for</b></p><p>　　DeQueue(&q,&head);</p><p><

98、b>　　}//while</b></p><p>　　printf("迷宮無(wú)路!\n");return;}</p><p>　　void main() </p><p>　　{ int a,i,j,maze2[M+2][N+2];</p><p>　　int maze[M+2][N+2]={</

99、p><p>　　{1,1,1,1,1,1,1,1,1,1},</p><p>　　{1,0,1,1,1,0,1,1,1,1},</p><p>　　{1,1,0,1,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,1,1,1,1},

100、</p><p>　　{1,1,0,0,1,1,0,0,0,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}}; /*構(gòu)造一個(gè)迷宮*/ </p><p>　　item move[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1

101、,-1},{-1,0},{-1,1}}; /*坐標(biāo)增量數(shù)組move的初始化*/</p><p>　　for(i=0;i<M+2;i++)</p><p>　　for(j=0;j<N+2;j++)</p><p>　　{ maze2[i][j]=maze[i][j];}</p><p>　　printf(" |***

102、**************迷宮求解系統(tǒng)*****************|\n");</p><p>　　printf(" | |\n");</p><p>　　printf(" | 1 、棧方法 求解迷宮的路徑

103、 |\n");</p><p>　　printf(" | |\n");</p><p>　　printf(" | 2 、隊(duì)列 求解的迷宮路徑 |\n");</p><p>

104、　　printf(" | |\n");</p><p>　　printf(" | 3、 退出系統(tǒng) |\n");</p><p>　　printf(" |

105、 |\n");</p><p>　　printf(" |**********************************************|\n");</p><p>　　printf(" \t\n\n請(qǐng)選擇(0-3):"); scanf(&quo

106、t;%d",&a);</p><p>　　while(a!=3)</p><p>　　{ switch(a)</p><p>　　{ case 1:Sprint(maze); printf("求解路徑為：\n");Zmazepath(maze,move);break;</p><p>　

107、　case 2:printf("求解路徑為：\n");DLmazepath(maze2,move);break;</p><p>　　default : printf("\t\t選擇錯(cuò)誤?。n");}</p><p>　　printf("\t\n請(qǐng)選擇(0-3)："); scanf("%d",&a);