【正文】 華 北 科 技 學 院數(shù)據(jù)結構課程設計說明書班級 小組成員:______成績: _____小組成員: 成績: _____小組成員: _成績: _____設計題目:_____ 迷宮問題 _______ 設計時間: 至 指導教師:___ _____________ 評 語:________________________________ _________________________________________ _________________________________________ _________________________________________ 評閱教師: _____________目錄設計總說明 II第1章 課程設計內容和要求 1 1 1 2第2章 課程設計總體方案及分析 3 問題分析 3 系統(tǒng)總體設計 4 6第3章 程序運行結果與分析 11 調試分析 11 測試結果 11第4章 心得總結 20參考文獻 21附錄 22設計總說明：本課程設計是解決迷宮求解的問題，從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，需要用一個保存從入口到當前位置的路徑的結構。因此，在求迷宮通路的算法中要應用“隊列”的思想假設“當前位置”指的是“在搜索過程中的某一時刻所在圖中某個方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當前位置”，如此重復直至到達出口；若當前位置“不可通”，則應順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。所謂“下一位置”指的是當前位置四周4個方向（上、下、左、右）上相鄰的方塊。假設以隊列記錄“當前路徑”，則隊列中存放的是“當前路徑上最后一個通道塊”。由此，“納入路徑”的操作即為“當前位置入隊”；“從當前路徑上刪除前一通道塊”的操作即為“出隊”。關鍵詞：迷宮；窮舉；隊列。第1章 課程設計內容和要求 迷宮問題是取自心理學的一個古典實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒子中設置了許多墻，對行進方向形成了多處阻擋。盒子僅有一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重復進行上述實驗，一直到老鼠從入口走到出口，而不走錯一步。老鼠經(jīng)過多次試驗最終學會走通迷宮的路線。設計一個計算機程序對任意設定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的論。 要求設計程序輸出如下：(1) 建立一個大小為mn的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生成），并在屏幕上顯示出來；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點 的坐標。（3）用一種標志（如數(shù)字8）在迷宮中標出該條通路；（4）在屏幕上輸出迷宮和通路；（5）上述功能可用菜單選擇。用戶進入菜單頁面選擇迷宮的狀態(tài)（1表示手動生成迷宮，2表示自動生成迷宮，3表示迷宮游戲，4表示退出）運用本迷宮系統(tǒng)，用戶可以根據(jù)自己的需求輸入所需的迷宮，其中0表示通路，1表示障礙。用戶可以自己定義迷宮并設置其中的障礙，以矩陣形式輸入，也可通過定義迷宮的行列數(shù)由系統(tǒng)自動生成迷宮。本系統(tǒng)自帶一迷宮地圖可供用戶娛樂，用戶的最高成績可以被保存，下次進入游戲系統(tǒng)可以刷新紀錄。第2章 課程設計總體方案及分析 問題分析要建立迷宮首先就要建立存儲結構，這里我們用數(shù)組的方式建立的。根據(jù)用戶輸入的迷宮的大?。ㄎ覀冊O置的最大值為40可以根據(jù)要求調解），迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述；迷宮是一個矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個位置都可以用其行列號來唯一指定，但是二維數(shù)組不能動態(tài)定義其大小，我們可以考慮先定義一個較大的二維數(shù)組maze[M+2][N+2],然后用它的前m行n列來存放元素，即可得到一個mn的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m1,n1)表示迷宮出口位置。注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為339，當然，用戶也可根據(jù)需要，調整其大小。首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復出現(xiàn)，則將已搜索過的位置標記為2，同時保留搜索痕跡，在考慮進入下一個位置搜索之前，將當前位置保存在一個隊列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。以矩陣 0 0 1 0 1 為例，來示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0首先，將位置(0,0)(序號0)放入隊列中，其前節(jié)點為空，從它開始搜索，其標記變?yōu)?，由于其只有一個非障礙位置，所以接下來移動到(0,1)(序號1)，其前節(jié)點序號為0，標記變?yōu)?，然后從(0,1)移動到(1,1)(序號2)，放入隊列中，其前節(jié)點序號為1，(1,1)存在(1，2)(序號3)、(2，1)(序號4)兩個可移動位置，它的相鄰非障礙節(jié)點均入隊列，且它們的前節(jié)點序號均為該位置的序號，所以如果存在路徑，則從出口處節(jié)點的位置，逆序就可以找到其從出口到入口的通路。 搜索路徑表012345678910(0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)(3,4)10122345679由此可以看出，得到最短路徑(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)4. 輸出結果輸出的結果分為兩種，一種是直觀的用圖給出的通路，其中通路用☆表示，第二種輸出的是尋找完后的路徑，路徑用具體的坐標來表示。 系統(tǒng)總體設計 1. 功能結構圖 (1)構建一個二維數(shù)組maze[M+2][N+2]用于存儲迷宮矩陣 (2)自動或手動生成迷宮，即為二維數(shù)組maze[M+2][N+2]賦值 (3)構建一個隊列用于存儲迷宮路徑 (4)建立迷宮節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況 (5)實現(xiàn)搜索算法 (6)屏幕上顯示操