【正文】 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè)計說明書 迷宮問題求解 學 生 姓 名 學號 班級 成績 指 導(dǎo) 教 師 計算機科學與技術(shù)系 2021 年 9 月 9 日 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計評閱書 題 目 迷宮問題求解 學生姓名 學號 指導(dǎo)教師評語及成績 成績： 教師簽名： 年 月 日 答辯教師評語及成績 成績： 教師簽名： 年 月 日 教研室意見 總成績： 室主任簽名： 年 月 日 注：指導(dǎo)教師成績 60%，答辯成績 40%，總成績合成后按五級制記入。 課程設(shè)計任務(wù)書 2021 — 2021 學年第 一 學期 專業(yè)： 學號： 姓名： 課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè)計題目： 迷宮問題求解 完成期限：自 2021 年 8 月 29 日至 2021 年 9 月 9 日共 2 周 設(shè)計依據(jù)、要求及主要內(nèi)容（可另加附頁）： 輸入一個任意大小的迷宮數(shù)據(jù)，設(shè)置入口、出口及障礙，借助棧結(jié)構(gòu)求解走出迷宮的路徑并輸出。 ，采用 C/C++實現(xiàn)。 ，操作簡便，容錯性。 基本要求如下： 1）問題分析和任務(wù)定義：根據(jù)設(shè)計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？確定問題的輸入數(shù)據(jù)集合。 2）邏輯設(shè)計：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明），各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖； 3）詳細設(shè)計 ：定義相應(yīng)的存儲結(jié)構(gòu)。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作做出進一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義； 4）程序編碼：把詳細設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚； 5）程序調(diào)試與測試：能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確保程序正確。調(diào)試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結(jié)果； 6）結(jié)果分析：程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果； 7）編寫課程設(shè)計報告； 以上要求中前三個階段的任務(wù)完成后，先將設(shè)計說明書的草稿交指導(dǎo)老師面審，審查合格后方可進入后續(xù)階段的工作。設(shè)計工作結(jié)束后，經(jīng)指導(dǎo)老師驗收合格后將設(shè)計說明書打印裝訂，并進行答辯。 指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準日期： 2021 年 8 月 29 日 摘 要 設(shè)計了一個尋找迷宮出口路徑的程序，該程序具有設(shè)置任 意大小的迷宮數(shù)據(jù)，通過設(shè)置的迷宮入口出口及障礙，探索出一條簡單路徑并輸出的功能。該程序采用 VC 作為軟件開發(fā)環(huán)境，借助棧先入后出的特點，先將入口作為檢索的起點，順著某個方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路返回，換個方向在繼續(xù)探索，直到所有可能的通路都探索到為止，最后把探索到的路徑輸出。 關(guān)鍵詞： 迷宮路徑；探索；輸出 目 錄 ............................................................... 1 ..................................................... 2 ............................................................... 3 ............................................................... 4 迷宮數(shù)據(jù)的存儲 .................................................... 4 當前位置可通性的判斷及探索方向的改變 .............................. 5 無通路時沿原路返回 ................................................ 6 路徑信息入棧和出棧 ................................................ 7 當前探索位置的切換 ................................................ 8 最終探索路徑的輸出及標記 .......................................... 9 打印迷宮信息 ..................................................... 10 .............................................................. 11 文件包含和結(jié)構(gòu)體的定義 ........................................... 11 棧的初始化及入棧出棧函數(shù) ......................................... 11 申請迷宮大小及障礙的設(shè)置 ......................................... 12 通道可通性測試 ................................................... 13 為走過的通道留下足跡 ............................................. 13 探索位置的切換 ................................................... 13 入口到出口的路徑探索 ............................................. 14 打印迷宮信息 ..................................................... 15 主函數(shù) ........................................................... 16 .............................................................. 18 總結(jié) .................................................................... 21 參考文獻 ................................................................ 22 _x0001_ 1 百手起駕 整理為您 本次課題是實現(xiàn)迷宮問題的求解，利用 C 語言設(shè)計一個能實現(xiàn)輸入一個任意大小的迷宮數(shù)據(jù)，利用二維數(shù)組來儲存設(shè)置的入口、出口及障礙，借助棧先入后出的結(jié)構(gòu)特性保存迷宮探索過程中留下的路徑信息，以便在遇到障礙時 沿原路返回，在探索結(jié)束后輸出棧中保存的最終路徑。 _x0001_ 2 百手起駕 整理為您 迷宮求解的實現(xiàn)依賴于路徑探索的算法，路徑探索的算法采用的是“窮舉求解”的方法。因此有以下問題： (1)數(shù)據(jù)存儲結(jié)構(gòu)的選擇。 (2)當前位置的可通性判斷及探索方向的改變。 (3)道路不通時沿原路返回的算法。 (4)路徑信息的入棧和出棧。 (5)最終路徑的輸出。 _x0001_ 3 百手起駕 整理為您 程序要實現(xiàn)路徑探索及輸出即要實現(xiàn)當前位置可通性的判斷；路徑可通時朝默認方向繼續(xù)向前探索，路徑不可通時沿原路返回改變探索方向，輸出最終探索結(jié)果。其關(guān)系如圖 所示。 開始當前位置是否可通給定當前位置朝默認方向繼續(xù)向前探索Y后退一步改變方向繼續(xù)探索N結(jié)束 圖 迷宮路徑探索功能結(jié)構(gòu) _x0001_ 4 百手起駕 整理為您 迷宮數(shù)據(jù)的存儲 Maze 是指向指針的指針，用行 h和列 l來存儲迷宮的大小，使用 malloc 申請一個二維數(shù)組，根據(jù)用戶輸入的障礙坐標在 maze 數(shù)組的相應(yīng)位置存入 1 作為障礙標記，直到用戶輸入 0 0 結(jié)束障礙的設(shè)置。該模塊的執(zhí)行過程如圖 所示。 int i =0,j=0。int h ,l,n,mihmaze =( int **) malloc(sizeof (int )* h)maze [i]=( int *) malloc(sizeof (int )* l)i++Yscanf (% d%d,amp。 n,amp。 m)!( n== 0amp。amp。 m== 0)maze [n][ m]= 1scanf ( dc%d,amp。 n,amp。 m)YN開始結(jié)束 圖 迷宮數(shù)據(jù)的存儲 _x0001_ 5 百手起駕 整理為您 當前位置可通性的判斷及探索方向的改變 當前位置 curpos的坐標在 maze數(shù)組中對應(yīng)位置儲存的數(shù)據(jù)若非 1和 8即為可通在此留下足跡，由變量 di 來記錄下一個探索方向，把 下一個位置作為當前位置并繼續(xù)探索，若當前位置不可通，則后退一步按順時針方向改變探索方向。操作流程如圖 所示。 Maze [ curpos . y ][ curpos . x ]!= 1 amp。amp。maze [ curpos . y ][ curpos . x ]!= 8f ootprint ( maze , curpos )Yc urpos = nextpos ( curpos , e . di )e . di = 1 。curpos = startcurpos == endNback ( maze , curpos )Ne . di ++Yc urpos = nextpos ( curpos , e . di )結(jié)束Ye . di 4N開始 圖 可通性的判斷及探索方向的改變 _x0001_ 6 百手起駕 整理為您 無通路時沿原路返回 借助棧先入后出的特性，把探索過的路徑信息 e 壓入棧 s 中。若當前位置 curpos的下一個探索方向的變量值 di 為 4 時，表示當前位置周圍四個方向均無通道，沿原路退回一步將路徑信息 e 逐個出棧，一退直到 di4，改變方向繼續(xù)探索。該模塊的執(zhí)行過程如圖 所示。 s . top != s . basep op ( s , e )Ye . di == 4 amp。amp。s . top != s . baseNYYpass ( maze , curpos )N開始結(jié)束N 圖 無