当前位置： 代码网 > it编程>编程语言>C/C++ > 【数据结构】迷宫问题DFS非递归（c语言实现）

【数据结构】迷宫问题DFS非递归（c语言实现）

2024年07月31日 • C/C++ •我要评论
迷宫问题

1.问题展示

在这里插入图片描述

2.栈的所有有用的函数

因为要用栈实现，所以我们必须将有关栈的函数全部写出来，我们已经之前写过栈的初始化，等等，，我们将他拷贝过来，或者你们直接去看我那一篇。

//栈的实现
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef struct stack//定义一个栈的结构体变量	
{
	int * a;
	int top; // 栈顶
	int capacity; // 容量
}stack;
void stackinit(stack* ps)
{
	assert(ps);//断言，防止为空指针
	ps->a = null;//所指向的地址为空
	ps->capacity = ps->top = 0;//容量和栈中元素个数均为0
}
void stackpush(stack* ps, int data)
{
	assert(ps);
	if (ps->capacity == ps->top)//如果栈中的元素个数等于栈的容量时考虑扩容，
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果刚开始时都等于0，就先给4个空间大小，后面如果满的话，容量扩大1倍
		 int* newnode = (int*)realloc(ps->a,sizeof(int)* newcapcity);//申请空间，将申请好的空间首地址传给newnode指针
		 assert(newnode);//断言，防止malloc失败
		 ps->a = newnode;//将newnode保存的申请空间的首地址传给ps->a,让ps->a指向创建好的空间
		ps->capacity = newcapcity;//容量大小更新为新容量大小



	}
	ps->a[ps->top] = data;//像存数组一样存数据
	ps->top++;//指向下一个
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int stackempty(stack* ps)
{
	assert(ps);
	return ps->top ==0;//ps->top为栈中元素个数.==0栈中无元素，无元素要返回1， 无元素ps->t0p==0，这个表达式结果是1，返回1;





}
// 出栈
void stackpop(stack* ps)
{
	assert(ps);
	assert(!stackempty(ps));//防止栈内无元素，继续出栈
	ps->top--;
}
// 获取栈顶元素
int stacktop(stack* ps)
{
	assert(ps);
	assert(!stackempty(ps));
	return ps->a[ps->top - 1];//ps->top为栈中元素个数，由于数组下标是从0开始，所以栈顶元素下标为ps->top-1;

}
// 获取栈中有效元素个数
int stacksize(stack* ps)
{
	assert(ps);
	return ps->top;

}
// 销毁栈
void stackdestroy(stack* ps)
{
	assert(ps);
	free(ps->a);//free掉动态申请的内存
	ps->a = null;//防止野指针
	ps->capacity = ps->top = 0;//容量和栈中元素个数置为0



}

但是不能直接用，所以我们必须加以修改，我们会将从入口到出口正确的路径坐标，以及每个坐标对应走向下一个坐标的方向保存在栈里面，由我之前实现的栈中一个元素变为三个元素，栈的实现做出以下改变，int * a，a指针不在指向一个int ，将inta改为proa;pro为结构体类型存放三个元素

typedef struct pro
{
	int x;
	int y;
	int di;




}pro;
typedef struct stack
{
	pro* a;
	int top; // 栈顶
	int capacity; // 容量
}stack;

void stackpush(stack* ps, int data1, int data2, int data3)//入栈
{
	assert(ps);
	
	if (ps->capacity == ps->top)
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		pro* tmp = (pro*)realloc(ps->a, sizeof(pro) * newcapcity);
		if (tmp == null)
		{
			perror("realloc fail");
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapcity;



		}






	}
	ps->a[ps->top].x = data1;
	ps->a[ps->top].y = data2;
	ps->a[ps->top].di = data3;
	ps->top++;







}

由于每层由之前一个元素变为三个元素，所以要修改获取栈顶元素函数，返回栈顶地址，然后通过地址来访问三个元素中的每一个

// 获取栈顶元素
pro* stacktop(stack* ps)
{
	assert(ps);
	assert(!stackempty(ps));
	return ps->a+ps->top-1;

}

3.修改后的栈的实现

typedef struct pro
{
	int x;
	int y;
	int di;




}pro;
typedef struct stack
{
	pro* a;
	int top; // 栈顶
	int capacity; // 容量
}stack;
void stackinit(stack* ps)//初始化栈
{
	ps->a = null;
	ps->top = 0;
	ps->capacity = 0;
}
void stackpush(stack* ps, int data1, int data2, int data3)//入栈
{
	assert(ps);
	//assert(ps->a);
	if (ps->capacity == ps->top)
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		pro* tmp = (pro*)realloc(ps->a, sizeof(pro) * newcapcity);
		if (tmp == null)
		{
			perror("realloc fail");
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapcity;



		}






	}
	ps->a[ps->top].x = data1;
	ps->a[ps->top].y = data2;
	ps->a[ps->top].di = data3;
	ps->top++;







}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int stackempty(stack* ps)
{
	assert(ps);
	return ps->top == 0;



}
// 出栈
void stackpop(stack* ps)
{
	assert(ps);
	assert(!stackempty(ps));
	ps->top--;

}
// 获取栈顶元素
pro* stacktop(stack* ps)
{
	assert(ps);
	assert(!stackempty(ps));
	return ps->a+ps->top-1;

}
// 获取栈中有效元素个数
int stacksize(stack* ps)
{
	assert(ps);
	return ps->top;





}

// 销毁栈
void stackdestroy(stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = null;
	ps->top = ps->capacity = 0;

}

4. 定义二维数组作为迷宫的地图

我们这里将1看做墙，0看做空地可以走的地方，然后迷宫入口坐标为（1,1），我们定义二维数组为m*n的

#define n 10
#define m 10

迷宫出口坐标为（m-2,n-2）;
定义全局变量，方便使用

int map[m][n] = {
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1},
};

在这里插入图片描述
黑框标注的分别为入口和出口.
在定义一个结构体，表示要走的方向

typedef struct direct 
{
	int conx;
	int cony;

}direct;

在主函数里面定义一个direct类型的数组，数组大小为四，存放上下左右走，坐标的变化，并且将他们赋值

   direct des[4];
	des[0].conx = 1;//向右走
	des[0].cony = 0;
	des[1].conx = -1;//向左走
	des[1].cony = 0;
	des[2].conx = 0;//向下走
	des[2].cony = 1;
	des[3].conx = 0;//向上走
	des[3].cony = -1;

在这里插入图片描述
向哪走就给对应坐标+上什么的，比如说我向右走，x+des[0].conx ,y+des[0].cony;

5.定义一个栈，将其初始化，当用完时候将其销毁

int main()
{
	
	direct des[4];
	des[0].conx = 1;//向右走
	des[0].cony = 0;
	des[1].conx = -1;//向左走
	des[1].cony = 0;
	des[2].conx = 0;//向下走
	des[2].cony = 1;
	des[3].conx = 0;//向上走
	des[3].cony = -1;
	stack st;
	
	stackinit(&st);
	
  
		stackdestroy(&st);
		stackdestroy(&scpy);
	return 0;

}

6. dfs算法寻找迷宫是否有通路

bool  findpath(int map[][n], direct des[], stack* ps)
{
	int line, col;//表示当前位置能走的下一个位置的坐标
	int x, y, di;//表示当前位置的坐标，以及当前位置准备向下一个方向走的方向
	int mapcon[m][n] = { 0 };//为了不修改原有的地图，重新创建一个二维数组
	for (int i = 0; i < m; i++)//遍历地图，将原地图的二维数组的值拷贝到mapcon中
	{
		for (int j = 0; j < n; j++)
		{  
			mapcon[i][j] = map[i][j];
			
		


		}
		
	}
	

	mapcon[1][1] = -1;//走过的地方用-1标记
	pro tmp;//保存当前位置的坐标，以及方向
	tmp.x = 1;
	tmp.y = 1;
	tmp.di = -1;//刚开始在（1,1），将tmp.x，tmp.y赋值为1，刚开始还没有方向tmp.di = -1；
	stackpush(ps, tmp.x, tmp.y, tmp.di);//将当前位置信息压入st栈中

	while (!stackempty(ps))//栈中不为空，开始循环
	{
		tmp.x = stacktop(ps)->x;
		tmp.y = stacktop(ps)->y;
		tmp.di = stacktop(ps)->di;//获取栈顶元素到tmp中去，以便于回退
		stackpop(ps);//出栈操作
		x = tmp.x;//当前坐标改为回退之后的坐标
		y = tmp.y;//当前坐标改为回退之后的坐标
		di = tmp.di + 1;//开始di=0,方向向右
		while (di < 4)//遍历当前位置的四个方向
		{
			line = x + des[di].conx;//记录下一个位置的坐标
			col = y + des[di].cony;//记录下一个位置的坐标
			if (mapcon[line][col] == 0)//如果下一个坐标时0，为空地的话，就可以前进
			{
				tmp.x = x;//保存当前位置坐标，以便于回退
				tmp.y = y;//保存当前位置坐标，以便于回退
				tmp.di = di;//保存当前位置坐标，以便于回退
				stackpush(ps, tmp.x, tmp.y, tmp.di);//当前位置目前确定是通往出口路上的一个坐标，先入栈
				x = line;//当前位置更新为下一个位置的坐标
				y = col;//当前位置更新为下一个位置的坐标
				mapcon[line][col] = -1;//留下足迹，标记为-1；
				if (x == m - 2 && y == n - 2)//是否到出口
				
					

					return true;//有通路，跳出
				
				
				else di = 0;//没到的话，将方向更新为向右
			}
			else di++;//如果当前位置的方向不是空地的话，就换另一个方向判断


		}



	}

	return false;//循环结束，无通路

}

7. 逆序打印坐标

如果有通路的话， findpath（）函数返回1，由于栈是先入后出，所以栈顶元素是出口的坐标，怎么逆序打印从入口到出口的坐标呢？我们可以在创建一个栈，使用栈判空函数循环将st中的元素入栈到另一个栈中，就做到了在原先栈底元素，跑到了新栈的栈顶，实现了逆序打印
在这里插入图片描述

	stack st;
	stack scpy;//定义一个栈用于倒翻数据
	stackinit(&st);
	stackinit(&scpy);//新栈初始话
    bool ret = findpath(map, des, &st);//返回1，地图有通路
		if (ret == 1)
		{
			printf("该地图有通路\n");
			while (!stackempty(&st))//原栈不为空的话
			{
				int num1=stacktop(&st)->x;
				int num2 = stacktop(&st)->y;
				int num3= stacktop(&st)->di;//获取旧栈栈顶元素
				/*printf("%d-%d ",num1,num2);*/
				stackpop(&st);//栈顶元素出st栈
				stackpush(&scpy, num1, num2, num3);//栈顶元素入新栈scpy


			}
			
			
			while (!stackempty(&scpy))//新栈scpy不为空，
			{
				int num1 = stacktop(&scpy)->x;
				int num2 = stacktop(&scpy)->y;
				int num3 = stacktop(&scpy)->di;//获取栈顶元素
				printf("(%d,%d)\n", num1, num2);//打印栈顶元素
				stackpop(&scpy);//新栈栈顶元素出栈
			

			}
			
		}
		else
		{

			printf("该地图无通路\n");
		}
		stackdestroy(&st);//销毁旧栈
		stackdestroy(&scpy);//销毁新栈

只打印坐标，不要求方向，我就在栈中没画方向.

8.整体代码

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>


#include <stdbool.h>
#define n 10
#define m 10
int map[m][n] = {
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,1,1},
	{1,0,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1},
};
typedef struct pro
{
	int x;
	int y;
	int di;




}pro;
typedef struct direct 
{
	int conx;
	int cony;

}direct;






typedef struct stack
{
	pro* a;
	int top; // 栈顶
	int capacity; // 容量
}stack;
void stackinit(stack* ps)//初始化栈
{
	ps->a = null;
	ps->top = 0;
	ps->capacity = 0;
}
void stackpush(stack* ps, int data1, int data2, int data3)//入栈
{
	assert(ps);
	//assert(ps->a);
	if (ps->capacity == ps->top)
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		pro* tmp = (pro*)realloc(ps->a, sizeof(pro) * newcapcity);
		if (tmp == null)
		{
			perror("realloc fail");
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapcity;



		}






	}
	ps->a[ps->top].x = data1;
	ps->a[ps->top].y = data2;
	ps->a[ps->top].di = data3;
	ps->top++;







}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int stackempty(stack* ps)
{
	assert(ps);
	return ps->top == 0;



}
// 出栈
void stackpop(stack* ps)
{
	assert(ps);
	assert(!stackempty(ps));
	ps->top--;

}
// 获取栈顶元素
pro* stacktop(stack* ps)
{
	assert(ps);
	assert(!stackempty(ps));
	return ps->a+ps->top-1;

}
// 获取栈中有效元素个数
int stacksize(stack* ps)
{
	assert(ps);
	return ps->top;





}

// 销毁栈
void stackdestroy(stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = null;
	ps->top = ps->capacity = 0;

}
enum  mine
{
	space,  //空地
	wall,//墙
	dest,  //目的地
	player//玩家





};
bool  findpath(int map[][n], direct des[], stack* ps)
{
	int line, col;
	int x, y, di;
	int mapcon[m][n] = { 0 };
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{  
			mapcon[i][j] = map[i][j];
			
		


		}
		
	}
	mapcon[m - 2][n - 2] = 0;

	mapcon[1][1] = -1;
	pro tmp;
	tmp.x = 1;
	tmp.y = 1;
	tmp.di = -1;
	stackpush(ps, tmp.x, tmp.y, tmp.di);

	while (!stackempty(ps))
	{
		tmp.x = stacktop(ps)->x;
		tmp.y = stacktop(ps)->y;
		tmp.di = stacktop(ps)->di;
		stackpop(ps);
		x = tmp.x;
		y = tmp.y;
		di = tmp.di + 1;
		while (di < 4)
		{
			line = x + des[di].conx;
			col = y + des[di].cony;
			if (mapcon[line][col] == 0)
			{
				tmp.x = x;
				tmp.y = y;
				tmp.di = di;
				stackpush(ps, tmp.x, tmp.y, tmp.di);
				x = line;
				y = col;
				mapcon[line][col] = -1;
				if (x == m - 2 && y == n - 2)
				
					

					return true;
				
				
				else di = 0;
			}
			else di++;


		}



	}

	return false;

}





int main()
{
	srand((unsigned int)time(null));
	direct des[4];
	des[0].conx = 1;//向右走
	des[0].cony = 0;
	des[1].conx = -1;//向左走
	des[1].cony = 0;
	des[2].conx = 0;//向下走
	des[2].cony = 1;
	des[3].conx = 0;//向上走
	des[3].cony = -1;
	stack st;
	stack scpy;
	stackinit(&st);
	stackinit(&scpy);
    bool ret = findpath(map, des, &st);
		if (ret == 1)
		{
			printf("该地图有通路\n");
			while (!stackempty(&st))
			{
				int num1=stacktop(&st)->x;
				int num2 = stacktop(&st)->y;
				int num3= stacktop(&st)->di;
				/*printf("%d-%d ",num1,num2);*/
				stackpop(&st);
				stackpush(&scpy, num1, num2, num3);


			}
			
			
			while (!stackempty(&scpy))
			{
				int num1 = stacktop(&scpy)->x;
				int num2 = stacktop(&scpy)->y;
				int num3 = stacktop(&scpy)->di;
				printf("(%d,%d)\n", num1, num2);
				stackpop(&scpy);
			

			}
			
		}
		else
		{

			printf("该地图无通路\n");
		}
		stackdestroy(&st);
		stackdestroy(&scpy);
	return 0;

}

9.编译运行

在这里插入图片描述

赞 (0)

相关文章:

版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站仅提供信息存储服务，不拥有所有权，不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 2386932994@qq.com 举报，一经查实将立刻删除。

发表评论

验证码：
最近更新的文章
推荐阅读
大家感兴趣的文章
Copyright © 2017-2025  代码网 保留所有权利. 粤ICP备2024248653号
站长QQ:2386932994 | 联系邮箱：2386932994@qq.com