資源簡介
程序在VC++ 6下順利編譯通過。
一、 實(shí)驗(yàn)?zāi)康模?
（1） 熟練掌握鏈棧的基本操作及應(yīng)用。
（2） 利用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)實(shí)現(xiàn)一個(gè)求解迷宮的非遞歸程序。
二、實(shí)驗(yàn)內(nèi)容：
【問題描述】
以一個(gè)m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對信任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。
【基本要求】
首先實(shí)現(xiàn)一個(gè)鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），……。
【測試數(shù)據(jù)】
迷宮的測試數(shù)據(jù)如下：左上角（1，1）為入口，右下角（8，9）為出口。
1 2 3 4 5 6 7 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
以方陣形式輸出迷宮及其通路。
輸出：
請輸入迷宮的長和寬:5 5
請輸入迷宮內(nèi)容:
0 1 1 0 0
0 0 1 1 0
1 0 0 1 1
1 0 0 1 0
1 1 0 0 0
迷宮的路徑為
括號內(nèi)的內(nèi)容分別表示為(行坐標(biāo),列坐標(biāo),數(shù)字化方向,方向)
(1,1,1,↓)
(2,1,2,→)
(2,2,1,↓)
(3,2,1,↓)
(4,2,2,→)
(4,3,1,↓)
(5,3,2,→)
(5,4,2,→)
(5,5,0,)
迷宮路徑探索成功!
代碼片段和文件信息
#include
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)
{
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;
?P->data=e;
?P->next=top;
?top=P;
}
T?Stack::Pop（）?????????????????//使棧頂元素出棧
{
T?Temp;
linkNode?*P;
P=top;
top=top->next;
Temp=P->data;
delete?P;
return?Temp;
}
T?Stack::GetPop（）???????????????//取出棧頂元素
{
return?top->data;
}
void?Stack::Clear（）????????????????????//把棧清空
{
?top=NULL;
}
bool?Stack::empty（）????????//判斷棧是否為空，如果為空則返回1，否則返回0
{
?if（top==NULL）?return?1;
?else?return?0;
}
int?move[4][2]={{01}{10}{0-1}{-10}};???//定義當(dāng)前位置移動(dòng)的4個(gè)方向
bool?Mazepath（int?**mazeint?mint?n）;??????
?????//尋找迷宮maze中從（0，0）到（mn）的路徑
?????//到則返回true否則返回false
void?PrintPath（Stack?p）;????????//輸出迷宮的路徑
void?Restore（int?**mazeint?mint?n）;????????//恢復(fù)迷宮
int**?GetMaze（int?&mint?&n）;???????//獲取迷宮
?????????????????????????????????//返回存取迷宮的二維指針
int?main（）
{
?int?m=0n=0;???????//定義迷宮的長和寬
?int?**maze;????????//定義二維指針存取迷宮
?maze=GetMaze（mn）;??//調(diào)用GetMaze（int?&mint?&n）函數(shù)，得到迷宮
?if（Mazepath（mazemn））?//調(diào)用Mazepath（int?**mazeint?mint?n）函數(shù)獲取路徑
??cout<<“迷宮路徑探索成功!\n“;
?else?cout<<“路徑不存在!\n“;
?return?0;
}
int**?GetMaze（int?&mint?&n）//返回存取迷宮的二維指針
{
int?**maze;??????????????//定義二維指針存取迷宮
int?i=0j=0;
cout<<“請輸入迷宮的長和寬:“;
int?ab;cin>>a>>b;?????????????//輸入迷宮的長和寬
cout<<“請輸入迷宮內(nèi)容:\n“;
m=a;
n=b;??????????//mn分別代表迷宮的行數(shù)和列數(shù)
maze=new?int?*[m+2];??//申請長度等于行數(shù)加2的二級指針
for（i=0;i
maze[i]=new?int[n+2];
}
for（i=1;i<=m;i++）??????????//輸入迷宮的內(nèi)容，0代表可通，1代表不通
for（j=1;j<=n;j++）
cin>>maze[i][j];
for（i=0;i
for（i=0;i
return?maze;??????????????//返回存貯迷宮的二維指針maze
};
bool?Mazepath（int?**mazeint?mint?n）//尋找迷宮maze中從（0，0）到（mn）的路徑
???????????/ 評論
共有 條評論
川公網(wǎng)安備 51152502000135號