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

1、課 程 設(shè) 計 報 告課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 課題名稱 迷宮問題 專 業(yè) 班 級 學(xué) 號 姓 名 指導(dǎo)教師 2012年 6月 9日課程設(shè)計任務(wù)書課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 課 題 迷宮問題 專業(yè)班級 學(xué)生姓名 學(xué) 號 指導(dǎo)老師 審 批 任務(wù)書下達日期： 2012年 6月 9日任務(wù)完成日期： 2012年 6月 16日一、設(shè)計內(nèi)容與設(shè)計要求1設(shè)計內(nèi)容：1）問題描述以一個M*N的長方陣表示迷宮，0和1分別表示迷宮中的通路和墻壁。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出米有通路的結(jié)論。2）基本要求a.實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得

2、的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一個坐標(biāo)的方向。b.編寫遞歸形式的算法，求得迷宮中所有可能的通路。3）測試數(shù)據(jù)迷宮的測試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（8,9）為出口。0010001000100010000011010111001000010000010001010111100111000101110000004）實現(xiàn)提示計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則，沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出

3、口，則設(shè)定的迷宮沒有通路。可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。2設(shè)計要求：l 課程設(shè)計報告規(guī)范1)需求分析a.程序的功能。b.輸入輸出的要求。2)概要設(shè)計a. 程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個模塊的功能。b. 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。3)詳細設(shè)計a.采用C語言定義相關(guān)的數(shù)據(jù)類型。b.寫出各模塊的類C碼算法。c.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的

4、流程圖。4)調(diào)試分析以及設(shè)計體會a.測試數(shù)據(jù)：準(zhǔn)備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯誤的輸入及輸出結(jié)果。b.程序調(diào)試中遇到的問題以及解決問題的方法。c.課程設(shè)計過程經(jīng)驗教訓(xùn)、心得體會。5)使用說明用戶使用手冊：說明如何使用你編寫的程序，詳細列出每一步的操作步驟。6)書寫格式見附帶說明。7)附錄a.參考書目b.源程序清單（帶注釋）l 考核方式指導(dǎo)老師負責(zé)驗收程序的運行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設(shè)計報告等進行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學(xué)的課程設(shè)計成績。具體考核標(biāo)準(zhǔn)包含以下幾個部分： 平時出勤 （占10%） 系統(tǒng)需

5、求分析、功能設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計及程序總體結(jié)構(gòu)合理與否（占10%） 程序能否完整、準(zhǔn)確地運行，個人能否獨立、熟練地調(diào)試程序（占40%） 設(shè)計報告（占30%）注意：不得抄襲他人的報告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴帧?獨立完成情況（占10%）。l 課程驗收要求 運行所設(shè)計的系統(tǒng)。 回答有關(guān)問題。 提交課程設(shè)計報告紙質(zhì)稿。 提交源程序、設(shè)計報告文檔電子稿。 依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。二、進度安排附：課程設(shè)計報告裝訂順序：封面、任務(wù)書、目錄、正文、評分、附件（A4大小的圖紙及程序清單）。 正文的格式:一級標(biāo)題用3號黑體,二級標(biāo)題用四號宋體加粗,正文用小四號宋體;行距為2

6、2。正文的內(nèi)容:一、課題的主要功能；二、課題的功能模塊的劃分（要求畫出模塊圖）；三、主要功能的實現(xiàn)（至少要有一個主要模塊的流程圖）；四、程序調(diào)試；五、總結(jié)；六、附件（所有程序的原代碼，要求對程序?qū)懗霰匾淖⑨專?。正文總字?shù)要求在5000字以上（不含程序原代碼）。 目錄一、 任務(wù)書2二、 基本算法7三、 需求分析7a. 程序的功能7b. 輸入輸出的要求7c. 程序算法分析8四、 概要設(shè)計8i. 設(shè)計中非遞歸程序的模塊結(jié)構(gòu)圖8ii. 程序的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)分析9iii. 試探方向的設(shè)計10iv. 達某點，以避免發(fā)生死循環(huán)11五、 詳細設(shè)計11a. 偽碼設(shè)計11b. mgpath（）流程圖12六

7、、 調(diào)試分析13七、 總結(jié)14八、 評分表16九、 附錄（源代碼清單）17一、基本算法走迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按東、東南、南、西南、西、西北、北、東北8個方向順序試探下一個位置；如果某方向可以通過，并且不曾到達，則前進一步，在新位置上繼續(xù)進行搜索；如果8個方向都走不通或曾經(jīng)到達過，則退回一步，在原來的位置上繼續(xù)試探下一位置。每前進或后退一步，都要進行判斷：若前進到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。用一個字符類型的二維數(shù)組表示迷宮，數(shù)組中每個元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點在位置（1，1）處，出口點在位置

8、（m,m）處。設(shè)計一個模擬走迷宮的算法，為其尋找一條從入口點到出口點的通路。二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的邊界；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宮的入口和出口；其余元素值用隨機函數(shù)產(chǎn)生。假設(shè)當(dāng)前所在位置是（x,y）。沿某個方向前進一步，它可能到達的位置最多有8個。如果用二維數(shù)組move記錄8個方向上行下標(biāo)增量和列下標(biāo)增量，則沿第i個方向前進一步，可能到達的新位置坐標(biāo)可利用move數(shù)組確定： x=x+movei0 y=y+movei1從迷宮的入口位置開始，沿圖示方向順序依次進行搜索。在搜索過程中，每前進一步，在所到位置處做標(biāo)記

9、“h”（表示這個位置在通路上），并將該位置的坐標(biāo)壓入棧中。每次后退的時候，先將當(dāng)前所在位置處的通路標(biāo)記“h”改成死路標(biāo)記“”（表示這個位置曾到達過但走不通，以后不要重復(fù)進入），然后將該位置的坐標(biāo)從棧頂彈出。搜索到出口位置時，數(shù)組中那些值為“h”的元素形成一條通路。二、需求分析a.程序的功能。(i) 實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，以非遞歸算法求取所有通路和最短路徑(ii)以一個遞歸算法，對任意輸入的迷宮矩陣（1代表不通，0代表通路）求出所有通路 b.輸入輸出的要求。(i) 求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一個坐標(biāo)的方向。（ii）輸

10、出迷宮示意圖c、程序算法分析1.迷宮的建立：迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述，2.迷宮的存儲：迷宮是一個矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個位置都可以用其行列號來唯一指定，但是二維數(shù)組不能動態(tài)定義其大小，我們可以考慮先定義一個較大的二維數(shù)組mazeM+2N+2,然后用它的前m行n列來存放元素，即可得到一個mn的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為39、39，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。3.迷宮路徑

11、的搜索：首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時保留搜索痕跡，在考慮進入下一個位置搜索之前，將當(dāng)前位置保存在一個棧中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。三、概要設(shè)計i）設(shè)計中非遞歸程序的模塊結(jié)構(gòu)圖圖中方框表示函數(shù)，方框中指出函數(shù)名，

12、箭頭方向表示函數(shù)間的調(diào)用關(guān)系，虛線方框表示文件的組成main（）mapath（）mgpath（）：求解迷宮問題，即輸出從（1，1）到（M，N）的全部路徑和最短路徑（包含最短路徑長度）。當(dāng)找到一條路徑時，不使用return語句退出，而是出棧一次，重新回溯走另一條路徑，并用minlen記錄最短路徑長度，Path數(shù)組記錄最短路徑。ii）程序的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)分析設(shè)迷宮為m行n列，利用mazemn來表示一個迷宮，mazeij=0或1; 其中：0表示通路，1表示不通，當(dāng)從某點向下試探時，中間點有4個方向可以試探，（見圖）而四個角點有2個方向，其它邊緣點有3個方向，為使問題簡單化我們用mazem+2n

13、+2來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個點的試探方向全部為4，不用再判斷當(dāng)前點的試探方向有幾個，同時與迷宮周圍是墻壁這一實際問題相一致。如圖3.4表示的迷宮是一個68的迷宮。入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。入口(1,1) 012345678n90111111111111011101111210010111113100000001141001101111511000100016101100010171111111111m 出口 (6,8) 圖1 用mazem+2n+2表示的迷宮迷宮的定義如下：#define m 6 /* 迷宮的實際行 */#define n

14、 8 /* 迷宮的實際列 */int maze m+2n+2 ;iii試探方向的設(shè)計 示迷宮的情況下，每個點有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：縱坐標(biāo)增量。Move數(shù)組如圖3所示。move數(shù)組定義如下：typede

15、f struct int x ; /行int y ; /列 item ; item move4 ;這樣對move的設(shè)計會很方便地求出從某點 (x，y) 按某一方向 v (0v3) 到達的新點（i，j）的坐標(biāo)：i =x + movev.x ，j = y + movev.y 。(x，y)圖2 與點(x，y)相鄰的4個點及坐標(biāo)(x，y+1)(x，y-1)(x+1，y)(x-1，y)xy00111020-13-10圖3 增量數(shù)組moveiii、棧的設(shè)計當(dāng)?shù)竭_了某點而無路可走時需返回前一點，再從前一點開始向下一個方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達的各點的坐標(biāo)，而且還要有從前一點到達本點的方向，

16、即每走一步棧中記下的內(nèi)容為(行，列，來的方向)。對于圖1所示迷宮，依次入棧為：top 3,4,0 3,3,0 3,2,1 2,2,0 2,1,1 1,1,0棧中每一組數(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)回溯，對應(yīng)的操作是出棧，沿下一個方向即方向繼續(xù)試探。棧中元素是一個由行、列、方向組成的三元組，棧元素的設(shè)計如下：typedef structint x , y , d ;/* 橫縱坐標(biāo)及方向*/datatype ;棧的定義為： SeqStack s

17、 ;iv、達某點，以避免發(fā)生死循環(huán)：一種方法是另外設(shè)置一個標(biāo)志數(shù)組markmn，它的所有元素都初始化為0，一旦到達了某一點 ( i , j )之后，使mark i j 置1，下次再試探這個位置時就不能再走了。另一種方法是當(dāng)?shù)竭_某點（i , j）后使maze i j 置 -1，以便區(qū)別未到達過的點，同樣也能起到防止走重復(fù)點的目的，此處采用后一方法，算法結(jié)束前可恢復(fù)原迷宮。四、詳細設(shè)計a.偽碼設(shè)計(1) 棧初始化;(2) 將入口點坐標(biāo)及到達該點的方向（設(shè)為-1）入棧(3) while (棧不空) 棧頂元素（x , y , d）出棧 ;求出下一個要試探的方向d+ ; while （還有剩余試探方向時

18、） if （d方向可走）則 （x , y , d）入棧 ; 求新點坐標(biāo) (i, j ) ;將新點（i , j）切換為當(dāng)前點（x , y） ; if ( (x ,)= =(,n) ) 結(jié)束 ; else 重置 d=0 ; else d+ ; 算法如下： int path(int &maze，int m, int n, int move) /m,n為 maze的一、二維長度，move為結(jié)構(gòu)體數(shù)組存放了試探的4個方向坐標(biāo) SeqStack s ; datetype temp ; int x, y, d, i, j ; temp.x=1 ; temp.y=1 ; temp.d=-1 ; Push_Se

19、qStack (s，temp) ;阿 while (! Empty_SeqStack (s ) ) Pop_SeqStack (s,temp) ;x=temp.x ; y=temp.y ; d=temp.d+1 ;while (d4) i=x+moved.x ; j=y+moved.y ;if ( mazeij= =0 ) temp=x, y, d ;Push_SeqStack ( s, temp ) ;x=i ; y=j ; mazexy= -1 ;if (x= =m&y= =n) return 1 ; /*迷宮有路*/else d=0 ; else d+ ; /*while (d4)*/

20、/*while (! Empty_SeqStack (s ) )*/ return 0 ;/*迷宮無路*/ 棧中保存的就是一條迷宮的通路。bmgpath（）流程圖開始棧不為空比較輸出最短路徑回溯無路可走輸出路徑讓該結(jié)點不可走找到下一個可走結(jié)點是否找到出口五、調(diào)試分析a、迷宮的測試數(shù)據(jù)如下：左上角（1,1）為入口，右下角（8,9）為出口。001000100010001000001101011100100001000001000101011110011100010111000000b、 程序調(diào)試截圖i) 遞歸算法程序求所有路徑，預(yù)設(shè)測試迷宮，輸出迷宮圖黑色方塊代表墻壁ii) 運行程序得出所有通路，

21、以圖的方式輸出，圓圈代表路徑（程序截圖如右）iii）輸入上表給出的測試矩陣，運行源代碼清單1，以三元組輸出所有通路，及最短路徑，程序運行截圖（如上）六、總結(jié)經(jīng)過一個星期的課程設(shè)計，過程曲折可謂一語難盡。整天都是對著電腦，不然就是翻閱資料。在此期間我失落過，也曾一度熱情高漲。點點滴滴令我回味無長。這次課程設(shè)計使我體會到只有做到細心耐心，恒心才能做好事情。這次的課程設(shè)計，加強了我們動手、思考和解決問題的能力。鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學(xué)知識的能力。培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。通過實際編譯系統(tǒng)的分析設(shè)計、編程

22、調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計方法。通過課程設(shè)計，培養(yǎng)了我嚴肅認真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。而且做課程設(shè)計同時也是對課本知識的鞏固和加強，平時看課本時，有些問題就不是很能理解，做完課程設(shè)計，那些問題就迎刃而解了。而且還可以記住很多東西。認識來源于實踐，實踐是認識的動力和最終目的，實踐是檢驗真理的唯一標(biāo)準(zhǔn)。所以這個期末測試之后的課程設(shè)計對我們的作用是非常大的。這次的課程設(shè)計使我懂得了理論與實際相結(jié)合是很非常重要的，只有理論知識是遠遠不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)，從而提高自己的實際動手能力和獨立思考的能力。

23、在整個設(shè)計過程中，構(gòu)思是很花費時間的。調(diào)試時經(jīng)常會遇到這樣那樣的錯誤，有的是因為粗心造成的語法錯誤。當(dāng)然，很多也時用錯了方法，總是實現(xiàn)不了。同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固。根據(jù)我在課程設(shè)計中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點： 1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴密。3、在做設(shè)計的時候要有信心，有耐心，切勿浮躁。4、認真的學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運用。5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。每個實驗通

24、常都要花費很久的時間才能理清一個程序的思路，而且要不斷的調(diào)試程序才能把程序調(diào)試正確，同時還要做到界面的輸出也是需要美化的。這次課程設(shè)計終于順利完成了，在設(shè)計中遇到了很多專業(yè)知識問題，最后在老師的辛勤指導(dǎo)下，也完成了課程設(shè)計。通過這次的課程設(shè)計，讓我更加了解到數(shù)據(jù)結(jié)構(gòu)的重要性。以及它對我們專業(yè)的發(fā)展發(fā)揮的作用。對我們而言，知識上的收獲很重要，但精神上的豐收更加可喜。讓我知道了學(xué)無止境的道理。我們每一個人永遠不能滿足于現(xiàn)有的成就，人生就像在爬山，一座山峰的后面還有更高的山峰在等著你。挫折是一份財富，經(jīng)歷是一份擁有。這次課程設(shè)計必將成為我人生旅途上一個非常美好的回憶！同時在做課程設(shè)計時要能夠從多方面

25、去考慮，去研究，用多種算法去實現(xiàn)要求。此次課程設(shè)計，學(xué)到了很多課內(nèi)學(xué)不到的東西，比如獨立思考解決問題，出現(xiàn)差錯的隨機應(yīng)變，這些都讓我受益非淺，今后的制作應(yīng)該能夠更輕松，自己也都能夠解決并高質(zhì)量的完成項目。評分表理學(xué)院課程設(shè)計評分表課題名稱： 迷宮問題 項 目評 價設(shè)計方案的合理性與創(chuàng)造性設(shè)計與調(diào)試結(jié)果設(shè)計說明書的質(zhì)量答辯陳述與回答問題情況課程設(shè)計周表現(xiàn)情況綜合成績 教師簽名： 日 期： 附錄A、參考書目1、數(shù)據(jù)結(jié)構(gòu)教程（第3版）李春葆 尹為民 編著 清華大學(xué)出版社出版2、數(shù)據(jù)結(jié)構(gòu)教程（第三版）上級實驗指導(dǎo)李春葆 尹為民 編著 清華大學(xué)出版社出版3、數(shù)據(jù)結(jié)構(gòu)（學(xué)習(xí)指導(dǎo)、實驗指導(dǎo)、課程設(shè)計） 陳媛

26、 編著 機械工業(yè)出版社出版B、源程序清單（帶注釋）i）非遞歸算法求迷宮源程序/* 實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫 * 一個求解迷宮的非遞歸程序。求得的通路以三元組 * （i，j，d）的形式輸出，其中：（i，j）指示迷宮中 * 的一個坐標(biāo)，d表示走到下一個坐標(biāo)的方向。 */#include #include #define M 9 /行數(shù)#define N 8/列數(shù)#define MaxSize 100/棧最多元素個數(shù)int mgM+2N+2 = /迷宮測試數(shù)據(jù)矩陣,左上角（1,1）為入口，右下角（9,8）為出口1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,

27、0,1,1,0,1,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;struct int i;int j;int di; StackMaxSize,PathMaxSize;/定義棧和存放最短路徑的數(shù)組int top=-1;/棧頂指針int count=1;/路徑數(shù)計數(shù)int minlen=MaxSi

28、ze;/最短路徑長度void mgpath()/路徑為:(1,1)-(M,N)int i,j,di,find,k;top+;/進棧Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;/初始結(jié)點進棧while (top-1)/棧不空時循環(huán)i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if (i=M & j=N)/找到了出口,輸出路徑 printf(%4d: ,count+);for (k=0;k=top;k+) /以三元組輸出路徑printf(%d,%d,%d) ,Stackk.i,Stackk.j,Stackk.

29、di);if (k+1)%5=0) printf(nt);/輸出時每5個結(jié)點換一行printf(n);if (top+1minlen)/比較找最短路徑for (k=0;k=top;k+)Pathk=Stackk;minlen=top+1;mgStacktop.iStacktop.j=0;/讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;find=0;while (di4 & find=0)/找下一個可走結(jié)點di+;switch(di)case 0:i=Stacktop.i-1;j=Stacktop.j;break;cas

30、e 1:i=Stacktop.i;j=Stacktop.j+1;break;case 2:i=Stacktop.i+1;j=Stacktop.j;break;case 3:i=Stacktop.i,j=Stacktop.j-1;break;if (mgij=0) find=1;if (find=1)/找到了下一個可走結(jié)點Stacktop.di=di;/修改原棧頂元素的di值top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;/下一個可走結(jié)點進棧mgij=-1;/避免重復(fù)走到該結(jié)點else/沒有路徑可走,則退棧mgStacktop.iStacktop.j=

31、0; /讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點top-;printf(最短路徑如下:n);printf(長度: %dn,minlen);printf(路徑: );for (k=0;kminlen;k+)switch(Pathk.di)case 0:printf(%d,%d,%s) ,Pathk.i,Pathk.j,);break;case 1:printf(%d,%d,%s) ,Pathk.i,Pathk.j,);break;case 2:printf(%d,%d,%s) ,Pathk.i,Pathk.j,);break;case 3:printf(%d,%d,%s) ,Pathk.i,Pathk.j,);break;case-1: printf(%d,%d,%s)