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

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ù)類(lèi)型的定義342主要模塊的算法描述35 測(cè)試分析66 課程設(shè)計(jì)總結(jié)7參考文獻(xiàn)8致 謝8附 錄（程序代碼實(shí)現(xiàn)）91 前言設(shè)計(jì)一個(gè)簡(jiǎn)單迷宮程序，從入口出發(fā)，按某一方向向前探索，若能走通（未走過(guò)的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向；若所有方向均沒(méi)有通路，則沿原點(diǎn)返回前一點(diǎn)，換下一個(gè)方向在繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無(wú)路可走又返回到入口點(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í)來(lái)研究、解決一些具有一定綜合性問(wèn)題的專(zhuān)業(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ǔ)。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集成開(kāi)發(fā)環(huán)境3 概要設(shè)計(jì)3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（1）迷宮類(lèi)型設(shè)迷宮為m行n列，利用mazem

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

4、口，對(duì)于每一點(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)至少被訪(fǎng)問(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)型定義如下：typedef struct /隊(duì)的相關(guān)類(lèi)型定義 int x,y; int pre;elemtype; typedef struct /隊(duì)列的類(lèi)型定義 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請(qǐng)選擇(0-3):"); scanf("%d",&a);while(a!=3) switch(a) case 1:sp

8、rint(maze);printf(“路徑為：n"); zmazepath(maze,move);break; case2:sprint(maze2);printf("路徑：n"); dlmazepath(maze2,move);break; default : printf("tt選擇錯(cuò)誤！n"); printf("tn請(qǐng)選擇(0-3).n"); scanf("%d",&a); printf("ntt非常感謝您的使用!n");（2）利用隊(duì)列實(shí)現(xiàn)迷宮求解偽代碼如下：int dl

9、mazepath_(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ì)； 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(&qu

10、ot;(%d,%d)<-",(q.elemi).x,(q.elemi).y); i=(q.elemi).pre; while(i!=-1)利用棧方法和隊(duì)列方法用到的是同一個(gè)迷宮數(shù)組，在使用棧方法實(shí)現(xiàn)迷宮求解時(shí)，為避免死循環(huán)改變了原來(lái)的迷宮數(shù)組的個(gè)別路徑值，因此使用隊(duì)列求解時(shí)不能得到相應(yīng)的路徑解，為避免此，我們可在用棧方法求解迷宮路徑之前將數(shù)組賦值給另一個(gè)數(shù)組，這樣隊(duì)列求解迷宮時(shí)可以再原來(lái)不改變的迷宮數(shù)組下進(jìn)行。具體實(shí)現(xiàn)代碼如下： for(i=0;i<m+2;i+) for(j=0;j<n+2;j+) maze2ij=mazeij;（3）隊(duì)列的操作void initq

11、ueue(sqqueue *q) /*隊(duì)列的初始化*/ 將隊(duì)中元素賦值為0；int queueempty(sqqueue q) /*判隊(duì)空*/ if（隊(duì)長(zhǎng)度為0） 返回 1； else 返回 0； void gethead (sqqueue q,elemtype *e)/*讀隊(duì)頭元素*/ if（隊(duì)的長(zhǎng)度為0） 輸出提示隊(duì)列為空； else 將隊(duì)中值賦給e； void enqueue(sqqueue *q,elemtype e)/*入隊(duì)*/ if（隊(duì)列長(zhǎng)度已滿(mǎn)）輸出提示； else 將e中元素賦給隊(duì)列； 隊(duì)尾指針指向下一個(gè)元素；隊(duì)長(zhǎng)加1； void dequeue(sqqueue *q,elem

12、type *e)/*出隊(duì)*/ if（判隊(duì)空） 輸出提示； else 將隊(duì)中元素賦給e；隊(duì)頭指向下一個(gè)元素；隊(duì)長(zhǎng)減1； 5 測(cè)試分析測(cè)試數(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）選擇3運(yùn)行結(jié)果如下： 圖5.3 退出程序 根據(jù)結(jié)果分析：利用棧求得的路徑不一定是最短路徑，而用隊(duì)列求得的路徑是最短路徑。6 課程設(shè)計(jì)總結(jié)課程設(shè)計(jì)終于在本組組員共同的努力下完成了。通過(guò)本次課程設(shè)計(jì)讓我對(duì)棧和隊(duì)列這一章的知識(shí)有了進(jìn)一步了解，

13、也讓我知道了用棧和隊(duì)列實(shí)現(xiàn)迷宮問(wèn)題的基本原理，知道了棧和隊(duì)列的不同存儲(chǔ)結(jié)構(gòu)的定義和算法描述，同時(shí)也學(xué)會(huì)了編寫(xiě)簡(jiǎn)單的迷宮問(wèn)題的程序。選了題目之后，我感覺(jué)題目之前已經(jīng)做過(guò)一點(diǎn)相關(guān)的實(shí)驗(yàn)，本以為很快就能搞好，但是，真正做起來(lái)才感覺(jué)沒(méi)有那么簡(jiǎn)單，讓我更加意識(shí)到自己的不足，我所知道的，所懂的太少了。在剛開(kāi)始編程的時(shí)候，我感到有點(diǎn)迷茫，雖然懂得了其相應(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)的。所以我覺(jué)得在以后的學(xué)習(xí)中，我會(huì)更加注重實(shí)

14、踐，注重多練，多積累，為自己的以后工作打下結(jié)實(shí)的基礎(chǔ)。參考文獻(xiàn)1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)m北京：中國(guó)電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解m北京：中國(guó)電力出版社，20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）m. 北京：清華大學(xué)出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)m北京：中國(guó)鐵道出版社，2003致 謝在這次課程設(shè)計(jì)的撰寫(xiě)過(guò)程中，我得到了許多人的鼓勵(lì)和幫助，在此，我表示衷心的感謝。首先，我要感謝我的指導(dǎo)老師黃同城老師，他在課程設(shè)計(jì)上給予我的很大的幫助，指導(dǎo)課程設(shè)計(jì)的具體實(shí)現(xiàn)方向。并且為我分析部分比較難懂的地方，讓我把此次課程設(shè)計(jì)做得更加完善。

15、在此期間，我對(duì)迷宮問(wèn)題有了更深刻的認(rèn)識(shí)，而且也明白了很多做課程設(shè)計(jì)需要注意的地方，讓我變得更嚴(yán)謹(jǐn)。然后，我要感謝我們第一大組組員們，在組內(nèi)討論時(shí)，他們各抒己見(jiàn)，思路發(fā)散，討論時(shí)錙銖必較，正是因?yàn)檫@份熱情，我們對(duì)這次的課程設(shè)計(jì)充滿(mǎn)了激情，方向也很明確。在匯報(bào)進(jìn)程的時(shí)候，組內(nèi)積極討論，相互競(jìng)爭(zhēng)，優(yōu)缺互補(bǔ)，讓我們的課程設(shè)計(jì)更加完美，讓我們自己在討論中知道自己的優(yōu)點(diǎn)，認(rèn)識(shí)自己的缺點(diǎn)，不斷完善自己。最后感謝我的母校邵陽(yáng)學(xué)院，謝謝母校為我們提供了這樣一個(gè)環(huán)境，讓同學(xué)們能相聚在一起，讓我們有這樣一起奮斗共同完成目標(biāo)的經(jīng)歷。附錄 具體程序代碼實(shí)現(xiàn)#include<stdio.h>#include&

16、lt;stdlib.h> #define m 6#define n 8#define maxsize 100#define max m*ntypedef struct /棧的相關(guān)類(lèi)型定義 int x,y,d; /d 下一步方向 elemtype;typedef struct elemtype datamaxsize; int top; sqstack;typedef struct int x,y; item;typedef struct /隊(duì)的相關(guān)類(lèi)型定義 int x,y; int pre; elemtype; typedef struct /隊(duì)列的類(lèi)型定義 elemtype elemm

17、axsize; 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=maxsize-1) printf("stack is fulln"); return; s->top+; s->datas-

18、>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(s

19、qqueue *q) /隊(duì)的初始化 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=maxsiz

20、e) printf("queue is fulln"); else q->elemq->rear.x=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-&

21、gt;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=0;i<m+2;i+) for(j=0;j<n+2;j+) printf("%2d",aij); printf("n"); void zprintpath(sqstack s)/輸出迷宮路徑，棧中保存的就是一

22、條迷宮 的通路 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 x,y,d,i,j; initstack(&s);/棧的初始化 temp.x=1

23、;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(d<8) 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;/if else d+;

24、 /while /while return; printf("迷宮無(wú)路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

25、q; elemtype head,e; int x,y,v,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;v<8;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("迷宮無(wú)路!n"); return;void main() int a,i,j,maze2m+2n+2; 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