c語言從入門到精通——第21章.ppt

《c語言從入門到精通——第21章.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第21章迷宮求解問題描述問題分析及實現(xiàn)開發(fā)過程常見問題及解決第21章迷宮求解問題描述問題分析及實現(xiàn)開發(fā)過程常見問題及解決第21章迷宮求解問題描述問題分析及實現(xiàn)開發(fā)過程常見問題及解決第21章迷宮求解問題描述問題分析及實現(xiàn)開發(fā)過程常見問題及解決迷宮求解C語言的功能是強大的，可以實現(xiàn)很多有意義的問題的求解。比如算法領(lǐng)域的經(jīng)典問題——迷宮求解。在一個M×N的迷宮中，給定一個入口，一個出口，如何從入口走到出口？本章就實現(xiàn)了這一算法。21.1問題描述以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。對任意設(shè)定的迷宮，

2、求出一條從入口到出口的通路并輸出所經(jīng)過的坐標點，或得出沒有通路的結(jié)論。21.2問題分析及實現(xiàn)21.2.1問題分析21.2.2問題實現(xiàn)21.2.3程序運行21.2問題分析及實現(xiàn)由問題描述可知，我們要實現(xiàn)的是打印從坐標A，走到坐標B，要繞過路障走一條路徑出來。簡單舉例：從左向右走動，中間有障礙物，此時，需要向上再向右，或向下再向右，只有繞過左與右之間的障礙物，才可以順利從左走至右，以下將仔細地分析問題并實現(xiàn)算法。21.2.1問題分析我們的將要開發(fā)的程序，就是設(shè)置一個迷宮（m×n）,并設(shè)置入口點，出口點，從出口點走向入口點，

3、將途經(jīng)的坐標記錄到“棧”底，在找到路徑時，將彈出棧頂元素，此時，就是所有途經(jīng)的坐標點。21.2.2問題實現(xiàn)本小節(jié)就來通過編程求解迷宮問題，實現(xiàn)的代碼如下。1.采用結(jié)構(gòu)體保存過程數(shù)據(jù)通過定義兩個結(jié)構(gòu)體類型，分別記錄棧中的走過的坐標及走過的方向，采用結(jié)構(gòu)體實現(xiàn)棧的存儲。那么，根據(jù)這個思路，代碼如下（代碼21-1.txt）。21.2.2問題實現(xiàn)2.輸出結(jié)果將結(jié)果輸出至屏幕，以循環(huán)打印的方式，調(diào)用標準輸入輸出函數(shù)printf,將結(jié)果回顯。代碼如下（代碼21-2.txt）。21.2.2問題實現(xiàn)01/*輸出路徑*/02voidOu

4、tputPath(PSeqStackst)03{04DataTypeelement;05printf("出迷宮的路徑是:");06while(!isEmptyStack_seq(st))07{08element=Top_seq(st);09Pop_seq(st);10printf("路過的節(jié)點坐標是:第%d行第%d列",element.x,element.y);/*打印路徑上的每一點*/11}12}21.2.2問題實現(xiàn)3.求解經(jīng)過的坐標點及方向從入口點開始，依次試探四個方向，只要某個方向沒有障礙，則繼續(xù)

5、這個方向，并將這個方向不是障礙物的點做為下一個當前點，循環(huán)直到到達入口點。代碼如下（代碼21-3.txt）21.2.3程序運行單擊【調(diào)試】工具欄中的按鈕，即可輸出以下運行結(jié)果。21.3開發(fā)過程常見問題及解決開發(fā)過程常見問題及解決辦法如下，僅供參考。⑴在程序中，如何表示一個坐標點呢？方法很簡單：只需要用一對變量即可保存。即：一個變量保存橫坐標，另外一個變量保存縱坐標。⑵此程序的另一難點就是，方向如何表示？我們知道，水平方向有兩個（左右），垂直方向也有兩個（上下），所以方向就用8個變量可以表示出來。