AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2023-10-23 138
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】迷宫问题DFS非递归（c语言实现）

本来之前写过一个推箱子，就想着写个迷宫游戏，因为想着推箱子游戏里面也有墙，也有玩家的移动，比推箱子简单的是还不用判断前面是否有箱子的情况，但是自己写的迷宫游戏如果自己随机生成的迷宫地图的话，不一定会有通路，他要学一个什么随机迷宫的生成，刚看完懒猫老师的那个迷宫问题使用的是非递归DFS寻找迷宫是否有通路，用的是非递归DFS实现，然后随机迷宫生成用的是DFS递归写的，我真的要成两半了，今天分享给大家的是DFS算法找迷宫是否有出路，这个好像有的会作为数据结构的大作业还是啥的，用c语言实现，参考b站懒猫老师的课迷宫问题

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.编译运行

文章标签：
C语言
定位技术
算法
关键词：
C语言数据结构
数据结构c语言
数据结构dfs
数据结构递归
数据结构迷宫
嘎嘎旺
目录
相关文章
XIAZHI
|
2月前
|
机器学习/深度学习 算法 C语言
【趣学C语言和数据结构100例】11-15
本文介绍了五个C语言编程问题及其实现，包括矩阵对角线元素之和、有序数组插入、数组逆序、杨辉三角输出和魔方阵生成。每个问题不仅涉及基本的数组操作，还涵盖了算法设计的核心思想，如循环、条件判断和递归。通过解决这些问题，读者可以加深对C语言和数据结构的理解，提升编程技能。这些问题的解决过程展示了如何有效处理数组和矩阵，以及如何利用算法优化程序性能，为实际应用提供了宝贵的实践经验。
XIAZHI
63 4
【趣学C语言和数据结构100例】11-15
土木林森
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
49 1
XIAZHI
|
2月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
XIAZHI
56 4
XIAZHI
|
2月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景，如直接插入排序适合小规模或基本有序的数据，快速排序则适用于大规模数据集，具有较高的效率。通过学习这些算法，读者可以加深对数据结构和算法设计的理解，提升解决实际问题的能力。
XIAZHI
45 4
XIAZHI
|
2月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现，涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大，且在实际应用中极为广泛，有助于提升编程能力和数据结构理解。
XIAZHI
53 4
XIAZHI
|
2月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现，涵盖二叉树的层次遍历及广度优先搜索（BFS）和深度优先搜索（DFS）的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点；BFS利用队列从源节点逐层遍历图节点，适用于最短路径等问题；DFS通过递归或栈深入图的分支，适合拓扑排序等场景。这些算法是数据结构和算法学习的基础，对提升编程能力和解决实际问题至关重要。
XIAZHI
54 4
XIAZHI
|
2月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现，涵盖链表与二叉树操作，包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法，解决了理论与实际应用中的常见问题，有助于提升编程能力和数据结构理解。
XIAZHI
45 4
XIAZHI
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现，涵盖链表与数组操作，如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例，帮助读者深入理解数据结构与算法设计的核心思想，提升编程技能。
XIAZHI
37 4
XIAZHI
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】51-55
本文介绍了五个关于链表操作的C语言实现案例，包括删除单链表中的重复元素、从两个有序链表中查找公共元素、判断一个链表是否为另一链表的连续子序列、判断循环双链表是否对称及合并两个循环单链表。每个案例都详细解析了算法思路与实现方法，涵盖了链表操作的多种场景，旨在帮助读者深入理解链表数据结构的应用，提升算法设计与编程能力。
XIAZHI
44 4
XIAZHI
|
2月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】16-20
本文精选了五个C语言编程问题，涵盖数组操作、字符串处理等基础领域。包括查找二维数组中的鞍点、折半查找法、统计文章中字符数量、电文解密及字符串连接。每个问题都附有详细的代码实现与分析，旨在帮助读者理解算法逻辑，提升编程技巧。通过这些实践，不仅能锻炼编程能力，还能加深对数据结构和算法的理解，为未来的学习和工作打下坚实基础。
XIAZHI
68 4