迷宮問題非遞歸求解--數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言課程設(shè)計(jì)-在線瀏覽
2025-08-07 18:50本頁(yè)面
【正文】 ………………4四．詳細(xì)設(shè)計(jì)……………………………6五．代 碼……………………………10六. 測(cè) 試…………………………….15七. 總 結(jié)…………………………….17一. 實(shí)驗(yàn)內(nèi)容任務(wù)：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求：，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求：使用非遞歸算法。，其中1表示迷宮的墻壁，0表示迷宮的通路，從而建立自己的迷宮；，當(dāng)然也可以設(shè)計(jì)出口了；： （1）構(gòu)造棧Stack, T 描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型, LinkNode鏈表結(jié)點(diǎn)三個(gè)類,其中Stack是Linknode的友元類. （2）構(gòu)造存取迷宮的二維指針GetMaze(int amp。n) （3）恢復(fù)迷宮Restore(int **maze,int m,int n) （4）在迷宮中尋找一條通路Mazepath(int **maze,int m,int n) （5）輸出所找到的通路PrintPath() (6) 定義當(dāng)前位置移動(dòng)的4個(gè)方向move數(shù)組.三．總體設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)：首先用二維指針存儲(chǔ)迷宮數(shù)據(jù)，迷宮數(shù)據(jù)由用戶輸入。求得的通路以三元組（i，j，d）形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向（東、南、西、北四個(gè)方向所用代表數(shù)字，自行定義）。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。為處理方便起見，可在迷宮的四周加一圈障礙。經(jīng)過的位置把0變?yōu)?，帶輸出迷宮路徑后在恢復(fù)迷宮院士為止2. 本程序有三個(gè)模塊：⑴ 主程序模塊⑵ 三個(gè)類模塊即其對(duì)象：實(shí)現(xiàn)棧鏈表抽象數(shù)據(jù)類型；⑶ 迷宮二維指針單元模塊：存儲(chǔ)迷宮,尋路徑,輸出迷宮,恢復(fù)迷宮。m,int amp。amp。一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的遞歸或非遞歸程序。迷宮的過程可以模擬為一個(gè)搜索的過程：每到一處，總讓它按東、南、西、北4個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果4方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來(lái)的位置上繼續(xù)試探下一位置。用一個(gè)二維指針數(shù)組迷宮表示迷宮，數(shù)組中每個(gè)元素取值“0”（表示通路）或“1”（表示墻壁）。設(shè)計(jì)一個(gè)模擬走迷宮的算法，為其尋找一條從入口點(diǎn)到出口點(diǎn)的通路。沿某個(gè)方向前進(jìn)一步，它可能到達(dá)的位置最多有4。定義一個(gè)棧，按從入口到出口存取路徑.在搜索過程中，每前進(jìn)一步，如果有新位置入棧，則把上一個(gè)探索的位置存入棧中,當(dāng)前位置”1”（表示這個(gè)位置在通路上），并將該位置的坐標(biāo)壓入棧中。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。為處理方便起見，可在迷宮的四周加一圈障礙。(二). 為實(shí)現(xiàn)算法，需要類的象數(shù)據(jù)類型：類及其對(duì)象:類 Stack 對(duì)象成員如下:Stack()。Stack()。 把元素data壓入棧中T Pop()。 取出棧頂元素 void Clear()。 判斷棧是否為空，如果為空則返回1，否則返回0T類 迷宮中當(dāng)前位置的結(jié)構(gòu)類型: T對(duì)象成員如下:x。 y代表當(dāng)前位置的列坐標(biāo)dir。2）在時(shí)間上為簡(jiǎn)單的鏈表?xiàng)５拇鎯?chǔ)結(jié)構(gòu)，二維指針GetMaze, Restore兩函數(shù)算法時(shí)間復(fù)雜度為O（(m+2)*(n+2)）, Mazepath,PrintPath為O(1),（m為行數(shù)，n為列數(shù)）。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。*/includeiostreamusing namespace std。 //x代表當(dāng)前位置的行坐標(biāo) int y。 //0:無(wú)效,1:東,2:南,3:西,4:北}。public: T data。}。 //指向第一個(gè)結(jié)點(diǎn)的棧頂指針public: Stack()。 //析構(gòu)函數(shù)
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1