迷宮問題非遞歸求解--數(shù)據(jù)結(jié)構(gòu)c語言課程設(shè)計(jì)(編輯修改稿)
2025-02-06 15:06 本頁面
【文章內(nèi)容簡介】 O(1),（ m 為行數(shù)， n 為列數(shù)）。 東華理工大學(xué) 軟件學(xué)院 軟件工程系 10 (五 ) UML 圖 T +X:int +y:int +dir:int 東華理工大學(xué) 軟件學(xué)院 軟件工程系 11 LinkNode +T data Stack +push(T e):void +T Getpop ( ):void +T pop ( ) +empty ( ):bool +Stack ( ) +~Stack ( ) +Clear ( ):void +next LinkNode LinkNode top friend 東華理工大學(xué) 軟件學(xué)院 軟件工程系 12 五．代碼 /*以一個(gè) m n 的長方陣表示迷宮， 0 和 1 分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（ i,j,d）的形式輸出，其中：（ i,j）指示迷宮中的一個(gè)坐標(biāo)， d 表示走到下一坐標(biāo)的方向。如：對(duì)于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（ 1,1,1），（ 1,2,2），（ 2,2,2），（ 3,2,3），（ 3,1,2），?。 */ includeiostream using namespace std。 class T //定義描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型 { public: int x。 //x 代表當(dāng)前位置的行坐標(biāo) int y。 //y 代表當(dāng)前位置的列坐標(biāo) int dir。 //0:無效 ,1:東 ,2:南 ,3:西 ,4:北 }。 class LinkNode //鏈表結(jié)點(diǎn) 東華理工大學(xué) 軟件學(xué)院 軟件工程系 13 { friend class Stack。 public: T data。 LinkNode *next。 }。 class Stack { private: LinkNode *top。 //指向第一個(gè)結(jié)點(diǎn)的棧頂指針 public: Stack()。 //構(gòu)造函數(shù)，置空棧 ~Stack()。 //析構(gòu)函數(shù) void Push(T e)。 //把元素 data 壓入棧中 T Pop()。 //使棧頂元素出棧 T GetPop()。 //取出棧頂元素 void Clear()。 //把棧清空 bool empty()。 //判斷棧是否為空，如果為空則返回 1，否則返回 0 }。 Stack::Stack() //構(gòu)造函數(shù)，置空棧 { top=NULL。 } Stack::~Stack() //析構(gòu)函數(shù) { } void Stack::Push(T e) //把元素 x 壓入棧中 { LinkNode *P。 P=new LinkNode。 Pdata=e。 Pnext=top。 top=P。 } T Stack::Pop() //使棧頂元素出棧 { T Temp。 LinkNode *P。 P=top。 top=topnext。 Temp=Pdata。 delete P。 return Temp。 } 東華理工大學(xué) 軟件學(xué)院 軟件工程系 14 T Stack::GetPop() //取出棧頂元素 { return topdata。 } void Stack::Clear() //把棧清空 { top=NULL。 } bool Stack::empty() //判斷棧是否為空，如果為空則返回 1，否則返回 0 { if(top==NULL) return 1。 else return 0。 } int move[4][2]={{0,1},{1,0},{0,1},{1,0}}。 //定義當(dāng)前位置移動(dòng)的 4 個(gè)方向 bool Mazepath(int **maze,int m,int n)。 //尋找迷宮 maze 中從（ 0，
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1