C語言課件 第21 22章

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

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

3、1.2.2 問題實現(xiàn) 本小節(jié)就來通過編程求解迷宮問題，實現(xiàn)的代碼如下。 1. 采用結(jié)構(gòu)體保存過程數(shù)據(jù) 通過定義兩個結(jié)構(gòu)體類型，分別記錄棧中的走過的坐標(biāo)及走過的方向，采用結(jié)構(gòu)體實現(xiàn)棧的存儲。那么，根據(jù)這個思路，代碼如下（代碼21-1.txt）。nnn21.2.2 問題實現(xiàn) 2. 輸出結(jié)果 將結(jié)果輸出至屏幕，以循環(huán)打印的方式，調(diào)用標(biāo)準(zhǔn)輸入輸出函數(shù)printf,將結(jié)果回顯。代碼如下（代碼21-2.txt）。21.2.2 問題實現(xiàn)01 /*輸出路徑*/02 void outputpath(pseqstack st) 03 04 datatype element; 05 printf(nn出迷宮的路徑是

4、:n); 06 while(!isemptystack_seq(st) 07 08 element = top_seq(st); 09 pop_seq(st); 10 printf(n路過的節(jié)點坐標(biāo)是: 第%d行 第%d列, element.x, element.y);/* 打印路徑上的每一點*/11 12 21.2.2 問題實現(xiàn) 3. 求解經(jīng)過的坐標(biāo)點及方向 從入口點開始，依次試探四個方向，只要某個方向沒有障礙，則繼續(xù)這個方向，并將這個方向不是障礙物的點做為下一個當(dāng)前點，循環(huán)直到到達(dá)入口點。代碼如下（代碼21-3.txt）21.2.3 程序運行 單擊【調(diào)試】工具欄中的按鈕，即可輸出以下運行結(jié)果。21.3 開發(fā)過程常見問題及解決 開發(fā)過程常見問題及解決辦法如下，僅供參考。 在程序中，如何表示一個坐標(biāo)點呢？方法很簡單：只需要用一對變量即可保存。即：一個變量保存橫坐標(biāo)，另外一個變量保存縱坐