欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之利用栈寻路(深度优先搜索)

程序员文章站 2022-07-14 19:30:01
...

写完了栈的两种实现方式的博客,我们来看利用栈来寻路:
栈的特性适合来存储路径坐标,并且撞墙后可以以栈的弹顶元素来实现回退功能,所以用栈来实现这个算法,我这里运用的是深度优先搜索思想了(虽然我没有特别明显的dfs函数,大佬请不要喷,本菜面对的是新手)
首先我们绘迷宫肯定是二维数组实现了,但是存储这个点就需要结构体了所以我们来封装一下:

struct point {
	int x;
	int y;
};

接下来用栈来存储路径

struct point path[100];//存放路径
int stacktop = -1;//栈顶标记

接下来为二维数组分配空间:

int** map = NULL;//二维数组
int size = 0;//迷宫大小
struct point here = {1,1};//当前位置
int** makemap(int x, int y) {
	int** array = (int**)malloc(sizeof(int*)*x);
	for (int i = 0; i < y; i++) {
		array[i] = (int*)malloc(sizeof(int)*x);
	}
	return array;
}

创建地图,让用户来输入:

void createmap() {
	printf("输入一个迷宫大小:");
	scanf("%d", &size);
	map = makemap(size + 2, size + 2);//加2表示外边框
	printf("输入迷宫");
	for (int i = 1; i <= size; i++) {
		for (int j = 1; j <= size; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	//加边框,1表示边框
	for (int i = 0; i <= size + 1; i++) {
		map[0][i] = map[size + 1][i] = 1;//上下的墙
		map[i][0] = map[i][size + 1] = 1;//左右的墙
	}
}

这里的边框大家可以画画图来理解一下

接下来是重头戏,寻找路径:

bool findpath() {
	//移动的属性描述出来
	struct point fx[4];//方向
	//右
	fx[0].x = 0;
	fx[0].y = 1;
	//下
	fx[1].x = 1;
	fx[1].y = 0;
	//左
	fx[2].x = 0;
	fx[2].y = 1;
	//上
	fx[3].x = 0;
	fx[3].y = 1;
	map[1][1] = 1;
	int next = 0;//下一个移动方向
	int end = 3;//结束方向
	while (here.x != size || here.y != size) {
		int xnum, ynum;//记录下标变化;
		while (next <= end) {
			//行列的变化=原位置+偏移值 偏移值由移动方向确定
			xnum = here.x + fx[next].x;
			ynum = here.x + fx[next].y;
			//一旦确定一个方向能走,就需要下一步
			//不能移动测试
			if (map[xnum][ynum] == 0) {
				break;//退出循环走一遍
			}
			next++;
		}
		//可以移动
		if (next <= end) {
			//走到下一个
			path[++stacktop] = here;
			//改变当前位置
			here.x = xnum;
			here.y = ynum;
			map[xnum][ynum] = 1;
			next = 0;//起始方向置为零;
		}
		else {//大于等于四的方向,就是该点已经没有走的地方了
			//回到上一步去;
			if (stacktop != -1) {
				return 0;
			}
			struct point nx = path[stacktop];
			stacktop--;//出栈的方式回退一步;
			//方向的处理
			//处理原因是为了效率,因为重置的话就是回退一下又要全判断一下,何
			//不必看一下上一步的碰壁情况来判断上一步的下一步要干什么呢?
			if (nx.x == here.x) {//行没改变
				next = 2 + nx.y - here.y;
			}
			else {
				next = 3 + nx.x - here.x;
			}
			here = nx;//回到上一步
		}
	}
	return true;
}

回退的功能就是利用栈的出栈来实现的
接下来是结束后打印路径:

void printpath(){
	printf("路径方式:\n");
	struct point curPos;
	while (stacktop != -1) {
		curPos = path[stacktop];
		stacktop--;
		printf("(%d,%d)", curPos.x, curPos.y);
	}
	printf("\n");

}

以下主函数:

int main() {
	createmap();
	if (findpath()) {
		printpath();
	}
	else {
		printf("没有路径\n");
	}
	return 0;
}

现在的输出结果是倒着来的,想一想为什么?
答案是,出栈是先进后出
下面是整体的程序(其中有错误,欢迎大佬指正):

#include<stdio.h>
#include<stdlib.h>
struct point {
	int x;
	int y;
};
struct point path[100];//存放路径
int stacktop = -1;//栈顶标记
int** map = NULL;//二维数组
int size = 0;//迷宫大小
struct point here = {1,1};//当前位置
int** makemap(int x, int y) {
	int** array = (int**)malloc(sizeof(int*)*x);
	for (int i = 0; i < y; i++) {
		array[i] = (int*)malloc(sizeof(int)*x);
	}
	return array;
}
void createmap() {
	printf("输入一个迷宫大小:");
	scanf("%d", &size);
	map = makemap(size + 2, size + 2);//加2表示外边框
	printf("输入迷宫");
	for (int i = 1; i <= size; i++) {
		for (int j = 1; j <= size; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	//加边框,1表示边框
	for (int i = 0; i <= size + 1; i++) {
		map[0][i] = map[size + 1][i] = 1;//上下的墙
		map[i][0] = map[i][size + 1] = 1;//左右的墙
	}
}
bool findpath() {
	//移动的属性描述出来
	struct point fx[4];//方向
	//右
	fx[0].x = 0;
	fx[0].y = 1;
	//下
	fx[1].x = 1;
	fx[1].y = 0;
	//左
	fx[2].x = 0;
	fx[2].y = 1;
	//上
	fx[3].x = 0;
	fx[3].y = 1;
	map[1][1] = 1;
	int next = 0;//下一个移动方向
	int end = 3;//结束方向
	while (here.x != size || here.y != size) {
		int xnum, ynum;//记录下标变化;
		while (next <= end) {
			//行列的变化=原位置+偏移值 偏移值由移动方向确定
			xnum = here.x + fx[next].x;
			ynum = here.x + fx[next].y;
			//一旦确定一个方向能走,就需要下一步
			//不能移动测试
			if (map[xnum][ynum] == 0) {
				break;//退出循环走一遍
			}
			next++;
		}
		//可以移动
		if (next <= end) {
			//走到下一个
			path[++stacktop] = here;
			//改变当前位置
			here.x = xnum;
			here.y = ynum;
			map[xnum][ynum] = 1;
			next = 0;//起始方向置为零;
		}
		else {//大于等于四的方向,就是该点已经没有走的地方了
			//回到上一步去;
			if (stacktop != -1) {
				return 0;
			}
			struct point nx = path[stacktop];
			stacktop--;//出栈的方式回退一步;
			//方向的处理
			//处理原因是为了效率,因为重置的话就是回退一下又要全判断一下,何
			//不必看一下上一步的碰壁情况来判断上一步的下一步要干什么呢?
			if (nx.x == here.x) {//行没改变
				next = 2 + nx.y - here.y;
			}
			else {
				next = 3 + nx.x - here.x;
			}
			here = nx;//回到上一步
		}
	}
	return true;
}
void printpath(){
	printf("路径方式:\n");
	struct point curPos;
	while (stacktop != -1) {
		curPos = path[stacktop];
		stacktop--;
		printf("(%d,%d)", curPos.x, curPos.y);
	}
	printf("\n");

}
int main() {
	createmap();
	if (findpath()) {
		printpath();
	}
	else {
		printf("没有路径\n");
	}
	return 0;
}

好了,栈的内容我就写完了,下一站是队列。