C语言数据结构----栈实现迷宫

https://blog.csdn.net/qq_43079376/article/details/89337578

#include <stdio.h> #define MAX 30 typedef struct { int x; int y; int di; }Box; typedef struct { int top; Box data[MAX]; }Stack; int map[10][10]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; int search(int beginX,int beginY,int endX,int endY) { int i,j,k,di,find; Stack s; s.top = -1; s.top++; s.data[s.top].x = beginX; s.data[s.top].y = beginY; s.data[s.top].di = -1; map[beginX][beginY]=-1; while (s.top>-1) { i = s.data[s.top].x; j = s.data[s.top].y; di = s.data[s.top].di; //结束,输出结果 if (i == endX&&j == endY) { printf("迷宫路径如下:\n"); for (k = 0; k < s.top; ++k) { if ((k+1)%5!=0) { printf("(%d,%d)\t",s.data[k].x,s.data[k].y); } else { printf("\n"); } } return 1; } find = 0; while (di<4&&find==0) { di++; switch (di) { //西 case 0: i = s.data[s.top].x-1; j = s.data[s.top].y; break; //南 case 1: i = s.data[s.top].x; j = s.data[s.top].y+1; break; //东 case 2: i = s.data[s.top].x+1; j = s.data[s.top].y; break; //北 case 3: i = s.data[s.top].x; j = s.data[s.top].y-1; break; } if (map[i][j] == 0) { find = 1; } } if (find == 1) { s.data[s.top].di = di; s.top++; s.data[s.top].x = i; s.data[s.top].y = j; s.data[s.top].di = -1; map[i][j] = -1; } else { map[s.data[s.top].x][s.data[s.top].y] = 0; s.top --; } } return 0; } int main() { if(!search(1,1,8,8)) { printf("NO"); } return 0; }

以上就是源码部分，接下来我将一步一步解读里面的每一个步骤：

栈的结构设计如下：

typedef struct { int x; //二维数组的行 int y; //二维数组的列 int di;//假如退栈时记录了上次在该点走过的方向 }Box; typedef struct { Box data[MAX];//存储走过的路径的行列 int top;//记录栈顶，后期回溯方便弹出 }

地图(二维数组)：

int map[10][10]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} };

迷宫的核心代码：

int search(int beginX,int beginY,int endX,int endY) { int i,j,k,di,find; Stack s; s.top = -1; s.top++; s.data[s.top].x = beginX; s.data[s.top].y = beginY; s.data[s.top].di = -1; map[beginX][beginY]=-1; while (s.top>-1) { i = s.data[s.top].x; j = s.data[s.top].y; di = s.data[s.top].di; //结束,输出结果 if (i == endX&&j == endY) { printf("迷宫路径如下:\n"); for (k = 0; k < s.top; ++k) { if ((k+1)%5!=0) { printf("(%d,%d)\t",s.data[k].x,s.data[k].y); } else { printf("\n"); } } return 1; } find = 0; while (di<4&&find==0) { di++; switch (di) { //西 case 0: i = s.data[s.top].x-1; j = s.data[s.top].y; break; //南 case 1: i = s.data[s.top].x; j = s.data[s.top].y+1; break; //东 case 2: i = s.data[s.top].x+1; j = s.data[s.top].y; break; //北 case 3: i = s.data[s.top].x; j = s.data[s.top].y-1; break; } if (map[i][j] == 0) { find = 1; } } if (find == 1) { s.data[s.top].di = di; s.top++; s.data[s.top].x = i; s.data[s.top].y = j; s.data[s.top].di = -1; map[i][j] = -1; } else { map[s.data[s.top].x][s.data[s.top].y] = 0; s.top --; } } return 0; }

第一段：

Stack s; s.top = -1; s.top++; //将起点放入栈中 s.data[s.top].x = beginX; s.data[s.top].y = beginY; s.data[s.top].di = -1;//还未选择方向，所以赋值为-1 map[beginX][beginY]=-1; //map为地图 //因为起点是我们走过的第一个点 //所以我们将他赋值为-1，后面所有走过的点都赋值为-1

将起点放入栈中，初始化栈。

第二段：

while (s.top>-1)

while循环的条件，有一种情况没有路径，所以这一点是为了判断是否能出去，倘若连起点都被栈弹出了，栈为空，就代表没有路径。

该函数会返回0，代表无法行走。

第三段：

i = s.data[s.top].x; j = s.data[s.top].y; di = s.data[s.top].di;

将栈顶元素的行列和存储下一个方向的变量di赋值给普通变量。

第四段：

//结束,输出结果 if (i == endX&&j == endY) { printf("迷宫路径如下:\n"); for (k = 0; k < s.top; ++k) { if ((k+1)%5!=0) { printf("(%d,%d)\t",s.data[k].x,s.data[k].y); } else { printf("\n"); } } return 1; }

将栈中的数据打印，结束的标志就是栈顶存储的点和出口点一样。

第五段：

find = 0; while (di<4&&find==0)//判断是否找到该点的方向 { di++;//每次循环+1 switch (di) { //西 case 0: i = s.data[s.top].x-1; j = s.data[s.top].y; break; //南 case 1: i = s.data[s.top].x; j = s.data[s.top].y+1; break; //东 case 2: i = s.data[s.top].x+1; j = s.data[s.top].y; break; //北 case 3: i = s.data[s.top].x; j = s.data[s.top].y-1; break; } //如果是可走的find赋值为1 if (map[i][j] == 0) { find = 1; } }

第六段：

if (find == 1)//可走就入栈 { s.data[s.top].di = di; s.top++; s.data[s.top].x = i; s.data[s.top].y = j; s.data[s.top].di = -1; map[i][j] = -1; } else {//不行就出栈 map[s.data[s.top].x][s.data[s.top].y] = 0; s.top --; }

第七段：

int main() { //主函数 //输入起点和终点 if(!search(1,1,8,8)) { printf("NO"); } return 0; }