迷宮問題非遞歸求解--數(shù)據(jù)結(jié)構(gòu)c語言課程設(shè)計-wenkub
2023-01-25 15:06:37 本頁面
【正文】 一 . 實驗內(nèi)容 ………………………… .3 二 . 需求分析 …………………………… 3 三．總體設(shè)計 …………………………… 4 四．詳細(xì)設(shè)計 …………………………… 6 五．代 碼 …………………………… 10 六 . 測 試 ……………… …………… .15 七 . 總 結(jié) …………………………… .17 東華理工大學(xué) 軟件學(xué)院 軟件工程系 3 一 . 實驗內(nèi)容 任務(wù)：可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； 要求： 二 .需求分析 ，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； 要求：使用非遞歸算法。 一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的遞歸或非遞歸程序。 迷宮 的入口點的下標(biāo)為（ 1， 1），出口點的下標(biāo)為（ m， n）。 東華理工大學(xué) 軟件學(xué)院 軟件工程系 5 (二 )流程圖 存 取 迷 宮 GetMaze(int amp。p().y==().y) 輸入迷宮的長和寬 內(nèi)容 顯示結(jié)果 Printpath（） 迷宮無路經(jīng) END 數(shù)組 move 用于更改方向 , 函數(shù) Push, PrintPath, Restore 調(diào)用 函數(shù) GetPop, Push, Pop 恢復(fù)迷宮 Restore() 調(diào)用 東華理工大學(xué) 軟件學(xué)院 軟件工程系 6 東華理工大學(xué) 軟件學(xué)院 軟件工程系 7 四．詳細(xì)設(shè)計 (一 ).基 本算法： 首先用二維指針存儲迷宮數(shù)據(jù)，迷宮數(shù)據(jù)由用戶輸入。 每前進或后退一步，都要進行判斷：若前進到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。 二維數(shù)組的第 0 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“ 1”， 表示迷宮的外墻；第 1 行第 1 列元素和第 m 行第 m 列元素置成“ 0”， 表示迷宮的入口和出口；其余元素值用 GetMaze 函數(shù)獲取 . 假設(shè)當(dāng)前所在位置是（ x,y）。 如果沒有新位置入棧，則返回到上一個位置 . 到達出口后 ,最后一個位置入棧 ,輸出路徑 ,并回復(fù)路徑 .把 1 變?yōu)?0. 東華理工大學(xué) 軟件學(xué)院 軟件工程系 8 總之 ,入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。對于迷宮的任一位置，均可約定有東、南、西、北四個 方向可通。 析構(gòu)函數(shù) void Push(T e)。 把棧清空 bool empty()。 0:無效 ,1:東 ,2:南 ,3:西 ,4:北 LinkNode類 鏈表結(jié)點 : 對象成員如下 : 友元類 Stack T data LinkNode *next 東華理工大學(xué) 軟件學(xué)院 軟件工程系 9 (三 ).函數(shù)調(diào)用關(guān)系 main GetMaze Mazepath Empy() GetPop() Push() PrintPath() Restore() Pop() GetPop() Push() (四 ) 算法的時間、空間復(fù)雜度 1）本算法在空間上主要開辟了 一 個 二維指針 ，規(guī)模都是迷宮 (m+2)*(n+2)，一個是 棧 ，一個是迷宮 路徑 記錄，輸出時候 調(diào)用棧 ， 在恢復(fù)迷宮 。 首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。 class T //定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型 { public: int x。 cla
試題試卷相關(guān)推薦
鄂ICP備17016276號-1