使用數據結構 棧（Stack）來實現一種低級的迷宮尋路的功能。
低級是因為無法判斷路徑是不是最短的。

這里使用的棧結構如圖 (這圖我選擇死亡...)

注意結構體里DataType的實際含義，是另外一個結構體，用于儲存二維位置x，y

地圖使用一個10x10的二維數組來表示，數字1表示該點是墻壁，0表示可以行走，2表示已經走過的地方。

我們用棧來儲存走過的位置，比如我們從起點(4,0)出發，就把(4,0)壓入棧，并把該點數值改為2，意為已經來過了。
如果遇到死路，那就不停地出棧，直到棧頂的這個點周圍有路可走為止。

?

邏輯部分偽代碼如下

while(沒有到達終點)
{
　　if(上下左右四個方向有路可走)
　　{
　　　　將可以走的那個位置（不是當前位置！）壓入棧
　　}
　　else
　　{
　　　　出棧
　　}
}

?

1 #include <stack> 2 #include <iostream> 3 4 using std::cout; 5 using std::endl; 6 using std::stack; 7 8 const int MAZEWIDTH = 10; 9 const int MAZEHEIGHT = 10; 10 11 //0可走 12 //1墻 13 //2走過 14 //3走過又退回來了 15 int Maze[MAZEWIDTH][MAZEHEIGHT] = { 16 //0 1 2 3 4 5 6 7 8 9 17 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,//0 18 1, 0, 1, 0, 0, 0, 1, 0, 0, 0,//1 19 1, 0, 0, 0, 1, 0, 1, 0, 0, 1,//2 20 1, 0, 1, 1, 0, 0, 1, 1, 0, 1,//3 21 1, 0, 1, 0, 0, 1, 0, 1, 0, 1,//4 22 0, 0, 1, 1, 0, 1, 0, 0, 0, 1,//5 23 1, 1, 0, 0, 0, 0, 1, 0, 1, 1,//6 24 1, 0, 1, 1, 1, 0, 1, 0, 0, 1,//7 25 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,//8 26 1, 1, 1, 1, 1, 1, 1, 1, 1, 1//9 27 }; 28 29 struct _XY { 30 int x, y; 31 32 _XY() { 33 x = y = 0; 34 } 35 36 _XY(int a, int b) : x(a), y(b) { } 37 38 int operator==(const struct _XY &a) { 39 return (a.x == x) && (a.y == y); 40 } 41 }; 42 43 typedef _XY XY; 44 45 class MazeBreaker { 46 private: 47 int MazeMap[MAZEWIDTH][MAZEHEIGHT]; 48 stack<XY> path; 49 XY start, end; 50 51 52 void push(XY xy) { 53 path.push(xy); 54 MazeMap[xy.x][xy.y] = 2; 55 } 56 57 void push(int x, int y) { 58 path.push(XY(x, y)); 59 MazeMap[x][y] = 2; 60 } 61 62 void pop() { 63 if (!(path.top() == start)) { 64 XY &loc = path.top(); 65 MazeMap[loc.x][loc.y] = 3; 66 path.pop(); 67 } 68 } 69 70 int End() { 71 return path.top() == end; 72 } 73 74 void ThereIsAWay() { 75 XY &loc = path.top(); 76 //UP 77 if (MazeMap[loc.x - 1][loc.y] == 0) { 78 push(loc.x - 1, loc.y); 79 return; 80 } 81 //RIGHT 82 if (MazeMap[loc.x][loc.y - 1] == 0) { 83 push(loc.x, loc.y - 1); 84 return; 85 } 86 //DOWN 87 if (MazeMap[loc.x + 1][loc.y] == 0) { 88 push(loc.x + 1, loc.y); 89 return; 90 } 91 //LEFT 92 if (MazeMap[loc.x][loc.y + 1] == 0) { 93 push(loc.x, loc.y + 1); 94 return; 95 } 96 pop(); 97 return; 98 } 99 100 public: 101 102 void GenerateMap() { 103 for (int lop = 0; lop < MAZEWIDTH; lop++) { 104 for (int lop2 = 0; lop2 < MAZEHEIGHT; lop2++) { 105 MazeMap[lop][lop2] = Maze[lop][lop2]; 106 } 107 } 108 push(start); 109 } 110 111 MazeBreaker() { 112 start.x = 5; 113 start.y = 0; 114 end.x = 1; 115 end.y = 9; 116 } 117 118 void FindPath() { 119 while (!End()) { 120 ThereIsAWay(); 121 } 122 123 for (int lop = 0; lop < MAZEWIDTH; lop++) { 124 for (int lop2 = 0; lop2 < MAZEHEIGHT; lop2++) { 125 if (MazeMap[lop][lop2] == 2) { 126 cout << "O"; 127 } else if (MazeMap[lop][lop2] == 3) { 128 cout << "X"; 129 } else { 130 cout << " "; 131 } 132 } 133 cout << endl; 134 } 135 } 136 137 }; 138 139 int main() { 140 MazeBreaker mb; 141 mb.GenerateMap(); 142 mb.FindPath(); 143 return 0; 144 }

?

?

///以下是老版本

?

首先是棧的頭文件，注意棧結構體內容的具體定義

Stack.h

1 #ifndef _STACK_H_ 2 #define _STACK_H_ 3 4 #include<stdio.h> 5 #include<stdlib.h> 6 7 //以下兩個數據大小視實際情況而定 8 //初始棧容量 9 #define STACK_INIT_SIZE 20 10 //每次擴容的增量 11 #define STACKINCREMENT 10 12 13 //迷宮地圖 14 int Maze[10][10]; 15 16 //表示位置 17 struct xy 18 { 19 int x, y; 20 }; 21 typedef struct xy XY; 22 typedef XY DataType; 23 24 struct stack 25 { 26 //指向棧最頂上的元素的接下來一個位置 27 //表示新入棧的值可以放在指向的地方 28 DataType *Top; 29 //指向棧底部，最里面的元素 30 DataType *Bottom; 31 //表示了當前棧的容量 32 int stacksize; 33 }; 34 typedef struct stack STACK; 35 36 //新建棧 37 int InitStack(STACK *S); 38 39 //銷毀棧 40 int DestroyStack(STACK *S); 41 42 //返回頂層元素 43 int GetTop(STACK S,int *x,int *y); 44 45 //Push操作，入棧，壓棧 46 int Push(STACK *S, int x,int y); 47 48 //Pop操作，出棧 49 int Pop(STACK *S); 50 51 #endif

然后是定義

Stack.c

1 #include"Stack.h" 2 3 int InitStack(STACK *S) 4 { 5 //創建出設定長度的順序表，地址賦給bottom指針 6 S->Bottom = (DataType*)malloc(STACK_INIT_SIZE*sizeof(DataType)); 7 if (!S->Bottom) 8 { 9 return 0; 10 } 11 S->stacksize = STACK_INIT_SIZE; 12 S->Top = S->Bottom; 13 return 1; 14 } 15 16 int DestroyStack(STACK *S) 17 { 18 S->Top = NULL; 19 free(S->Bottom); 20 S->Bottom = NULL; 21 return 1; 22 } 23 24 int GetTop(STACK S, int *x, int *y) 25 { 26 if (S.Bottom != S.Top) 27 { 28 //由于top指向的是最頂上元素的下一個位置 29 //所以取出最頂上元素的時候 30 //要把top減去1 31 *x = ((S.Top - 1)->x); 32 *y = ((S.Top - 1)->y); 33 return 1; 34 } 35 return 0; 36 } 37 38 int Push(STACK *S, int x,int y) 39 { 40 //當超出當前棧的容量時 41 //這里應該只有等于的情況 42 //而不會大于 43 if ((S->Top - S->Bottom) >= S->stacksize) 44 { 45 //realloc函數將開辟指定的儲存空間 46 //并將原來的數據全部移到這個新的儲存空間 47 S->Bottom = (DataType*)realloc(S->Bottom, (S->stacksize + STACKINCREMENT)*sizeof(DataType)); 48 if (!S->Bottom) 49 { 50 return 0; 51 } 52 //由于重新開辟了空間 53 //需要重新根據bottom指針的位置指定top 54 S->Top = S->Bottom + S->stacksize; 55 //最后增加當前棧容量 56 S->stacksize += STACKINCREMENT; 57 } 58 //再把入棧的數據存放好 59 (S->Top)->x = x; 60 (S->Top)->y = y; 61 S->Top++; 62 63 //在地圖上將該點標為2 64 Maze[x][y] = 2; 65 return 1; 66 } 67 68 //將該點丟棄 69 int Pop(STACK *S) 70 { 71 if (S->Bottom == S->Top) 72 { 73 printf("Empty Stack!Can not pop!\n"); 74 return 0; 75 } 76 //top指針先減1再取值 77 --S->Top; 78 return 1; 79 }

?

尋路的邏輯放在了main函數里，迷宮地圖的定義也在這里

main.c

二維數組Maze存放了迷宮的信息，你也可以自己改改*。

1 #include"Stack.h" 2 3 #define Up 1 4 #define Right 2 5 #define Down 3 6 #define Left 4 7 //代表已無路可走 8 //End of Road 9 #define EOR 5 10 11 //迷宮的地圖 12 //墻壁表示為1，可走的地方表示為0，走過的地方表示為2 13 //入口為(4,0)，出口為(0,8) 14 //可自行更改，但請確保有通路 15 16 Maze[10][10] = { 17 //0,1,2,3,4,5,6,7,8,9 18 1,1,1,1,1,1,1,1,0,1, //0 19 1,0,0,0,0,0,0,1,0,1, //1 20 1,0,1,0,1,1,1,1,0,1, //2 21 1,0,1,0,1,0,0,0,0,1, //3 22 0,0,1,0,1,0,1,0,1,1, //4 23 1,0,1,0,1,0,1,0,1,1, //5 24 1,1,0,0,1,0,1,0,1,1, //6 25 1,0,0,1,1,0,1,0,1,1, //7 26 1,0,0,0,0,0,1,0,0,1, //8 27 1,1,1,1,1,1,1,1,1,1 }; //9 28 29 //打印結果 30 int Print() 31 { 32 int lop, lop2; 33 for (lop = 0; lop < 10; lop++) 34 { 35 for (lop2 = 0; lop2 < 10; lop2++) 36 { 37 if (Maze[lop][lop2] == 2) 38 { 39 printf("1"); 40 } 41 else 42 { 43 printf(" "); 44 } 45 } 46 printf("\n"); 47 } 48 return 1; 49 } 50 51 int GameOver(STACK s, XY *loc,XY End) 52 { 53 GetTop(s, &(loc->x), &(loc->y)); 54 if (loc->x == End.x && loc->y == End.y) 55 { 56 return 1; 57 } 58 else 59 { 60 return 0; 61 } 62 } 63 64 //1 up.2 right.3 down.4 left 65 //看看當前位置的上下左右還有沒有能走的地方 66 int SearchPath(STACK s, XY loc) 67 { 68 int x, y; 69 x = loc.x; 70 y = loc.y; 71 72 //Up Available? 73 if (x != 0) 74 { 75 if (!Maze[x - 1][y]) 76 { 77 return Up; 78 } 79 } 80 //Right ? 81 if (y != 9) 82 { 83 if (!Maze[x][y + 1]) 84 { 85 return Right; 86 } 87 } 88 //Down? 89 if (x != 9) 90 { 91 if (!Maze[x + 1][y]) 92 { 93 return Down; 94 } 95 } 96 //Left? 97 if (y != 0) 98 { 99 if (!Maze[x][y - 1]) 100 { 101 return Left; 102 } 103 } 104 return EOR; 105 } 106 107 int main() 108 { 109 //儲存走出迷宮的路徑 110 STACK Path; 111 //儲存當前位置 112 XY loc; 113 //起點終點的位置 114 XY Start = { 4,0 }, End = { 0,8 }; 115 116 InitStack(&Path); 117 //將起點入棧 118 Push(&Path, Start.x, Start.y); 119 120 //開始 121 while (!GameOver(Path, &loc, End)) 122 { 123 switch (SearchPath(Path, loc)) 124 { 125 case Up: 126 Push(&Path, loc.x - 1, loc.y); 127 break; 128 case Right: 129 Push(&Path, loc.x, loc.y + 1); 130 break; 131 case Down: 132 Push(&Path, loc.x + 1, loc.y); 133 break; 134 case Left: 135 Push(&Path, loc.x, loc.y - 1); 136 break; 137 case EOR: 138 Pop(&Path); 139 break; 140 default: 141 printf("Shit Happened! Check your code!\n"); 142 break; 143 } 144 } 145 Print(); 146 DestroyStack(&Path); 147 return 0; 148 }

?

最后運行結果如圖

有一行多出來的1，因為打印的是走過的路徑。

?

*如果你想自己更改迷宮地圖的話，請務必記得更改相應的起點和終點（114行）

轉載于:https://www.cnblogs.com/makejeffer/p/4811500.html

總結

以上是生活随笔為你收集整理的数据结构应用实例#栈#迷宫寻路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。