迷宮問題非遞歸求解--數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言課程設(shè)計(jì)-文庫(kù)吧
2024-12-26 15:06 本頁(yè)面
【正文】 ，自行定義）。 迷宮的過程可以模擬為一個(gè)搜索的過程：每到一處，總讓它按東、南、西、北 4 個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果 4 方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來的位置上 繼續(xù)試探下一位置。 每前進(jìn)或后退一步，都要進(jìn)行判斷：若前進(jìn)到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。 用一個(gè)二維指針數(shù)組迷宮表示迷宮，數(shù)組中每個(gè)元素取值“ 0”（表示通路）或“ 1”（表示墻壁）。迷宮的入口點(diǎn)在位置（ 1， 1）處，出口點(diǎn)在位置（ m,n）處。設(shè)計(jì)一個(gè)模擬走迷宮的算法，為其尋找一條從入口點(diǎn)到出口點(diǎn)的通路。 二維數(shù)組的第 0 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“ 1”， 表示迷宮的外墻；第 1 行第 1 列元素和第 m 行第 m 列元素置成“ 0”， 表示迷宮的入口和出口；其余元素值用 GetMaze 函數(shù)獲取 . 假設(shè)當(dāng)前所在位置是（ x,y）。沿某個(gè)方向前進(jìn)一步，它可能到達(dá)的位置最多有 4。 如果用二維數(shù)組 move 記錄 4 方向上行下標(biāo)增量和列下標(biāo)增量，則沿第 i 個(gè)方向前進(jìn)一步，可能到達(dá)的新位置坐標(biāo)可利用 move 數(shù)組確定： x=x+move[loop][0] y=y+move[loop][1] 從迷宮的入口位置開始，沿圖示方向順序依次進(jìn)行搜索。定義一個(gè)棧，按從入口到出口存取路徑 . 在搜索過程中，每前進(jìn)一步，如果有新位置入棧，則把上一個(gè)探索的位置存入棧中 ,當(dāng)前位置 ”1”（ 表示這個(gè)位置在通路上），并將該位置的坐標(biāo)壓入棧中。 如果沒有新位置入棧，則返回到上一個(gè)位置 . 到達(dá)出口后 ,最后一個(gè)位置入棧 ,輸出路徑 ,并回復(fù)路徑 .把 1 變?yōu)?0. 東華理工大學(xué) 軟件學(xué)院 軟件工程系 8 總之 ,入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。 迷宮的入口點(diǎn)的下標(biāo)為（ 1， 1），出口點(diǎn)的下標(biāo)為（ m， n）。為處理方便起見，可在迷宮的四周加一圈障礙。對(duì)于迷宮的任一位置，均可約定有東、南、西、北四個(gè) 方向可通。 (二 ). 為實(shí)現(xiàn)算法，需要類的象數(shù)據(jù)類型： 類及其對(duì)象 : 類 Stack 對(duì)象成員如下 : Stack()。 構(gòu)造函數(shù)，置空棧操作結(jié)果：構(gòu)造一個(gè)空的棧 S。 Stack()。 析構(gòu)函數(shù) void Push(T e)。 把元素 data 壓入棧中 T Pop()。 使棧頂元素出棧 T GetPop()。 取出棧頂元素 void Clear()。 把棧清空 bool empty()。 判斷棧是否為空，如果為空則返回 1，否則返回 0 T類 迷宮中當(dāng)前位置的結(jié)構(gòu)類型 : T 對(duì)象成員如下 : x。 x代表當(dāng)前位置的行坐標(biāo) y。 y代表當(dāng)前位置的列坐標(biāo) dir。 0:無(wú)效 ,1:東 ,2:南 ,3:西 ,4:北 LinkNode類 鏈表結(jié)點(diǎn) : 對(duì)象成員如下 : 友元類 Stack T data LinkNode *next 東華理工大學(xué) 軟件學(xué)院 軟件工程系 9 (三 ).函數(shù)調(diào)用關(guān)系 main GetMaze Mazepath Empy() GetPop() Push() PrintPath() Restore() Pop() GetPop() Push() (四 ) 算法的時(shí)間、空間復(fù)雜度 1）本算法在空間上主要開辟了 一 個(gè) 二維指針 ，規(guī)模都是迷宮 (m+2)*(n+2)，一個(gè)是 棧 ，一個(gè)是迷宮 路徑 記錄，輸出時(shí)候 調(diào)用棧 ， 在恢復(fù)迷宮 。 2）在時(shí)間上為簡(jiǎn)單的 鏈表?xiàng)５拇鎯?chǔ)結(jié)構(gòu) ， 二維 指針 GetMaze, Restore 兩函數(shù) 算法時(shí)間復(fù)雜度為 O（ (m+2)*(n+2)） , Mazepath,PrintPath 為
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1