數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(迷宮問題)

1、<p>　　課 程 設(shè) 計 報 告</p><p>　　課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 </p><p>　　課題名稱 迷宮問題 </p><p>　　專 業(yè) 計算機科學(xué)與技術(shù) </p><p>　　一、設(shè)計內(nèi)容與設(shè)計要求&

2、lt;/p><p><b>　　1．設(shè)計內(nèi)容：</b></p><p><b>　　1）問題描述</b></p><p>　　以一個M*N的長方陣表示迷宮，0和1分別表示迷宮中的通路和墻壁。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出米有通路的結(jié)論。</p><p><b&g

3、t;　　2）基本要求</b></p><p>　　a.實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一個坐標(biāo)的方向。</p><p>　　b.編寫遞歸形式的算法，求得迷宮中所有可能的通路。</p><p><b>　　3）測試數(shù)據(jù)

4、</b></p><p>　　迷宮的測試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（8,9）為出口。</p><p><b>　　4）實現(xiàn)提示</b></p><p>　　計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則，沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條

5、通路。假如所有可能的通路都探索到而未能到達出口，則設(shè)定的迷宮沒有通路。</p><p>　　可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。</p><p><b>　　2．設(shè)計要求：</b></p><p>

6、;<b>　　課程設(shè)計報告規(guī)范</b></p><p><b>　　1)需求分析</b></p><p><b>　　a.程序的功能。</b></p><p>　　b.輸入輸出的要求。</p><p><b>　　2)概要設(shè)計</b></p>

7、<p>　　程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個模塊的功能。</p><p>　　課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。</p><p><b>　　3)詳細設(shè)計</b></p><p>　　a.采用C語言定義相關(guān)的數(shù)據(jù)類型。</p>

8、<p>　　b.寫出各模塊的類C碼算法。</p><p>　　c.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。</p><p>　　4)調(diào)試分析以及設(shè)計體會</p><p>　　a.測試數(shù)據(jù)：準(zhǔn)備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯誤的輸入及輸出結(jié)果。</p><p>　　b.程序調(diào)試中遇到的問題以及解決問題的

9、方法。</p><p>　　c.課程設(shè)計過程經(jīng)驗教訓(xùn)、心得體會。</p><p><b>　　5)使用說明</b></p><p>　　用戶使用手冊：說明如何使用你編寫的程序，詳細列出每一步的操作步驟。</p><p><b>　　6)書寫格式</b></p><p><

10、;b>　　見附帶說明。</b></p><p><b>　　7)附錄</b></p><p><b>　　a.參考書目</b></p><p>　　b.源程序清單（帶注釋）</p><p><b>　　目錄</b></p><p>　　

11、任務(wù)書………………………………………………………2</p><p>　　基本算法……………………………………………………7</p><p>　　需求分析……………………………………………………7</p><p>　　程序的功能…………………………………………………7</p><p>　　輸入輸出的要求……………………………………………7<

12、;/p><p>　　程序算法分析………………………………………………8</p><p>　　概要設(shè)計……………………………………………………8</p><p>　　設(shè)計中非遞歸程序的模塊結(jié)構(gòu)圖…………………………8</p><p>　　程序的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)分析………………………9</p><p>　　試探方向的設(shè)計…

13、…………………………………………10</p><p>　　達某點，以避免發(fā)生死循環(huán)……………………………11</p><p>　　詳細設(shè)計……………………………………………………11</p><p>　　偽碼設(shè)計……………………………………………………11</p><p>　　mgpath（）流程圖…………………………………………12<

14、/p><p>　　調(diào)試分析……………………………………………………13</p><p>　　總結(jié)…………………………………………………………14</p><p>　　八丶 附錄（源代碼清單）………………………………………17</p><p><b>　　一、基本算法</b></p><p>　　走迷

15、宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按東、東南、南、西南、西、西北、北、東北8個方向順序試探下一個位置；如果某方向可以通過，并且不曾到達，則前進一步，在新位置上繼續(xù)進行搜索；如果8個方向都走不通或曾經(jīng)到達過，則退回一步，在原來的位置上繼續(xù)試探下一位置。</p><p>　　每前進或后退一步，都要進行判斷：若前進到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。</p>

16、<p>　　用一個字符類型的二維數(shù)組表示迷宮，數(shù)組中每個元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點在位置（1，1）處，出口點在位置（m,m）處。設(shè)計一個模擬走迷宮的算法，為其尋找一條從入口點到出口點的通路。</p><p>　　二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的邊界；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宮的入口和出口；其

17、余元素值用隨機函數(shù)產(chǎn)生。</p><p>　　假設(shè)當(dāng)前所在位置是（x,y）。沿某個方向前進一步，它可能到達的位置最多有8個。</p><p>　　如果用二維數(shù)組move記錄8個方向上行下標(biāo)增量和列下標(biāo)增量，則沿第i個方向前進一步，可能到達的新位置坐標(biāo)可利用move數(shù)組確定：</p><p>　　x=x+move[i][0]</p><p>　

18、　y=y+move[i][1]</p><p>　　從迷宮的入口位置開始，沿圖示方向順序依次進行搜索。</p><p>　　在搜索過程中，每前進一步，在所到位置處做標(biāo)記“?”</p><p>　?。ū硎具@個位置在通路上），并將該位置的坐標(biāo)壓入棧中。</p><p>　　每次后退的時候，先將當(dāng)前所在位置處的通路標(biāo)記“?”改</p>

19、<p>　　成死路標(biāo)記“×”（表示這個位置曾到達過但走不通，以后</p><p>　　不要重復(fù)進入），然后將該位置的坐標(biāo)從棧頂彈出。</p><p>　　搜索到出口位置時，數(shù)組中那些值為“?”的元素形成一條</p><p><b>　　通路。</b></p><p><b>　　二、需求分

20、析</b></p><p><b>　　a.程序的功能。</b></p><p>　　(i) 實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，以非遞歸算法求取所有通路和最短路徑</p><p>　　(ii)以一個遞歸算法，對任意輸入的迷宮矩陣（1代表不通，0代表通路）求出所有通路 </p><p>　　b.輸入輸出的要求。

21、</p><p>　　(i) 求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一個坐標(biāo)的方向。</p><p>　?。╥i）輸出迷宮示意圖</p><p><b>　　c、程序算法分析</b></p><p><b>　　1.迷宮的建立：</b><

22、/p><p>　　迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述，</p><p><b>　　2.迷宮的存儲：</b></p><p>　　迷宮是一個矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個位置都可以用其行列號來唯一指定，但是二維數(shù)組不能動態(tài)定義其大小，我們可以考慮先定義一個較

23、大的二維數(shù)組maze[M+2][N+2],然后用它的前m行n列來存放元素，即可得到一個m×n的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。</p><p>　　注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為39、39，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。</p><p>　　3.迷宮路徑的搜索：</p><p&

24、gt;　　首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時保留搜索痕跡，在考慮進入下一個位置搜索之前，將當(dāng)前位置保存在一個棧中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不

25、存在從入口到出口的路徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。</p><p><b>　　三、概要設(shè)計</b></p><p>　　i）設(shè)計中非遞歸程序的模塊結(jié)構(gòu)圖</p><p>　　圖中方框表示函數(shù)，方框中指出函數(shù)名，箭頭方向表示函數(shù)間的調(diào)用關(guān)系，虛線方框表示文件的組成</p><p>　　mg

26、path（）：求解迷宮問題，即輸出從（1，1）到（M，N）的全部路徑和最短路徑（包含最短路徑長度）。當(dāng)找到一條路徑時，不使用return語句退出，而是出棧一次，重新回溯走另一條路徑，并用minlen記錄最短路徑長度，Path數(shù)組記錄最短路徑。</p><p>　　ii）程序的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)分析</p><p>　　設(shè)迷宮為m行n列，利用maze[m][n]來表示一個迷宮，maze[i

27、][j]=0或1; 其中：0表示通路，1表示不通，當(dāng)從某點向下試探時，中間點有4個方向可以試探，（見圖）而四個角點有2個方向，其它邊緣點有3個方向，為使問題簡單化我們用maze[m+2][n+2]來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個點的試探方向全部為4，不用再判斷當(dāng)前點的試探方向有幾個，同時與迷宮周圍是墻壁這一實際問題相一致。</p><p>　　如圖3.4表示的迷宮是一個6×

28、8的迷宮。入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。</p><p><b>　　入口(1,1) </b></p><p><b>　　出口 (6,8) </b></p><p>　　圖1 用maze[m+2][n+2]表示的迷宮</p><p><b>　　迷宮的定義如下：</

29、b></p><p>　　#define m 6 /* 迷宮的實際行 */</p><p>　　#define n 8 /* 迷宮的實際列 */</p><p>　　int maze [m+2][n+2] ;</p><p>　　iii．試探方向的設(shè)計</p><p>　　示迷宮的情況下

30、，每個點有4個方向去試探，如當(dāng)前點的坐標(biāo)(x , y)，與其相鄰的4個點的坐標(biāo)都可根據(jù)與該點的相鄰方位而得到，如圖2所示。因為出口在（m，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向為從正東沿順時針方向進行。為了簡化問題，方便的求出新點的坐標(biāo)，將從正東開始沿順時針進行的這4個方向（用0，1，2，3表示東、南、西、北）的坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組move [ 4 ]中，在move 數(shù)組中，每個元素有兩個域組成，x：橫坐標(biāo)增量，y：縱坐

31、標(biāo)增量。Move數(shù)組如圖3所示。</p><p>　　move數(shù)組定義如下：</p><p>　　typedef struct {</p><p>　　int x ; //行</p><p>　　int y ; //列</p><p>　　} item ; </p><p>　　it

32、em move[4] ;</p><p>　　這樣對move的設(shè)計會很方便地求出從某點 (x，y) 按某一方向 v (0≤v≤3) 到達的新點（i，j）的坐標(biāo)：i =x + move[v].x ，j = y + move[v].y 。</p><p><b>　　iii、棧的設(shè)計</b></p><p>　　當(dāng)?shù)竭_了某點而無路可走時需返回前一點

33、，再從前一點開始向下一個方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達的各點的坐標(biāo)，而且還要有從前一點到達本點的方向，即每走一步棧中記下的內(nèi)容為(行，列，來的方向)。對于圖1所示迷宮，依次入棧為：</p><p>　　棧中每一組數(shù)據(jù)是所到達的每點的坐標(biāo)及從該點沿哪個方向向下走的，對于圖3迷宮，走的路線為：(1,1)0(2,1)1(2,2)0(3,2)1(3,3)0(3,4)0（下腳標(biāo)表示方向），當(dāng)無路可走，則應(yīng)回溯

34、，對應(yīng)的操作是出棧，沿下一個方向即方向繼續(xù)試探。</p><p>　　棧中元素是一個由行、列、方向組成的三元組，棧元素的設(shè)計如下：</p><p>　　typedef struct{</p><p>　　int x , y , d ;/* 橫縱坐標(biāo)及方向*/</p><p>　　}datatype ;</p><p>

35、　　棧的定義為： SeqStack s ;</p><p>　　iv、達某點，以避免發(fā)生死循環(huán)：</p><p>　　一種方法是另外設(shè)置一個標(biāo)志數(shù)組mark[m][n]，它的所有元素都初始化為0，一旦到達了某一點 ( i , j )之后，使mark[ i ][ j ] 置1，下次再試探這個位置時就不能再走了。另一種方法是當(dāng)?shù)竭_某點（i , j）后使maze[ i ][ j ] 置 -1，

36、以便區(qū)別未到達過的點，同樣也能起到防止走重復(fù)點的目的，此處采用后一方法，算法結(jié)束前可恢復(fù)原迷宮。</p><p><b>　　四、詳細設(shè)計</b></p><p><b>　　a.偽碼設(shè)計</b></p><p><b>　　棧初始化;</b></p><p>　　將入口點坐標(biāo)

37、及到達該點的方向（設(shè)為-1）入棧</p><p>　　while (棧不空)</p><p>　　{ 棧頂元素＝＞（x , y , d）</p><p><b>　　出棧 ;</b></p><p>　　求出下一個要試探的方向d++ ;</p><p>　　while （還有剩余試探方向時）&l

38、t;/p><p>　　{ if （d方向可走）</p><p>　　則 { （x , y , d）入棧 ;</p><p>　　求新點坐標(biāo) (i, j ) ;</p><p>　　將新點（i , j）切換為當(dāng)前點（x , y） ;</p><p>　　if ( (x ,ｙ)= =(ｍ,n) ) 結(jié)束 ;</p

39、><p>　　else 重置 d=0 ;</p><p><b>　　}</b></p><p>　　else d++ ;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b&

40、gt;　　算法如下：</b></p><p>　　int path(int &maze，int m, int n, int move)</p><p>　　//m,n為 maze的一、二維長度，move為結(jié)構(gòu)體數(shù)組存放了試探的4個方向坐標(biāo)</p><p>　　{ SeqStack s ;</p><p>　　datet

41、ype temp ;</p><p>　　int x, y, d, i, j ; </p><p>　　temp.x=1 ; temp.y=1 ; temp.d=-1 ; </p><p>　　Push_SeqStack (s，temp) ;阿</p><p>　　while (! Empty_SeqStack (s ) ) {<

42、;/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>　　i=x+move[d].x ; j=y+move[d].y ;</p><p>　

43、　if ( maze[i][j]= =0 ) {</p><p>　　temp={x, y, d} ;</p><p>　　Push_SeqStack ( s, temp ) ;</p><p>　　x=i ; y=j ; maze[x][y]= -1 ;</p><p>　　if (x= =m&&y= =n) re

44、turn 1 ; /*迷宮有路*/</p><p>　　else d=0 ;</p><p><b>　　}</b></p><p>　　else d++ ;</p><p>　　} /*while (d<4)*/</p><p>　　} /*while (! Empty_SeqStac

45、k (s ) )*/</p><p>　　return 0 ;/*迷宮無路*/</p><p><b>　　} </b></p><p>　　棧中保存的就是一條迷宮的通路。</p><p>　　b．mgpath（）流程圖</p><p><b>　　五、調(diào)試分析</b>&l

46、t;/p><p>　　a、迷宮的測試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（8,9）為出口。</p><p><b>　　程序調(diào)試截圖</b></p><p>　　遞歸算法程序求所有路徑，</p><p>　　預(yù)設(shè)測試迷宮，輸出迷</p><p>　　宮圖黑色方塊代表墻壁</p>&l

47、t;p>　　運行程序得出所有通路，</p><p>　　以圖的方式輸出，圓圈代</p><p>　　表路徑（程序截圖如右）</p><p>　　iii）輸入上表給出的測試矩陣，運行源代碼清單1，以三元組輸出所有通路，及最短路徑，程序運行截圖（如上）</p><p><b>　　六、總結(jié)</b></p>

48、<p>　　經(jīng)過一個星期的課程設(shè)計，過程曲折可謂一語難盡。整天都是對著電腦，不然就是翻閱資料。在此期間我失落過，也曾一度熱情高漲。點點滴滴令我回味無長。這次課程設(shè)計使我體會到只有做到細心耐心，恒心才能做好事情。</p><p>　　這次的課程設(shè)計，加強了我們動手、思考和解決問題的能力。鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學(xué)知識的能力。培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立

49、思考，深入研究，分析問題、解決問題的能力。通過實際編譯系統(tǒng)的分析設(shè)計、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計方法。通過課程設(shè)計，培養(yǎng)了我嚴(yán)肅認真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。而且做課程設(shè)計同時也是對課本知識的鞏固和加強，平時看課本時，有些問題就不是很能理解，做完課程設(shè)計，那些問題就迎刃而解了。而且還可以記住很多東西。認識來源于實踐，實踐是認識的動力和最終目的，實踐是檢驗真理的唯一標(biāo)準(zhǔn)。所以這個期末測試之后的

50、課程設(shè)計對我們的作用是非常大的。</p><p>　　這次的課程設(shè)計使我懂得了理論與實際相結(jié)合是很非常重要的，只有理論知識是遠遠不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨立思考的能力。在整個設(shè)計過程中，構(gòu)思是很花費時間的。調(diào)試時經(jīng)常會遇到這樣那樣的錯誤，有的是因為粗心造成的語法錯誤。當(dāng)然，很多也時用錯了方法，總是實現(xiàn)不了。同時在設(shè)計的過程中發(fā)

51、現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固。</p><p>　　根據(jù)我在課程設(shè)計中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點：</p><p>　　1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。</p><p>　　2、寫程序的過程中要考慮周到，嚴(yán)密。</p><p>　　3、在做設(shè)計的時候要有信心，有耐心，切勿

52、浮躁。</p><p>　　4、認真的學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運用。</p><p>　　5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。</p><p>　　每個實驗通常都要花費很久的時間才能理清一個程序的思路，而且要不斷的調(diào)試程序才能把程序調(diào)試正確，同時還要做到界面的輸出也是需要美化的

53、。這次課程設(shè)計終于順利完成了，在設(shè)計中遇到了很多專業(yè)知識問題，最后在老師的辛勤指導(dǎo)下，也完成了課程設(shè)計。</p><p>　　通過這次的課程設(shè)計，讓我更加了解到數(shù)據(jù)結(jié)構(gòu)的重要性。以及它對我們專業(yè)的發(fā)展發(fā)揮的作用。對我們而言，知識上的收獲很重要，但精神上的豐收更加可喜。讓我知道了學(xué)無止境的道理。我們每一個人永遠不能滿足于現(xiàn)有的成就，人生就像在爬山，一座山峰的后面還有更高的山峰在等著你。挫折是一份財富，經(jīng)歷是一份擁有

54、。這次課程設(shè)計必將成為我人生旅途上一個非常美好的回憶！同時在做課程設(shè)計時要能夠從多方面去考慮，去研究，用多種算法去實現(xiàn)要求。此次課程設(shè)計，學(xué)到了很多課內(nèi)學(xué)不到的東西，比如獨立思考解決問題，出現(xiàn)差錯的隨機應(yīng)變，這些都讓我受益非淺，今后的制作應(yīng)該能夠更輕松，自己也都能夠解決并高質(zhì)量的完成項目。</p><p><b>　　附錄</b></p><p><b>　

55、　A、參考書目</b></p><p>　　1、《數(shù)據(jù)結(jié)構(gòu)教程（第3版）》李春葆 尹為民 編著 清華大學(xué)出版社出版</p><p>　　2、《數(shù)據(jù)結(jié)構(gòu)教程（第三版）上級實驗指導(dǎo)》李春葆 尹為民 編著 清華大學(xué)出版社出版</p><p>　　3、《數(shù)據(jù)結(jié)構(gòu)（學(xué)習(xí)指導(dǎo)、實驗指導(dǎo)、課程設(shè)計）》 陳媛 編著 機械工業(yè)出版社出版</p><

56、;p>　　B、源程序清單（帶注釋）</p><p>　　i）非遞歸算法求迷宮源程序</p><p>　　/* 實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫</p><p>　　* 一個求解迷宮的非遞歸程序。求得的通路以三元組</p><p>　　* （i，j，d）的形式輸出，其中：（i，j）指示迷宮中</p><p

57、>　　* 的一個坐標(biāo)，d表示走到下一個坐標(biāo)的方向。</p><p><b>　　*/</b></p><p>　　#include <stdio.h></p><p>　　#include <string></p><p>　　#define M 9 //行數(shù)</p&g

58、t;<p>　　#define N 8//列數(shù)</p><p>　　#define MaxSize 100//棧最多元素個數(shù)</p><p>　　int mg[M+2][N+2] = { //迷宮測試數(shù)據(jù)矩陣,左上角（1,1）為入口，右下角（9,8）為出口</p><p>　　{1,1,1,1,1,1,1,1,1,1},&

59、lt;/p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,1,1,0,0,0,1,0,1},</p><p>　　{1,0,0,0,0,1,1,0,1,1},</p><p>　　{1,0,1,1,1,0,0,1,0,1},</p><p>　　{1,0,0,0,1,0,0,0,0

60、,1},</p><p>　　{1,0,1,0,0,0,1,0,1,1},</p><p>　　{1,0,1,1,1,1,0,0,1,1},</p><p>　　{1,1,1,0,0,0,1,0,1,1},</p><p>　　{1,1,1,0,0,0,0,0,0,1},</p><p>　　{1,1,1,1,1,1,

61、1,1,1,1}</p><p><b>　　};</b></p><p><b>　　struct </b></p><p><b>　　{</b></p><p>　　int i;int j;int di;</p><p>　　} Stack[Max

62、Size],Path[MaxSize];//定義棧和存放最短路徑的數(shù)組</p><p>　　int top=-1;//棧頂指針</p><p>　　int count=1;//路徑數(shù)計數(shù)</p><p>　　int minlen=MaxSize;//最短路徑長度</p><p>　　void mgpat

63、h()//路徑為:(1,1)->(M,N)</p><p><b>　　{</b></p><p>　　int i,j,di,find,k;</p><p>　　top++;//進棧</p><p>　　Stack[top].i=1;</p><p>　　Stack

64、[top].j=1;</p><p>　　Stack[top].di=-1;mg[1][1]=-1;//初始結(jié)點進棧</p><p>　　while (top>-1)//棧不空時循環(huán)</p><p><b>　　{</b></p><p>　　i=Stack[top].i;j=Stack[top].j;

65、di=Stack[top].di;</p><p>　　if (i==M && j==N)//找到了出口,輸出路徑</p><p><b>　　{ </b></p><p>　　printf("%4d: ",count++);</p><p>　　for (k=0;k<

66、=top;k++)</p><p>　　{ //以三元組輸出路徑</p><p>　　printf("(%d,%d,%d) ",Stack[k].i,Stack[k].j,Stack[k].di);</p><p>　　if ((k+1)%5==0) printf("\n\t"

67、;);//輸出時每5個結(jié)點換一行</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　if (top+1<minlen)//比較找最短路徑</p><p><b>　　{</b></p>

68、<p>　　for (k=0;k<=top;k++)</p><p>　　Path[k]=Stack[k];</p><p>　　minlen=top+1;</p><p><b>　　}</b></p><p>　　mg[Stack[top].i][Stack[top].j]=0;//讓該位置變?yōu)槠?/p>

69、他路徑可走結(jié)點</p><p><b>　　top--; </b></p><p>　　i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;</p><p><b>　　}</b></p><p><b>　　find=0;</b>&l

70、t;/p><p>　　while (di<4 && find==0)//找下一個可走結(jié)點</p><p><b>　　{di++;</b></p><p>　　switch(di)</p><p><b>　　{</b></p><p>　　case

71、0:i=Stack[top].i-1;j=Stack[top].j;break;</p><p>　　case 1:i=Stack[top].i;j=Stack[top].j+1;break;</p><p>　　case 2:i=Stack[top].i+1;j=Stack[top].j;break;</p><p>　　case 3:i=Stack[top].i

72、,j=Stack[top].j-1;break;</p><p><b>　　}</b></p><p>　　if (mg[i][j]==0) find=1;</p><p><b>　　}</b></p><p>　　if (find==1)//找到了下一個可走結(jié)點</p>

73、<p>　　{Stack[top].di=di;//修改原棧頂元素的di值</p><p>　　top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;//下一個可走結(jié)點進棧</p><p>　　mg[i][j]=-1;//避免重復(fù)走到該結(jié)點</p><p><b>　　}</b

74、></p><p>　　else//沒有路徑可走,則退棧</p><p><b>　　{</b></p><p>　　mg[Stack[top].i][Stack[top].j]=0; //讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點</p><p><b>　　top--;</b><

75、/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("最短路徑如下:\n");</p><p>　　printf("長度: %d\n",minlen);</p><p>　　p

76、rintf("路徑: ");</p><p>　　for (k=0;k<minlen;k++)</p><p><b>　　{</b></p><p>　　switch(Path[k].di)</p><p><b>　　{</b></p><p&g

77、t;　　case 0:printf("(%d,%d,%s) ",Path[k].i,Path[k].j,"↑");break;</p><p>　　case 1:printf("(%d,%d,%s) ",Path[k].i,Path[k].j,"→");break;</p><p>　　case 2

78、:printf("(%d,%d,%s) ",Path[k].i,Path[k].j,"↓");break;</p><p>　　case 3:printf("(%d,%d,%s) ",Path[k].i,Path[k].j,"←");break;</p><p>　　case-1: printf(&

79、quot;(%d,%d,%s) ",Path[k].i,Path[k].j,"終點");break;</p><p><b>　　}</b></p><p>　　if ((k+1)%5==0) printf("\n\t"); //輸出時每5個結(jié)點換一行</p><p><b>　

80、　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　printf("迷宮所有路徑

81、如下:\n");</p><p>　　printf("三元組(i,j,di),(i,j)表示迷宮中的一個坐標(biāo),di:0↑;1→;2↓;3←;\n");</p><p><b>　　mgpath();</b></p><p><b>　　}</b></p><p>　　i

82、i）以遞歸形式算法求迷宮所有通路源代碼如下</p><p>　　//以遞歸形式求迷宮的所有通路</p><p>　　#include<stdio.h></p><p>　　int flag=0; //flag用來標(biāo)記是否路徑全部走完</p><p>　　int a[1

83、2][12]={</p><p>　　{1,1,1,1,1,1,1,1,1,1},</p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,1,1,0,0,0,1,0,1},</p><p>　　{1,0,0,0,0,1,1,0,1,1},</p><p>　　{1,0,1,1,

84、1,0,0,1,0,1},</p><p>　　{1,0,0,0,1,0,0,0,0,1},</p><p>　　{1,0,1,0,0,0,1,0,1,1},</p><p>　　{1,0,1,1,1,1,0,0,1,1},</p><p>　　{1,1,1,0,0,0,1,0,1,1},</p><p>　　{1,1

85、,1,0,0,0,0,0,0,1},</p><p>　　{1,1,1,1,1,1,1,1,1,1}</p><p><b>　　};</b></p><p>　　int go(int x,int y)</p><p><b>　　{</b></p><p>　　a[x][y

86、]=2;</p><p>　　if((x==9&&y==8)) //迷宮出口設(shè)置為9,8</p><p><b>　　flag=1;</b></p><p>　　if(flag!=1&&a[x-1][y]==0) //判斷向上是否有路<

87、;/p><p>　　go(x-1,y); //這個go()糾結(jié)了好久，多了個return怎么都不行了</p><p>　　if(flag!=1&&a[x][y+1]==0) //判斷向右是否有路</p><p>　　go(x,y+1);</p><p&g

88、t;　　if(flag!=1&&a[x+1][y]==0) //判斷向下是否有路</p><p>　　go(x+1,y);</p><p>　　if(flag!=1&&a[x][y-1]==0) //判斷向左是否有路</p><p>　　go(x,y-1);</p>

89、;<p>　　if(flag!=1)</p><p>　　a[x][y]=0;</p><p>　　return flag;</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p&

90、gt;<p>　　int i,j,k,l,q;</p><p>　　for(i=0;i<11;i++) //輸出迷宮</p><p><b>　　{</b></p><p>　　for(j=0;j<12;j++)</p><p><b>

91、　　{</b></p><p>　　if(a[i][j]==0)</p><p>　　printf(" ");</p><p>　　if(a[i][j]==1)</p><p>　　printf("■");</p><p><b>　　}</b>

92、;</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　if(go(1,1)==0) //設(shè)置了起始點為1,1</p&

93、gt;<p>　　printf("沒有路徑！\n");</p><p><b>　　else</b></p><p>　　for(k=0;k<12;k++) //輸出迷宮</p><p><b>　　{</b></p>&

94、lt;p>　　for(l=0;l<12;l++)</p><p><b>　　{</b></p><p>　　if(a[k][l]==0)</p><p>　　printf(" ");</p><p>　　if(a[k][l]==1)</p><p>　　prin

95、tf("■");</p><p>　　if(a[k][l]==2)</p><p>　　printf("●");</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>