个人中心
gpt4 book ai didi

使用堆栈标记连接的组件

转载 作者：行者123 更新时间：2023-11-30 21:42:26 25 4
gpt4 key购买 nike

我刚刚通过递归编码了连通分量标记但我想要通过使用堆栈和结构的非递归版本。

typedef struct _node{
int Xpos;
int Ypos;
int dir;    
}node;

node *stack[MAX];
node *push(node *t) {
stack[++top] = t;
return t;
}

node *pop() {
return stack[top--];
    }

结构组件确实有 X 位置、Y 位置和方向。前任)if(t->dir == 1) {t->Xpos =++t->Xpos, t->Ypos = --t->Ypos};8-邻居标记我真的需要帮助!//编辑

//编辑这是我通过递归所做的

#define MAP_SIZE 15
#define INILBCNT    10
int cnt = 1;
int input_map[MAP_SIZE][MAP_SIZE] =
{ {0,0,0,0,0,0,0,0,0,0,0,0,1,1,0},
{0,1,1,1,1,1,1,0,0,0,0,0,1,1,0},
{0,1,0,0,0,0,1,0,0,0,1,1,0,1,0},
{0,1,0,1,1,0,1,0,1,1,1,0,0,1,0},
{0,1,0,0,1,0,1,0,1,0,0,0,0,1,0},
{0,1,1,0,1,0,1,0,1,0,0,1,0,1,0},
{0,0,0,1,1,0,1,0,1,0,1,1,0,1,0},
{0,1,0,1,1,0,1,0,1,0,1,0,0,1,0},
{0,1,0,0,0,0,0,0,1,0,1,0,0,1,0},
{0,1,0,0,0,0,0,1,1,0,1,0,0,1,0},
{0,1,1,1,1,1,0,1,0,0,1,1,0,1,0},
{0,0,0,0,0,1,0,1,0,1,0,0,0,1,0},
{0,1,1,1,0,1,0,1,0,0,0,0,0,1,0},
{0,1,0,0,0,1,0,1,1,1,1,1,1,1,0},
{0,1,1,1,1,1,0,0,0,0,0,0,0,1,0}
};



void PrintMap()
{
system("cls");

for (int j = 0; j < MAP_SIZE; j++)
{
    for (int i = 0; i < MAP_SIZE; i++)
    {
        printf("%d ", input_map[j][i]);
    }
    printf("\n");   }  }

void glassFire(int mask_Y, int mask_X)
{

if (input_map[mask_Y][mask_X] != 1)
    return;
else
    if (input_map[mask_Y][mask_X] == 1)
    {
        input_map[mask_Y][mask_X] = cnt;            
        glassFire(mask_Y, mask_X + 1);
        glassFire(mask_Y + 1, mask_X);
        glassFire(mask_Y + 1, mask_X + 1);
        glassFire(mask_Y + 1, mask_X - 1);
        glassFire(mask_Y - 1, mask_X + 1);
        glassFire(mask_Y - 1, mask_X);
        glassFire(mask_Y - 1, mask_X + 1);
        glassFire(mask_Y, mask_X - 1); }}

void Serching()
{
PrintMap();
for (int i = 0; i < MAP_SIZE; i++)
{
    for (int j = 0; j < MAP_SIZE; j++)
    {

        if (input_map[j][i] == 1)
        {
            cnt++;
            glassFire(j, i);}
      }
   }
}

这段代码运行良好。

最佳答案

This code just worked well.

不，此代码具有未定义的行为，因为您在 input_map 中读取/写入 mask_Y 和/或 mask_X 值为 -1 和/或15 因为递归调用向 mask_Y/mask_X

添加/删除 1

在

void glassFire(int mask_Y, int mask_X)
{
  if (input_map[mask_Y][mask_X] != 1)
    return;
  else
    if (input_map[mask_Y][mask_X] == 1)
    {
        ...
    }
}

第一个if没用，但你必须检查索引，可以是:

void glassFire(int mask_Y, int mask_X)
{
   if ((mask_Y >= 0) && (mask_X >= 0) &&
       (mask_Y < MAP_SIZE) && (mask_X < MAP_SIZE) &&
       (input_map[mask_Y][mask_X] == 1))
   {
        ...
   }
}

您调用两次 glassFire(mask_Y - 1, mask_X + 1);，其中一次必须替换为 glassFire(mask_Y - 1, mask_X - 1);，其中丢失了。

而不是去做

   glassFire(mask_Y, mask_X + 1);
   glassFire(mask_Y + 1, mask_X);
   glassFire(mask_Y + 1, mask_X + 1);
   glassFire(mask_Y + 1, mask_X - 1);
   glassFire(mask_Y - 1, mask_X + 1);
   glassFire(mask_Y - 1, mask_X);
   glassFire(mask_Y - 1, mask_X - 1); /*  modified */
   glassFire(mask_Y, mask_X - 1); }}

您可以使用循环(这将有助于手动管理递归，更改更少的代码):

    static const YX offset[] = {
      {0,1}, {1,0}, {1,1}, {1,-1}, {-1,1}, {-1,0}, {-1,-1}, {0,-1}
    };

    for (int dir = 0; dir != 8; ++dir) 
      glassFire(mask_Y + offset[dir].y, mask_X + offset[dir].x);

with typedef struct YX { int y;整数x； } YX;

<小时/>

要删除递归调用，您包含方向的结构是不合适的，因为递归调用可以执行其他递归调用等，您只需保存稍后需要管理的索引即可。

幸运的是，请注意结果并不取决于递归调用的顺序。

解决方案可以是:

void glassFire(int mask_Y, int mask_X)
{
  YX * stack = NULL;
  size_t sz = 0;
  size_t deep = 0;

  for (;;) {
    if (input_map[mask_Y][mask_X] == 1) /* need to check, can be false now */
    {
      input_map[mask_Y][mask_X] = cnt;

      static const YX offset[] = {
        {0,1},  {1,0},  {1,1}, {1,-1}, {-1,1}, {-1,0}, {-1,-1},  {0,-1}
      };

      /* up to 8 positions to save */
      if ((deep + 8) > sz) {
        sz += 8;
        stack = realloc(stack, sz * sizeof(YX));
      }

      for (int dir = 0; dir != 8; ++dir) {
        int ny = mask_Y + offset[dir].y;
        int nx = mask_X + offset[dir].x;

        if ((ny >= 0) && (nx >= 0) &&
            (ny < MAP_SIZE) && (nx < MAP_SIZE) &&
            (input_map[ny][nx] == 1))
        {
          stack[deep].y = ny;
          stack[deep].x = nx;
          deep += 1;
        }
      }
    }

    if (deep == 0)
      /* empty */
      break;

    deep -= 1;
    mask_Y = stack[deep].y;
    mask_X = stack[deep].x;
  }

  free(stack);
}
<小时/>

如果我使用完整的程序(我删除了无用的INILBCN):

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

#define MAP_SIZE 15
int cnt = 1;
int input_map[MAP_SIZE][MAP_SIZE] =
{ {0,0,0,0,0,0,0,0,0,0,0,0,1,1,0},
{0,1,1,1,1,1,1,0,0,0,0,0,1,1,0},
{0,1,0,0,0,0,1,0,0,0,1,1,0,1,0},
{0,1,0,1,1,0,1,0,1,1,1,0,0,1,0},
{0,1,0,0,1,0,1,0,1,0,0,0,0,1,0},
{0,1,1,0,1,0,1,0,1,0,0,1,0,1,0},
{0,0,0,1,1,0,1,0,1,0,1,1,0,1,0},
{0,1,0,1,1,0,1,0,1,0,1,0,0,1,0},
{0,1,0,0,0,0,0,0,1,0,1,0,0,1,0},
{0,1,0,0,0,0,0,1,1,0,1,0,0,1,0},
{0,1,1,1,1,1,0,1,0,0,1,1,0,1,0},
{0,0,0,0,0,1,0,1,0,1,0,0,0,1,0},
{0,1,1,1,0,1,0,1,0,0,0,0,0,1,0},
{0,1,0,0,0,1,0,1,1,1,1,1,1,1,0},
{0,1,1,1,1,1,0,0,0,0,0,0,0,1,0}
};

void PrintMap()
{
  for (int j = 0; j < MAP_SIZE; j++)
  {
    for (int i = 0; i < MAP_SIZE; i++)
    {
        printf("%d ", input_map[j][i]);
    }
    putchar('\n');
  }
}

typedef struct YX { int y; int x; } YX;

void glassFire(int mask_Y, int mask_X)
{
  YX * stack = NULL;
  size_t sz = 0;
  size_t deep = 0;

  for (;;) {
    if (input_map[mask_Y][mask_X] == 1)
    {
      input_map[mask_Y][mask_X] = cnt;

      static const YX offset[] = {
        {0,1},  {1,0},  {1,1}, {1,-1}, {-1,1}, {-1,0}, {-1,-1},  {0,-1}
      };

      /* 8 positions to save */
      if ((deep + 8) > sz) {
        sz += 8;
        stack = realloc(stack, sz * sizeof(YX));
      }

      for (int dir = 0; dir != 8; ++dir) {
        int ny = mask_Y + offset[dir].y;
        int nx = mask_X + offset[dir].x;

        if ((ny >= 0) && (nx >= 0) &&
            (ny < MAP_SIZE) && (nx < MAP_SIZE) &&
            (input_map[ny][nx] == 1))
        {
          stack[deep].y = ny;
          stack[deep].x = nx;
          deep += 1;
        }
      }
    }

    if (deep == 0)
      /* empty */
      break;

    deep -= 1;
    mask_Y = stack[deep].y;
    mask_X = stack[deep].x;
  }

  free(stack);
}

void Serching() /* probably searching */
{
  PrintMap();

  for (int i = 0; i < MAP_SIZE; i++)
  {
    for (int j = 0; j < MAP_SIZE; j++)
    {
        if (input_map[j][i] == 1)
        {
          cnt++;
          glassFire(j, i);}
      }
   }
}

int main()
{
  Serching();
  putchar('\n');
  PrintMap();
}

编译与执行:

pi@raspberrypi:~ $ gcc -pedantic -Wall -Wextra c.c
pi@raspberrypi:~ $ ./a.out
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 
0 1 1 1 1 1 1 0 0 0 0 0 1 1 0 
0 1 0 0 0 0 1 0 0 0 1 1 0 1 0 
0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 
0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 
0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 
0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 
0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 
0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 
0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 
0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 
0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 
0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 
0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 

0 0 0 0 0 0 0 0 0 0 0 0 4 4 0 
0 2 2 2 2 2 2 0 0 0 0 0 4 4 0 
0 2 0 0 0 0 2 0 0 0 4 4 0 4 0 
0 2 0 2 2 0 2 0 4 4 4 0 0 4 0 
0 2 0 0 2 0 2 0 4 0 0 0 0 4 0 
0 2 2 0 2 0 2 0 4 0 0 5 0 4 0 
0 0 0 2 2 0 2 0 4 0 5 5 0 4 0 
0 3 0 2 2 0 2 0 4 0 5 0 0 4 0 
0 3 0 0 0 0 0 0 4 0 5 0 0 4 0 
0 3 0 0 0 0 0 4 4 0 5 0 0 4 0 
0 3 3 3 3 3 0 4 0 0 5 5 0 4 0 
0 0 0 0 0 3 0 4 0 5 0 0 0 4 0 
0 3 3 3 0 3 0 4 0 0 0 0 0 4 0 
0 3 0 0 0 3 0 4 4 4 4 4 4 4 0 
0 3 3 3 3 3 0 0 0 0 0 0 0 4 0

我让 cnt 和 input_map 全局化，但它们可以在 Serching 中本地化，并在 glassFire 的参数中给出>。全局变量越少越好。

请注意，我的代码产生与您相同的结果(以修正为模)，但我不知道您的代码是否正确，因为我不知道它真正需要做什么;-)

关于使用堆栈标记连接的组件，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55709947/

25 4 0
文章推荐： c# - NopCommerce、C#、MVC、Elastic Search 多个参数
文章推荐： c - 用C从文件中读取字符和字符串
文章推荐： c# - 正则表达式从 GMT 字符串中提取时间
文章推荐： c - 无法理解的指针错误
行者123
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com