中國(guó)礦業(yè)大學(xué)信控學(xué)院
?
補(bǔ)一下我之前在博客園發(fā)布的內(nèi)容
?懶得調(diào)了，想復(fù)制完整代碼直接復(fù)制最下面的，想復(fù)制分布代碼去看我博客園鏈接吧
《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程設(shè)計(jì)——迷宮問(wèn)題 - 刷子zz - 博客園
一、?問(wèn)題描述
問(wèn)題中迷宮可用方陣[m,n]表示，0表示能通過(guò)，1表示不能通過(guò)。若要從從左上角[1,1]進(jìn)入迷宮，設(shè)計(jì)算法，尋求一條從右下角 [m,n] 出去的路徑。我們用遞增的數(shù)來(lái)代表尋找出口方向與步數(shù)，用-2來(lái)代表尋找過(guò)程中找錯(cuò)的路徑。
二、?需求分析
?
需要先創(chuàng)建一個(gè)迷宮，在開(kāi)始后就開(kāi)始搜尋，當(dāng)一個(gè)點(diǎn)周圍有0點(diǎn)（改點(diǎn)并不是以搜尋過(guò)的點(diǎn)），那么到這里繼續(xù)往下搜，如果搜到盡頭那么就要倒回去，在搜尋倒回去的周圍還有為搜尋過(guò)得0點(diǎn)，因此需要一個(gè)存儲(chǔ)算法，要滿足后入先出，那么就是棧，利用棧就可以滿足需求。
三、?算法分析
?
1.??? 首先先定義棧，本問(wèn)題中，不需要在中間插入與彈出，插入與彈出操作均在棧頭，因此我們利用順序棧。
并且該棧與實(shí)驗(yàn)課的棧不同，因?yàn)橐獫M足實(shí)際需求，所以我們需要定義步數(shù)以及改點(diǎn)所在的位置以及臨近路徑的位置在我們棧中，具體操作如下。
1 //記錄通道塊在迷宮矩陣當(dāng)中的橫、縱坐標(biāo)
2 struct Position {
3 int x;
4 int y;
5 };
6
7 //放入棧當(dāng)中的通道塊元素
8 struct SElement {
9 int ord;//記錄步數(shù)
10 Position p;//記錄位置
11 int di;//記錄下一次測(cè)試這一路徑的臨近路徑的位置
12 };
13
14 struct MyStack {
15 SElement* base;
16 SElement* top;
17 int stacksize;
18 };
2.??? 棧的一些列基礎(chǔ)操作，例如創(chuàng)建棧，判斷棧是否為空，取棧頂元素，獲取棧長(zhǎng)，入棧，出棧。上述操作類似學(xué)校實(shí)驗(yàn)中基本操作，這里不在敘述，詳見(jiàn)附錄中全部代碼。
3.??? 接下來(lái)創(chuàng)建迷宮，這里迷宮利用數(shù)組來(lái)生成，x軸為n，y軸為m
?? n為18，m為15。生成方法簡(jiǎn)單，這里不在敘述，詳見(jiàn)附錄中全部代碼。
4.??? 接下來(lái)定義如何走這個(gè)迷宮，考慮我們用0作為通道，1作為墻壁，那么搜尋一個(gè)點(diǎn)的上下左右0就是可以通過(guò)，1就是不能通過(guò)。利用以下循環(huán)來(lái)完成目標(biāo)：
步驟1：挪到0處的點(diǎn)并且把剛才位置入棧，讓改點(diǎn)改為步數(shù)，讓步數(shù)加一，然后繼續(xù)搜索其上下左右（除去剛才通過(guò)的點(diǎn)）如果有0，繼續(xù)執(zhí)行步驟1。
步驟2：如果周圍的點(diǎn)無(wú)0（除去剛才已經(jīng)通過(guò)的點(diǎn)），讓改點(diǎn)改為-2，那么就出棧，把路徑調(diào)到剛才的那個(gè)點(diǎn)，并且把步數(shù)減一，然后執(zhí)行步驟1，搜尋其上下左右（出去剛才走錯(cuò)的點(diǎn)以及入這個(gè)點(diǎn)之前的點(diǎn)）。
直至入棧點(diǎn)是終點(diǎn)那么退出循環(huán)。
代碼如下：
1 do
2 {
3 if (Pass(curp))
4 {
5 FootPrint(curp, curStep);//可走就在迷宮里面留下足跡
6 //創(chuàng)建一個(gè)棧元素，存儲(chǔ)可行路徑的相關(guān)值
7 SElement e;
8 e.di = 1;// 下一個(gè)路塊為這一個(gè)路塊的右邊的路塊
9 e.ord = curStep;
10 e.p.x = curp.x;
11 e.p.y = curp.y;
12 Push(&path, e);//將路徑塊入棧
13 if (curp.x == m - 2 && curp.y == n - 2) break; //如果被壓入的路徑塊到了迷宮的終點(diǎn)就退出循環(huán)
14 //找到下一個(gè)被試塊
15 curp = NextPosition(curp, 1);//找到前一個(gè)被試塊東面的路徑塊作為被試塊
16 curStep++;//被探索的步數(shù)加一
17 }
18 else//如果當(dāng)前被試路徑不能夠通過(guò)的話
19 {
20 if (!IsStackEmpty(&path))
21 {
22 SElement e;
23 Pop(&path, &e);
24 curStep--;
25 //將這一段所有的周圍路徑都已經(jīng)被測(cè)試過(guò)的路徑從棧中清除
26 while (e.di == 4 && !IsStackEmpty(&path)) {
27 MarkPrint(e.p);
28 Pop(&path, &e);
29 curStep--;
30 }
31 //如果當(dāng)前棧頂還有未被測(cè)試的路徑就測(cè)試剩余的周圍路徑
32 if (e.di<4)
33 {
34 curp = NextPosition(e.p, e.di + 1);
35 e.di++;
36 curStep++;
37 Push(&path, e);
38 }
39 }
40 }
41 } while (!IsStackEmpty(&path));
5.??? 在定義上述代碼中如何去搜尋，按照從右到下再到左再到上的方法搜尋。代碼如下：
1 //按順時(shí)針?lè)较驈挠议_(kāi)始尋找矩陣當(dāng)中某一個(gè)位置的臨近位置
2 Position NextPosition(Position now, int direction)
3 {
4 Position next;
5 int x = now.x;
6 int y = now.y;
7 switch (direction)
8 {
9 //右
10 case 1: {
11 next.x = x;
12 next.y = y + 1;
13 break;
14 }
15 //下
16 case 2: {
17 next.x = x + 1;
18 next.y = y;
19 break;
20 }
21 //左
22 case 3: {
23 next.x = x;
24 next.y = y - 1;
25 break;
26 }
27 //上
28 case 4:{
29 next.x = x - 1;
30 next.y = y;
31 break;
32 }
33 default:break;
34 }
35 return next;
36}
6.??? 定義是否可以通過(guò)函數(shù)，是就返回ture不是就返回false。代碼如下：
1 //輔助函數(shù)考察當(dāng)前路徑能否通過(guò)
2 bool Pass(Position posi)
3 {
4 //只有路徑所在位置的數(shù)字為0的是可以走的
5 if (Maze[posi.x][posi.y] == 0)
6 {
7 return true;
8 }
9 return false;
10 }
7.??? 定義是入棧和出棧時(shí)如何修改迷宮數(shù)組中的值。代碼如下：
1 //改變改點(diǎn)為步驟數(shù)
2 void FootPrint(Position p, int step)
3 {
4 Maze[p.x][p.y] = step;
5 }
6
7 //路徑不可走的話就留下-2的標(biāo)記
8 void MarkPrint(Position p)
9 {
10 Maze[p.x][p.y] = -2;
11}
8.??? 定義打印迷宮函數(shù)，這個(gè)就是遍歷整個(gè)數(shù)組，過(guò)程簡(jiǎn)單這里不在敘述，見(jiàn)附錄中全部代碼。
四、?結(jié)論
?編輯ing...
五、?參考文獻(xiàn)
[1] 嚴(yán)蔚敏，吳偉民——《數(shù)據(jù)結(jié)構(gòu)》清華大學(xué)出版社2004.2.1
六、?附錄文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-498670.html
完整代碼如下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-498670.html
#include <stdio.h>
#include <malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//記錄通道塊在迷宮矩陣當(dāng)中的橫、縱坐標(biāo)
struct Position {
int x;
int y;
};
//放入棧當(dāng)中的通道塊元素
struct SElement {
int ord;//記錄步數(shù)
Position p;//記錄位置
int di;//記錄下一次測(cè)試這一路徑的臨近路徑的位置
};
struct MyStack {
SElement* base;
SElement* top;
int stacksize;
};
//創(chuàng)建一個(gè)棧如果創(chuàng)建成功則返回1，否則就返回0
int InitStack(MyStack* s)
{
s->base = (SElement*)malloc(STACK_INIT_SIZE * sizeof(SElement));//為棧分配初始空間
if (!s->base) return 0;
s->top = s->base;//設(shè)定為空棧
s->stacksize = STACK_INIT_SIZE;
return 1;
}
//判斷棧是否為空，如果是空的就返回0，否則就返回1
int IsStackEmpty(MyStack* s)
{
if (s->top == s->base) return true;
return false;
}
//獲取棧頂元素,如果棧為空就返回0 否則就返回1
int GetTop(MyStack* s, SElement* e)
{
if (IsStackEmpty(s)) return 0;
e = s->top - 1;
return 1;
}
//獲取棧的長(zhǎng)度，并且通過(guò)程序返回
int StackLength(MyStack* s)
{
return s->top - s->base;
}
//插入元素e為新的棧頂元素，插入成功則返回1，否則返回0
int Push(MyStack* s, SElement e)
{
if (s->top - s->base >= STACK_INIT_SIZE)
{
s->base = (SElement*)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElement));
if (!s->base) return 0;
s->top = s->base + s->stacksize;
s->stacksize += STACKINCREMENT;
}
*(s->top) = e;
s->top++;
return 1;
}
//彈出棧頂元素賦值給e彈出成功返回1，彈出失敗返回0
int Pop(MyStack* s, SElement* e)
{
if (IsStackEmpty(s)) return 0;
*e = *(s->top - 1);
s->top--;
return 1;
}
//定義墻元素為1 可走路徑為0 已知路徑為curStep 不能夠通過(guò)的路徑為-2
#define m 15
#define n 18
int Maze[m][n] = { { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 },
{ 1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1 },
{ 1,0,1,1,1,0,1,0,0,1,0,1,1,1,1,1,0,1 },
{ 1,0,1,1,1,0,1,0,1,1,0,1,0,1,1,0,0,1 },
{ 1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,0,1,1 },
{ 1,1,1,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1 },
{ 1,1,1,0,0,1,1,0,1,1,0,0,0,1,1,1,1,1 },
{ 1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1 },
{ 1,1,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1 },
{ 1,0,0,1,1,1,1,1,1,0,1,1,0,1,0,0,1,1 },
{ 1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,1 },
{ 1,0,0,1,0,1,0,1,0,0,1,1,0,0,0,1,1,1 },
{ 1,1,0,1,0,1,0,1,1,1,0,0,0,1,1,1,1,1 },
{ 1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1 },
{ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 } };
//輔助函數(shù)考察當(dāng)前路徑能否通過(guò)
bool Pass(Position posi)
{
//只有路徑所在位置的數(shù)字為0的是可以走的
if (Maze[posi.x][posi.y] == 0)
{
return true;
}
return false;
}
//按順時(shí)針?lè)较驈挠议_(kāi)始尋找矩陣當(dāng)中某一個(gè)位置的臨近位置
Position NextPosition(Position now, int direction)
{
Position next;
int x = now.x;
int y = now.y;
switch (direction)
{
//右
case 1: {
next.x = x;
next.y = y + 1;
break;
}
//下
case 2: {
next.x = x + 1;
next.y = y;
break;
}
//左
case 3: {
next.x = x;
next.y = y - 1;
break;
}
//上
case 4:
{
next.x = x - 1;
next.y = y;
break;
}
default:break;
}
return next;
}
//改變改點(diǎn)為步驟數(shù)
void FootPrint(Position p, int step)
{
Maze[p.x][p.y] = step;
}
//路徑不可走的話就留下-2的標(biāo)記
void MarkPrint(Position p)
{
Maze[p.x][p.y] = -2;
}
//打印出迷宮矩陣
void Display_migong()
{
for (int i = 0; i<m; i++)
{
for (int j = 0; j<n; j++)
{
if (Maze[i][j]<0)
printf("%d ", Maze[i][j]);
else if (Maze[i][j]<10)
printf("%d ", Maze[i][j]);
else
printf("%d ", Maze[i][j]);
}
printf("\n");
}
}
int main()
{
//迷宮程序主體
MyStack path;//記錄路徑的棧
InitStack(&path);//初始化路徑數(shù)組
Position curp;//當(dāng)前被試位置
Display_migong();
//初始化當(dāng)前位置為矩陣入口
curp.x = 1;
curp.y = 1;
int curStep = 1;//被探索的步數(shù)
do
{
if (Pass(curp))
{
FootPrint(curp, curStep);//可走就在迷宮里面留下足跡
//創(chuàng)建一個(gè)棧元素，存儲(chǔ)可行路徑的相關(guān)值，將這個(gè)元素存儲(chǔ)到棧當(dāng)中
SElement e;
e.di = 1;//下一個(gè)路塊為這一個(gè)路塊的右邊的路塊
e.ord = curStep;
e.p.x = curp.x;
e.p.y = curp.y;
Push(&path, e);//將路徑塊入棧
if (curp.x == m - 2 && curp.y == n - 2) break; //如果被壓入的路徑塊到了迷宮的終點(diǎn)就退出循環(huán)
curp = NextPosition(curp, 1);//找到前一個(gè)被試塊東面的路徑塊作為被試塊
curStep++;//被探索的步數(shù)加一
}
else//如果當(dāng)前被試路徑不能夠通過(guò)的話
{
if (!IsStackEmpty(&path))
{
SElement e;
Pop(&path, &e);
curStep--;
//將所有的周圍路徑都已經(jīng)被測(cè)試過(guò)的路徑從棧中清除
while (e.di == 4 && !IsStackEmpty(&path)) {
MarkPrint(e.p);
Pop(&path, &e);
curStep--;
}
//如果當(dāng)前棧頂還有未被測(cè)試的路徑就測(cè)試剩余的周圍路徑
if (e.di<4)
{
curp = NextPosition(e.p, e.di + 1);
e.di++;
curStep++;
Push(&path, e);
}
}
}
} while (!IsStackEmpty(&path));
printf("\n");
//打印出結(jié)果迷宮矩陣
Display_migong();
return 0;
}到了這里，關(guān)于《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程設(shè)計(jì)——迷宮問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【Python數(shù)據(jù)結(jié)構(gòu)與算法】--- 遞歸算法的應(yīng)用 ---[烏龜走迷宮] |人工智能|探索掃地機(jī)器人工作原理](https://imgs.yssmx.com/Uploads/2024/02/752756-1.gif)
