用棧方法、隊(duì)列方法求解迷宮問題

1、目 錄1 前言12 需求分析12.1課程設(shè)計(jì)目的12.2課程設(shè)計(jì)任務(wù)12.3設(shè)計(jì)環(huán)境13 概要設(shè)計(jì)13.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)13.2模塊設(shè)計(jì)24 詳細(xì)設(shè)計(jì)341數(shù)據(jù)類型的定義342主要模塊的算法描述35 測試分析66 課程設(shè)計(jì)總結(jié)7參考文獻(xiàn)8致 謝8附 錄（程序代碼實(shí)現(xiàn)）91 前言設(shè)計(jì)一個(gè)簡單迷宮程序，從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向；若所有方向均沒有通路，則沿原點(diǎn)返回前一點(diǎn)，換下一個(gè)方向在繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點(diǎn)。并利用兩種方法實(shí)現(xiàn)：一種用棧實(shí)現(xiàn)，另一種用隊(duì)列實(shí)現(xiàn)。2 需求分析2

2、.1課程設(shè)計(jì)目的學(xué)生在教師指導(dǎo)下運(yùn)用所學(xué)課程的知識(shí)來研究、解決一些具有一定綜合性問題的專業(yè)課題。通過課程設(shè)計(jì)（論文），提高學(xué)生綜合運(yùn)用所學(xué)知識(shí)來解決實(shí)際問題、使用文獻(xiàn)資料、及進(jìn)行科學(xué)實(shí)驗(yàn)或技術(shù)設(shè)計(jì)的初步能力，為畢業(yè)設(shè)計(jì)（論文）打基礎(chǔ)。2.2課程設(shè)計(jì)任務(wù)給出一個(gè)任意大小的迷宮數(shù)據(jù)，求出一條走出迷宮的路徑，輸出迷宮并將所求路徑輸出。要求用兩種方法實(shí)現(xiàn)：一種用棧實(shí)現(xiàn)，另一種用隊(duì)列實(shí)現(xiàn)。，我主要負(fù)責(zé)隊(duì)列方面2.3設(shè)計(jì)環(huán)境（1）WINDOWS 2000/2003/XP/7/Vista系統(tǒng)（2）Visual C+或TC集成開發(fā)環(huán)境3 概要設(shè)計(jì)3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（1）迷宮類型設(shè)迷宮為M行N列，利用mazeM

3、N來表示一個(gè)迷宮，maze=0或1，其中0表示通路，1表示不通。當(dāng)從某點(diǎn)試探是，中間點(diǎn)有8個(gè)不同點(diǎn)可以試探，而四個(gè)角有3個(gè)方向，其他邊緣點(diǎn)有5個(gè)方向，為使問題更容易分析我們用mazeM+2N+2來表示迷宮，而迷宮四周的值全部為1。定義如下：#define M 6 /*迷宮的實(shí)際行*/#define N 8 /*迷宮的實(shí)際列*/int mazeM+2N+2;（2）隊(duì)列的類型定義隊(duì)列的有關(guān)數(shù)據(jù)結(jié)構(gòu)、試探方向等和棧的求解方法處理基本相同。不同的是：如何存儲(chǔ)搜索路徑。在搜索過程中必須幾下每一個(gè)可到達(dá)的坐標(biāo)點(diǎn)，以便從這些點(diǎn)出發(fā)繼續(xù)向四周搜索。到達(dá)迷宮的出口點(diǎn)（m,n）后，為能夠從出口沿搜索路徑回溯直至入

4、口，對于每一點(diǎn)，記下坐標(biāo)點(diǎn)的同時(shí)，還要記下到達(dá)該點(diǎn)的前驅(qū)點(diǎn)，因此用一個(gè)結(jié)構(gòu)體數(shù)組eleMAX作為隊(duì)列的存儲(chǔ)空間，因?yàn)槊恳稽c(diǎ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ì)尾。類型定義如下：typedef struct /隊(duì)的相關(guān)類型定義 int x,y; int pre;Elemtype; typedef struct /隊(duì)列的類型定義 Elemtype elemMAXSIZE; int front,rear; int len;SqQueue;3.2模塊設(shè)

5、計(jì)定義函數(shù)DLmazepath( )，利用隊(duì)列實(shí)現(xiàn)迷宮求。定義函數(shù)DLmazepath( )，實(shí)現(xiàn)隊(duì)列的迷宮路徑輸出。定義函數(shù)InitQueue（），實(shí)現(xiàn)隊(duì)列的初始化。定義函數(shù)QueueEmpty( )，判斷隊(duì)列是否為空，為空返回1，否則返回0.定義函數(shù)GetHead (SqQueue q,Elemtype *e)，實(shí)現(xiàn)隊(duì)頭元素的讀取。定義函數(shù)EnQueue(SqQueue *q,Elemtype e)，實(shí)現(xiàn)入隊(duì)操作。定義函數(shù)DeQueue(SqQueue *q,Elemtype *e)，實(shí)現(xiàn)出隊(duì)操作。定義函數(shù)Sprint(int aM+2N+2)，實(shí)現(xiàn)，迷宮的輸出。4 詳細(xì)設(shè)計(jì)（1）主函數(shù)v

6、oid main() int a,i,j,maze2M+2N+2;/*構(gòu)造一個(gè)迷宮*/ int mazeM+2N+2= 1,1,1,1,1,1,1,1,1,1, 1,0,1,1,1,0,1,1,1,1, 1,1,0,1,0,1,1,1,1,1, 1,0,1,0,0,0,0,0,1,1, 1,0,1,1,1,0,1,1,1,1, 1,1,0,0,1,1,0,0,0,1, 1,0,1,1,0,0,1,1,0,1, 1,1,1,1,1,1,1,1,1,1; item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1; /*坐標(biāo)增量數(shù)組move的初始化*/為使得程

7、序更加人性化，更加友好，因此可將系統(tǒng)輸出界面設(shè)置如下： printf( |*迷宮求解系統(tǒng)*|n); printf( | 1 、棧方法 求解迷宮的路徑 |n); printf( | 2 、隊(duì)列 求解的迷宮路徑 |n); printf( | 3、 退出系統(tǒng) |n); printf( |*|n);printf(tnn請選擇(0-3):); scanf(%d,&a);while(a!=3) switch(a) Case 1:Sprint(maze);printf(“路徑為：n); Zmazepath(maze,move);break; Case2:Sprint(maze2);printf(路徑：n);

8、 DLmazepath(maze2,move);break; default : printf(tt選擇錯(cuò)誤！n); printf(tn請選擇(0-3).n); scanf(%d,&a); printf(ntt非常感謝您的使用!n);（2）利用隊(duì)列實(shí)現(xiàn)迷宮求解偽代碼如下：int DLmazepath_(int mazeM+2N+2,item move8)/*采用隊(duì)列的迷宮算法。MazeM+2N+2表示迷宮數(shù)組，move8表示坐標(biāo)增量數(shù)組*/ 隊(duì)的初始化； 將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為-1）入隊(duì)； While(隊(duì)不為空) For( 從1到8個(gè)方向) 求新坐標(biāo)點(diǎn)坐標(biāo)，并將可到達(dá)點(diǎn)分別入隊(duì)；

9、If（點(diǎn)（x,y）為出口點(diǎn)）結(jié)束輸出路徑，迷宮有路； 當(dāng)前點(diǎn)搜索完8個(gè)方向后出隊(duì)； Return o /*迷宮五路*/void DLprintpath(SqQueue q)/輸出迷宮路徑，隊(duì)列中保存的就是一條迷宮的通路 int i; i=q.rear-1; do printf(%d,%d)-,(q.elemi).x,(q.elemi).y); i=(q.elemi).pre; while(i!=-1)利用棧方法和隊(duì)列方法用到的是同一個(gè)迷宮數(shù)組，在使用棧方法實(shí)現(xiàn)迷宮求解時(shí)，為避免死循環(huán)改變了原來的迷宮數(shù)組的個(gè)別路徑值，因此使用隊(duì)列求解時(shí)不能得到相應(yīng)的路徑解，為避免此，我們可在用棧方法求解迷宮路徑

10、之前將數(shù)組賦值給另一個(gè)數(shù)組，這樣隊(duì)列求解迷宮時(shí)可以再原來不改變的迷宮數(shù)組下進(jìn)行。具體實(shí)現(xiàn)代碼如下： for(i=0;iM+2;i+) for(j=0;jN+2;j+) maze2ij=mazeij;（3）隊(duì)列的操作void InitQueue(SqQueue *q) /*隊(duì)列的初始化*/ 將隊(duì)中元素賦值為0；int QueueEmpty(SqQueue q) /*判隊(duì)空*/ if（隊(duì)長度為0） 返回 1； else 返回 0； void GetHead (SqQueue q,ElemType *e)/*讀隊(duì)頭元素*/ if（隊(duì)的長度為0） 輸出提示隊(duì)列為空； else 將隊(duì)中值賦給e； voi

11、d EnQueue(SqQueue *q,ElemType e)/*入隊(duì)*/ if（隊(duì)列長度已滿）輸出提示； else 將e中元素賦給隊(duì)列； 隊(duì)尾指針指向下一個(gè)元素；隊(duì)長加1； void DeQueue(SqQueue *q,ElemType *e)/*出隊(duì)*/ if（判隊(duì)空） 輸出提示； else 將隊(duì)中元素賦給e；隊(duì)頭指向下一個(gè)元素；隊(duì)長減1； 5 測試分析測試數(shù)據(jù)及結(jié)果如下：（1）系統(tǒng)友好界面輸出 圖5.1 進(jìn)入系統(tǒng)界面運(yùn)行結(jié)果（2）選擇1,運(yùn)行結(jié)果輸出如下： 圖5.2 迷宮以及使用棧求解迷宮路徑的輸出（3）選擇2、3 運(yùn)行結(jié)果如下： 圖5.3 迷宮以及使用隊(duì)列求解迷宮路徑的輸出（4）選

12、擇3運(yùn)行結(jié)果如下： 圖5.3 退出程序 根據(jù)結(jié)果分析：利用棧求得的路徑不一定是最短路徑，而用隊(duì)列求得的路徑是最短路徑。6 課程設(shè)計(jì)總結(jié)課程設(shè)計(jì)終于在本組組員共同的努力下完成了。通過本次課程設(shè)計(jì)讓我對棧和隊(duì)列這一章的知識(shí)有了進(jìn)一步了解，也讓我知道了用棧和隊(duì)列實(shí)現(xiàn)迷宮問題的基本原理，知道了棧和隊(duì)列的不同存儲(chǔ)結(jié)構(gòu)的定義和算法描述，同時(shí)也學(xué)會(huì)了編寫簡單的迷宮問題的程序。選了題目之后，我感覺題目之前已經(jīng)做過一點(diǎn)相關(guān)的實(shí)驗(yàn)，本以為很快就能搞好，但是，真正做起來才感覺沒有那么簡單，讓我更加意識(shí)到自己的不足，我所知道的，所懂的太少了。在剛開始編程的時(shí)候，我感到有點(diǎn)迷茫，雖然懂得了其相應(yīng)的算法和思想，但是卻不知

13、道要怎樣安排程序的結(jié)構(gòu)、以及什么方法將其功能實(shí)現(xiàn)，更不知道要從哪里開始著手進(jìn)行。老師說的沒錯(cuò)，我們平時(shí)的學(xué)習(xí)中程序練習(xí)太少，寫的太少，什么事不可能一蹴而就，都是通過一點(diǎn)一滴的鍛煉慢慢積累起來的。所以我覺得在以后的學(xué)習(xí)中，我會(huì)更加注重實(shí)踐，注重多練，多積累，為自己的以后工作打下結(jié)實(shí)的基礎(chǔ)。參考文獻(xiàn)1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)M北京：中國電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解M北京：中國電力出版社，20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）M. 北京：清華大學(xué)出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M北京：中國鐵道出版社，2003致 謝在這次課程

14、設(shè)計(jì)的撰寫過程中，我得到了許多人的鼓勵(lì)和幫助，在此，我表示衷心的感謝。首先，我要感謝我的指導(dǎo)老師黃同城老師，他在課程設(shè)計(jì)上給予我的很大的幫助，指導(dǎo)課程設(shè)計(jì)的具體實(shí)現(xiàn)方向。并且為我分析部分比較難懂的地方，讓我把此次課程設(shè)計(jì)做得更加完善。在此期間，我對迷宮問題有了更深刻的認(rèn)識(shí)，而且也明白了很多做課程設(shè)計(jì)需要注意的地方，讓我變得更嚴(yán)謹(jǐn)。然后，我要感謝我們第一大組組員們，在組內(nèi)討論時(shí)，他們各抒己見，思路發(fā)散，討論時(shí)錙銖必較，正是因?yàn)檫@份熱情，我們對這次的課程設(shè)計(jì)充滿了激情，方向也很明確。在匯報(bào)進(jìn)程的時(shí)候，組內(nèi)積極討論，相互競爭，優(yōu)缺互補(bǔ)，讓我們的課程設(shè)計(jì)更加完美，讓我們自己在討論中知道自己的優(yōu)點(diǎn)，認(rèn)識(shí)

15、自己的缺點(diǎn)，不斷完善自己。最后感謝我的母校邵陽學(xué)院，謝謝母校為我們提供了這樣一個(gè)環(huán)境，讓同學(xué)們能相聚在一起，讓我們有這樣一起奮斗共同完成目標(biāo)的經(jīng)歷。附錄 具體程序代碼實(shí)現(xiàn)#include#include #define M 6#define N 8#define MAXSIZE 100#define MAX M*Ntypedef struct /棧的相關(guān)類型定義 int x,y,d; /d 下一步方向 elemtype;typedef struct elemtype dataMAXSIZE; int top; Sqstack;typedef struct int x,y; item;typed

16、ef struct /隊(duì)的相關(guān)類型定義 int x,y; int pre; Elemtype; typedef struct /隊(duì)列的類型定義 Elemtype elemMAXSIZE; int front,rear; int len; SqQueue; /* 棧函數(shù) */void InitStack(Sqstack *s) /構(gòu)造空棧 s-top=-1; int Stackempty(Sqstack s) /判斷棧是否為空 if(s.top=-1) return 1; else return 0; void push(Sqstack *s,elemtype e) /入棧 if(s-top=M

17、AXSIZE-1) printf(Stack is fulln); return; s-top+; s-datas-top.x=e.x; s-datas-top.y=e.y; s-datas-top.d=e.d;void pop (Sqstack *s,elemtype *e) / 出棧算法 if(s-top=-1) printf(Stack is emptyn); return; e-x=s-datas-top.x; e-y=s-datas-top.y; e-d=s-datas-top.d; s-top-;/* 隊(duì)函數(shù) */void InitQueue(SqQueue *q) /隊(duì)的初始化

18、q-front=q-rear=0; q-len=0;int QueueEmpty(SqQueue q) /判斷隊(duì)空 if (q.len=0) return 1; else return 0; void GetHead (SqQueue q,Elemtype *e)/讀隊(duì)頭元素 if (q.len=0) printf(Queue is emptyn); else *e=q.elemq.front;void EnQueue(SqQueue *q,Elemtype e) /入隊(duì) if(q-len=MAXSIZE) printf(Queue is fulln); else q-elemq-rear.x

19、=e.x;q-elemq-rear.y=e.y; q-elemq-rear.pre=e.pre;q-rear=q-rear+1; q-len+; void DeQueue(SqQueue *q,Elemtype *e) /出隊(duì) if(q-len=0) printf(Queue is emptyn); else e-x=q-elemq-rear.x;e-y=q-elemq-rear.y; e-pre=q-elemq-rear.pre;q-front=q-front+1; q-len-; void Sprint(int aM+2N+2) int i,j; printf(迷宮為：n); for(i=

20、0;iM+2;i+) for(j=0;jN+2;j+) printf(%2d,aij); printf(n); void Zprintpath(Sqstack s)/輸出迷宮路徑，棧中保存的就是一條迷宮 的通路 elemtype temp; printf(%d,%d)-,M,N); while(!Stackempty(s) pop(&s,&temp); printf(%d,%d)-,temp.x,temp.y);printf(n); void Zmazepath(int mazeM+2N+2,item move8) /棧的迷宮求解輸出 Sqstack s; elemtype temp;int

21、x,y,d,i,j; InitStack(&s);/棧的初始化 temp.x=1;temp.y=1;temp.d=-1; push(&s,temp); while(!Stackempty (s) pop(&s,&temp); x=temp.x;y=temp.y;d=temp.d+1; while(d8) i=x+moved.x; j=y+moved.y; if(mazeij=0) temp.x=x;temp.y=y;temp.d=d; push(&s,temp); x=i;y=j; mazexy=-1; if(x=M&y=N) Zprintpath(s); return； else d=0;/

22、if else d+; /while /while return; printf(迷宮無路n);return;void DLprintpath(SqQueue q)/輸出迷宮路徑，隊(duì)列中保存的就是一條迷宮的通路int i; i=q.rear-1; do printf(%d,%d)-,(q.elemi).x,(q.elemi).y); i=(q.elemi).pre; while(i!=-1); printf(n);void DLmazepath(int maze1M+2N+2,item move8) /隊(duì)列的迷宮求解 SqQueue q; Elemtype head,e; int x,y,v,

23、i,j; InitQueue(&q); /隊(duì)列的初始化 e.x=1;e.y=1;e.pre=-1; EnQueue (&q,e); maze111=-1; while(!QueueEmpty (q) GetHead(q,&head); x=head.x;y=head.y; for(v=0;v8;v+) i=x+movev.x; j=y+movev.y; if(maze1ij=0) e.x=i;e.y=j;e.pre=q.front; EnQueue(&q,e); maze1xy=-1; /if if(i=M&j=N) DLprintpath(q); return ; /for DeQueue(&q,&head); /while printf(迷宮無路!n); return;void ma