迷宮與棧問題

1、目錄目錄一、一、 系統(tǒng)開發(fā)的背景系統(tǒng)開發(fā)的背景.1 1二、二、 系統(tǒng)分析與設(shè)計(jì)系統(tǒng)分析與設(shè)計(jì).1 1( (一一) )系統(tǒng)功能要求系統(tǒng)功能要求.1( (二二) )系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì).1三、三、 系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).2 2( (一一) )棧的基本操作棧的基本操作.2( (二二) )迷宮算法：迷宮算法：PATHPATH(S(SEQEQS STACKTACK * *S S) ) .4( (三三) )迷宮路徑輸出算法：迷宮路徑輸出算法：PRINTPATHPRINTPATH(S(SEQEQS STACKTACK * *S S) ) .6( (四四) )主函數(shù)主函數(shù).7四、四、

2、系統(tǒng)測試系統(tǒng)測試.8 8( (一一) )測試主函數(shù)迷宮的輸入輸出測試主函數(shù)迷宮的輸入輸出.8( (二二) )測試迷宮函數(shù)和迷宮路徑輸出函數(shù)測試迷宮函數(shù)和迷宮路徑輸出函數(shù).8五、五、 總結(jié)總結(jié).9 9六、六、 附件（代碼）附件（代碼）.9 91迷宮與棧問題迷宮與棧問題一、一、 系統(tǒng)開發(fā)的系統(tǒng)開發(fā)的背景背景迷宮問題是心理學(xué)中的一個經(jīng)典問題，一直以來人們樂都此不彼的研究它。 同樣利用棧的思想也可以解決迷宮問題。二、二、 系統(tǒng)分析與設(shè)計(jì)系統(tǒng)分析與設(shè)計(jì)( (一一) )系統(tǒng)功能要求系統(tǒng)功能要求以一個mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個程序，對任意設(shè)定的迷宮，求出一條從入口到出

3、口的通路，或得出沒有通路的結(jié)論。首先實(shí)現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。( (二二) )系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)通過對系統(tǒng)功能的分析，系統(tǒng)功能如圖 1 所示。迷宮與棧問題迷宮與棧問題棧棧的的基基本本操操作作 迷迷宮宮算算法法主主 函函數(shù)數(shù)迷迷宮宮路路徑徑輸輸出出2圖 1 迷宮與棧問題系統(tǒng)功能圖通過上圖的功能分析，把整個系統(tǒng)劃分為 4 個模塊：1、棧的基本操作：該模塊主要包括棧的初始化、?？张袆e算法、入棧算法、出棧算法；主要通過函數(shù) SeqStack

4、 *Init_SeqStack()、Empty_SeqStack(SeqStack *s)、Push_SeqStack(SeqStack *s,DateType x)、pop_SeqStack(SeqStack *s,DateType *x)實(shí)現(xiàn)；2、迷宮算法：該模塊主要通過函數(shù) path(SeqStack *s)實(shí)現(xiàn)，3、迷宮路徑輸出算法：該模塊主要通過函數(shù) printpath(SeqStack *s)實(shí)現(xiàn)；4、主函數(shù)：該模塊主要是迷宮的輸入、打印，以及對以上函數(shù)的調(diào)用。三、三、 系統(tǒng)的設(shè)計(jì)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)與實(shí)現(xiàn)( (一一) )棧的基本操作棧的基本操作分析：棧的初始化算法也可理解為置空棧算法

5、：首先建立?？臻g，然后初始化棧頂指針。利用 if 來判斷是否申請到足夠大的儲存空間，然后返回空指針或?？臻g地址；?？张袆e算法：當(dāng)棧頂指針指向棧底時，棧為空；入棧算法：入棧時，首先借助 if 語句判斷棧是否滿了，棧滿時，不能入棧，返回錯誤代碼 0，相反，棧頂指針向上移動，將 x 置于新的棧頂，入棧成功返回成功代碼 1；出棧算法：出棧時，首先判斷棧是否為空，借助于 if 語句，?？詹荒艹鰲?，返回錯誤代碼 0，相反，保存棧頂元素值，棧頂指針向下移動 ，棧頂元素存入*x，返回成功代碼 1；該模塊如圖 2 所示：3 圖 2 棧的基本操作 該模塊的具體代碼如下所示：/棧的初始化算法SeqStack *In

6、it_SeqStack()SeqStack *s;s=(SeqStack *)malloc(sizeof(SeqStack);s-top=0;return s;/?？张袆e算法int Empty_SeqStack(SeqStack *s)if(s-top=0) /判斷空棧return 1;else return 0;/入棧算法int Push_SeqStack(SeqStack *s,DateType x)if(s-top=Maxsize-1) /判斷棧滿return 0;elses-top+;s-datas-top=x;return 1;/出棧算法int pop_SeqStack(SeqSta

7、ck *s,DateType *x)if(Empty_SeqStack(s)棧的基本操作棧的基本操作棧棧的的初初始始化化棧?？湛张信袆e別算算法法入入棧棧操操作作出出棧棧操操作作4return 0;else*x=s-datas-top;s-top-;return 1;( (二二) )迷宮算法：迷宮算法：path(SeqStackpath(SeqStack *s)*s)分析：從迷宮入口出發(fā)，按照一定的順序（在本程序中順序依次為右、右下、下、左下、左、左上，上、右上）對周圍的墻、路進(jìn)行判斷；若周圍的位置都為 1（即沒有通路） ，則沿原路返回前一點(diǎn)，換下一個方向繼續(xù)試探，直到所有通路都試探到，或找到一

8、條通路，或無路可走又返回到入口點(diǎn)。在求解過程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走時，能正確返回前一點(diǎn)，以便繼續(xù)從下一個方向向前試探，則需要用一個棧保存所能到達(dá)的沒一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。棧是由行、列、方向組成的三元組。迷宮求解算法思想如下：（1）棧初始化。（2）將入口坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為-1）入棧。（3）偽代碼入下： while（棧不空）棧頂元素=（x,y,d）出棧；求下一個要試探的方向 d+；while(還有剩余試探方向) if（d 方向可走） （x,y,d）入棧； 求新點(diǎn)坐標(biāo)（i,j）; 將新點(diǎn)（i,j）切換為當(dāng)先點(diǎn)（x,y）; If（(x,y)=(m,n)） 結(jié)束； e

9、lse 重置 d=0；5else d+;該模塊的具體代碼如下所示：/迷宮算法int path(SeqStack *s)DateType temp;int x,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1; /初始化入口坐標(biāo)及方向Push_SeqStack(s,temp);while(!Empty_SeqStack(s)pop_SeqStack(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) /該點(diǎn)可達(dá)temp.x=x; temp.y=y; t

10、emp.d=d; /坐標(biāo)及方向Push_SeqStack(s,temp); / 坐標(biāo)及方向入棧x=i;y=j;mazexy=-1; / 到達(dá)新點(diǎn)if(x=m & y=n)return 1; /到出口，迷宮有路，成功返回 1elsed=0; /重新初始化方向elsed+; /改變方向return 0; /迷宮無路，失敗返回 06( (三三) )迷宮路徑輸出算法：迷宮路徑輸出算法：printpath(SeqStackprintpath(SeqStack *s)*s)分析：利用 for 循環(huán)輸出棧中保存的路徑。該算法的流程圖如圖 3 所示：圖 3 迷宮路徑輸出流程圖該模塊的具體代碼如下所示：

11、void printpath(SeqStack *s)int i;for(i=1;itop;i+)printf(%d,%d,%d,s-datai.x,s-datai.y,s-datai.d);if(itop)printf(-);if(i%3=0)printf(n);printf(n);itopi=1s-datai.x,s-datai s-datai.d.y,s-datai.di+NY7( (四四) )主函數(shù)主函數(shù) 分析：迷宮的輸入輸出借助于 for 循環(huán)實(shí)現(xiàn)，為了迷宮算法查找方便，用 mazem+2m+2來表示迷宮,在四周加上一圈“哨兵”即迷宮四周的值全部為 1。標(biāo)識迷宮入口和出口即將 maz

12、e11、mazemn置為0。該模塊的具體代碼如下所示：void main()SeqStack *s;int i,j,k;printf(n);printf( 迷宮與棧問題 n);printf(n);printf(請按行輸入迷宮(%d*%d):n,m,n);printf(提示：0 表示通路，1 表示阻礙n);for(i=1;i=m;i+) for(j=1;j=n;j+) scanf(%ld,&mazeij);maze11=0; mazemn=0;for(i=0;im+2;i+)mazei0=1;mazein+1=1; for(j=0;jn+2;j+) maze0j=1; mazem+1j=

13、1; printf(n 輸入的迷宮如圖所示n); for(i=0;im+2;i+) for(j=0;jn+2;j+) printf(%2d,mazeij);8 printf(n); s=Init_SeqStack(); k=path(s); if(k=1) printf(n 輸出路徑如下：n); printpath(s); else printf(失?。n); getchar();四、四、 系統(tǒng)測試系統(tǒng)測試( (一一) )測試主函數(shù)迷宮的輸入輸出測試主函數(shù)迷宮的輸入輸出圖 4 迷宮的輸入及打印( (二二) )測試迷宮函數(shù)和迷宮路徑輸出函數(shù)測試迷宮函數(shù)和迷宮路徑輸出函數(shù)9圖 5 迷宮路徑的輸出

14、五、五、 總結(jié)總結(jié)系統(tǒng)完成了迷宮的輸入輸出及查找路徑并輸出了路徑的功能。系統(tǒng)不能輸出迷宮所有的路徑。統(tǒng)過這段時間的課程設(shè)計(jì)，我對計(jì)算機(jī)的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及 C 語言的使用都有了更深的了解。尤其是 C 語言的進(jìn)步讓我深刻的感受到任何所學(xué)的知識都需要實(shí)踐，沒有實(shí)踐就無法真正理解這些知識以及掌握它們。在設(shè)計(jì)此程序時，剛開始感到比較迷茫，然后一步步分析，試著寫出基本的算法，思路漸漸清晰，最后完成程序。當(dāng)然也遇到不少的問題，也正是因?yàn)檫@些問題引發(fā)的思考給我?guī)Я耸斋@。這次課程設(shè)計(jì)讓我更加深入了解很多方面的知識，如順序結(jié)構(gòu)的棧類型及其基本操作，數(shù)組的運(yùn)用等等。在實(shí)際的上機(jī)操作過程中，不僅是讓我們了解數(shù)

15、據(jù)結(jié)構(gòu)的理論知識，更重要的是培養(yǎng)解決實(shí)際問題的能力，所以相信通過此次課程設(shè)計(jì)可以提高我們分析設(shè)計(jì)能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實(shí)踐打下良好的基礎(chǔ)。六、六、 附件（代碼）附件（代碼）#include#include#define m 10 /迷宮的行#define n 10 /迷宮的列/順序棧的類型描述#define Maxsize 5010int mazem+2n+2;/Move 數(shù)組定義typedef structint x,y;item;item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;/棧中元素的設(shè)計(jì)typedef structint

16、x,y,d;DateType; /橫坐標(biāo)及方向typedef structDateType dataMaxsize;int top;SeqStack;SeqStack *s;/定義一個指向順序棧的指針變量/棧的初始化算法SeqStack *Init_SeqStack()SeqStack *s;s=(SeqStack *)malloc(sizeof(SeqStack);s-top=0;return s;/?？张袆e算法int Empty_SeqStack(SeqStack *s)if(s-top=0) /判斷空棧return 1;else return 0;/入棧算法int Push_SeqSta

17、ck(SeqStack *s,DateType x)if(s-top=Maxsize-1) /判斷棧滿return 0;elses-top+;s-datas-top=x;return 1;/出棧算法int pop_SeqStack(SeqStack *s,DateType *x)if(Empty_SeqStack(s)return 0;else11*x=s-datas-top;s-top-;return 1;/迷宮算法int path(SeqStack *s)DateType temp;int x,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1; /初始化入口坐標(biāo)及方向

18、Push_SeqStack(s,temp);while(!Empty_SeqStack(s)pop_SeqStack(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) /該點(diǎn)可達(dá)temp.x=x; temp.y=y; temp.d=d; /坐標(biāo)及方向Push_SeqStack(s,temp); / 坐標(biāo)及方向入棧x=i;y=j;mazexy=-1; / 到達(dá)新點(diǎn)if(x=m & y=n)return 1; /到出口，迷宮有路，成功返回 1elsed=0; /重新初始化方向elsed+; /改變方向return 0; /迷宮無路，失敗返回 012/打印迷宮路徑函數(shù)void