案例十九老鼠鉆迷宮

1、目錄目錄退出退出目錄目錄第1頁 共36頁案例十九 老鼠鉆迷宮本案例知識要點(diǎn)二維數(shù)組的使用堆棧的使用鏈表的使用類的設(shè)計(jì)和使用目錄目錄退出退出目錄目錄第2頁 共36頁一、案例需求案例描述有一個(gè)迷宮，只有一個(gè)入口和一個(gè)出口，有一只小老鼠想從迷宮的入口穿越迷宮走到出口。要求編程實(shí)現(xiàn)迷宮以及老鼠穿越迷宮的動態(tài)過程。案例效果圖案例效果如圖所示。目錄目錄退出退出目錄目錄第3頁 共36頁老鼠鉆迷宮案例效果圖 目錄目錄退出退出目錄目錄第4頁 共36頁功能說明迷宮使用隨機(jī)函數(shù)生成。在屏幕上用了18行70列來繪制迷宮，分別用“”表示當(dāng)前老鼠所在位置、“=”表示走過的無用的路、“+”表示走過的有用的路、“ ”（空格）

2、表示路、“*”表示墻；以第2行第1列為老鼠初始位置，以第17行第70列為老鼠出口，如老鼠最終能從第2行第1列走到第17行第70列，則表示老鼠鉆迷宮成功。提供不同的鉆迷宮速度：1表示快速；2表示慢速。程序結(jié)束后顯示鉆迷宮結(jié)果：顯示成功或失敗提示，如果成功則顯示走過的步數(shù)和有用步數(shù)。 目錄目錄退出退出目錄目錄第5頁 共36頁二、案例分析首先分析如何模擬一個(gè)迷宮，即采用何種數(shù)據(jù)結(jié)構(gòu)來存儲和表示迷宮。可以用一個(gè)二維數(shù)組來模擬迷宮，在數(shù)組中用不同的字符來表示“通道”和“墻”。通過將這個(gè)數(shù)組動態(tài)地顯示在屏幕上，可以看到由“通道”和“墻”組成的迷宮，以及在迷宮中奔跑的“小老鼠”。采用隨機(jī)函數(shù)的方法生成這個(gè)二

3、維數(shù)組，即隨機(jī)生成“墻”和“通道”。然后解決鉆迷宮的算法，先從老鼠所在的位置開始探索。假設(shè)開始是在A點(diǎn)位置，從A點(diǎn)“上”、“下”、“左”、“右”4個(gè)方向可能的通道中隨機(jī)選擇一個(gè)開始前進(jìn)一步到B點(diǎn)，如果在B點(diǎn)的4個(gè)方向上，除了從A點(diǎn)過來的這個(gè)方向之外的其他3個(gè)方向還有通道，那么就從B點(diǎn)開始重新探索，如果B點(diǎn)是個(gè)死胡同，則后退到A點(diǎn)，并將A到B的這個(gè)方向標(biāo)記為“不通”。然后重新選擇A點(diǎn)的其他的方向。走到新的點(diǎn)后，再重新開始這個(gè)判斷過程。也就是需要將小老鼠走過的每一步都記載下來，遇到死胡同的時(shí)候，就要后退一步，退到剛剛走過的位置選擇其他的方向再次開始，直到小老鼠走到了出口。目錄目錄退出退出目錄目錄第

4、6頁 共36頁“存儲走過的點(diǎn)退到最近走過的點(diǎn)”是一個(gè)典型的堆棧結(jié)構(gòu)，即把小老鼠走過的節(jié)點(diǎn)按照走過的順序壓入堆棧。若遇到死胡同，則最近走過的點(diǎn)就在棧頂，可以直接出棧。一般來說，對堆棧的存儲有兩種方式，即數(shù)組和鏈表，數(shù)組方式一般是在能夠預(yù)先知道堆棧深度的情況下采用，以便定義數(shù)組。而鏈表在內(nèi)存的占用方法靈活高效，本案例適合采用鏈表的方式來存儲堆棧。目錄目錄退出退出目錄目錄第7頁 共36頁三、案例設(shè)計(jì)類的設(shè)計(jì)基于上述分析，本案例需要自定義一些全局常量，定義一個(gè)結(jié)構(gòu)體SNode，同時(shí)需要設(shè)計(jì)一個(gè)類Stack。類Stack用來處理入棧（將老鼠的成功步壓棧）、出棧（老鼠走入死胡同，彈出棧頂步，從老鼠的上一個(gè)

5、位置開始繼續(xù)向后探索）、判?？盏炔僮?。目錄目錄退出退出目錄目錄第8頁 共36頁目錄目錄退出退出目錄目錄第9頁 共36頁目錄目錄退出退出目錄目錄第10頁 共36頁（3）Stack類的設(shè)計(jì)結(jié)構(gòu)體SNode Stack類的結(jié)構(gòu) 目錄目錄退出退出目錄目錄第11頁 共36頁 數(shù)據(jù)成員 int totallength; 用來記載棧操作次數(shù)。 int length; 用來記載棧深度。 SNode *top; 設(shè)置棧頂指針。目錄目錄退出退出目錄目錄第12頁 共36頁 函數(shù)成員 Stack(); 構(gòu)造函數(shù)，用來進(jìn)行初始化工作。棧頂指針置空，棧深度 和棧操作次數(shù)清零。 int Pop(); 反悔一步則進(jìn)行出棧操作

6、，返回棧頂元素。 int Push(int e); 如果是有效步則進(jìn)行入棧操作，將元素e壓棧。e代表老鼠 本步走的方向，有上、下、左、右4個(gè)方向。 int IsEmpty(); 判斷棧是否為空，棧為空則返回OK，否則返回ERROR。目錄目錄退出退出目錄目錄第13頁 共36頁 2主程序設(shè)計(jì) （1）全局變量 char arr1870; 定義存儲迷宮用的字符型二維數(shù)組。 （2）函數(shù)設(shè)計(jì) void InitMaze() 迷宮初始化函數(shù)，該函數(shù)用于設(shè)置1870的二維數(shù)組arr的每一個(gè)元素的值。通過給某行某列的元素賦予字符“*”表示迷宮的墻，賦予空格字符“ ”表示迷宮的通道。其中 18行70列的迷宮圖中第

7、一行、最后一行、第一列（除外第一列第二行的位置以外）、最后一列（除第70列第17行的位置以外）規(guī)定為墻，第2行第1列規(guī)定為迷宮入口，第17行第80列規(guī)定為迷宮出口。為了減少死通道過多的缺陷，第2行第2列第2行第4列規(guī)定為通道，第17行第67列第17行第69列規(guī)定為迷宮通道。目錄目錄退出退出目錄目錄第14頁 共36頁void ShowMaze() 利用迷宮初始化函數(shù)InitMaze()中設(shè)置的二維數(shù)組arr的值來繪制18行70列的迷宮圖。其中：“*”表示墻；“”表示老鼠；“ ”（空格）表示路；“+”表示有用的路；“=”表示無用的路。目錄目錄退出退出目錄目錄第15頁 共36頁 （3）主函數(shù)設(shè)計(jì) v

8、oid main() 在主函數(shù)中定義了一個(gè)用于存儲老鼠走過的路線的棧s。首先初始化迷宮，顯示迷宮圖及老鼠初始位置，接下來讓用戶選擇老鼠鉆迷宮速度，其中提供了慢速、快速兩種速度。隨后老鼠開始在4個(gè)方向上試探，如果某個(gè)方向有通道則將方向值壓入棧s，剛走過的方向用“+”標(biāo)記，并在新位置顯示老鼠。若4個(gè)方向均無通道，則標(biāo)記通道為“=”（表示此路不通），同時(shí)作出棧處理。出棧后根據(jù)棧中記錄的方向值，把老鼠退回一步，此時(shí)開始試探老鼠的下一個(gè)可用的位置。如無可用位置，則繼續(xù)退回上一步，直至老鼠走到出口（表示鉆迷宮成功），或老鼠返回入口（表示迷宮無通道）為止。程序流程如圖所示。目錄目錄退出退出目錄目錄第16頁

9、共36頁主程序流程圖目錄目錄退出退出目錄目錄第17頁 共36頁四、案例實(shí)現(xiàn)目錄目錄退出退出目錄目錄第18頁 共36頁目錄目錄退出退出目錄目錄第19頁 共36頁目錄目錄退出退出目錄目錄第20頁 共36頁目錄目錄退出退出目錄目錄第21頁 共36頁目錄目錄退出退出目錄目錄第22頁 共36頁目錄目錄退出退出目錄目錄第23頁 共36頁目錄目錄退出退出目錄目錄第24頁 共36頁目錄目錄退出退出目錄目錄第25頁 共36頁目錄目錄退出退出目錄目錄第26頁 共36頁目錄目錄退出退出目錄目錄第27頁 共36頁目錄目錄退出退出目錄目錄第28頁 共36頁目錄目錄退出退出目錄目錄第29頁 共36頁目錄目錄退出退出目錄目

10、錄第30頁 共36頁目錄目錄退出退出目錄目錄第31頁 共36頁目錄目錄退出退出目錄目錄第32頁 共36頁目錄目錄退出退出目錄目錄第33頁 共36頁目錄目錄退出退出目錄目錄第34頁 共36頁目錄目錄退出退出目錄目錄第35頁 共36頁五、案例總結(jié)與提高案例總結(jié)本案例是一個(gè)用堆棧實(shí)現(xiàn)的典型案例。堆棧是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，在很多問題的求解過程中都要用到它，讀者應(yīng)熟練掌握。本案例的難點(diǎn)體現(xiàn)在老鼠的智能化上，即老鼠如何走、如何退。分析案例代碼可以看出老鼠智能化的關(guān)鍵是它試探的每一步都被記錄在堆棧中，同時(shí)棋盤的狀態(tài)被記錄在二維數(shù)組中，可以看出是記錄在案的數(shù)據(jù)“武裝”了老鼠的大腦。因此在編寫類似的人工智能程序時(shí)，讀者要考慮的關(guān)鍵問題除了算法以外，還要重點(diǎn)考慮采用何種數(shù)據(jù)結(jié)構(gòu)。另外，在實(shí)際運(yùn)行程序時(shí)由于運(yùn)行速度太快，因此加了兩個(gè)空循環(huán)來延時(shí)。讀者可以嘗試取消空循環(huán)或增加延時(shí)來感受老鼠鉆迷宮的不同速度。目錄目錄退出退出目錄目錄第36頁 共36頁案例提高改變記載迷宮的方式，記載一條長的通道，而不是一步一步地判斷，可以一次性走很多步。例如，向右的通道有10步，現(xiàn)在的程序是10次循環(huán)，而改進(jìn)后可以一次循環(huán)走10步，不過不能用數(shù)組來記載迷宮，而要采用向量的方式，這樣算法會快捷得多。例如用 （2，7，1）三元組的方式來存儲，表示從第2格到第7格方向是“向右”的一條路，這樣，可以一次走很多步。采用