3

我对c很陌生，所以如果我的步骤有误，请告诉我。假设我有以下内容：

struct graphNode{
    int val;
    graphNode* parent;
    int succSize;
    int succMaxSize;
    graphNode* succ[1];
};

我将创建一个新节点：

graphNode *n;
n = malloc(sizeof(struct graphNode));
assert(n);
n->val = 1;
n->parent = NULL;
n->succSize = 0;
n->succMaxSize = 1;

然后，如果我想为节点添加后继者

if (n->succSize == n->succMaxSize){
    n->succ = realloc(n->succ, sizeof(graphNode*) * n->succMaxSize * 2);
    n->succMaxSize *= 2;
} 
n->succ[succSize] = n2; //n2 is of type graphNode*
succSize++;

这个对吗？我是否也需要为结构重新分配，或者数组的重新分配是否足够？我需要为初始数组分配 malloc 吗？初始数组大小是否应该包含在我对 n 的 malloc 调用中？

4

5 回答 5

7

在 C 中定义“可拉伸”数组成员的常用方法是指定大小0或根本不指定大小，例如：

struct foo {
    int stuff;
    bar theBars[]; // or theBars[0]
};

有了这个定义，最后sizeof(struct foo)会包含除数组之外的所有元素，你可以通过说 . 来分配正确的大小malloc(sizeof(struct foo) + numberOfBars * sizeof(bar))。

如果您需要重新分配它以更改bar元素的数量，那么您将使用相同的公式（但使用新的numberOfBars）。

需要明确的是，您不能只是realloc结构的一部分。你必须realloc整件事。

于 2013-10-17T22:09:15.303 回答
1

realloc(ptr,size)需要 2 个参数，而不是 1 中使用的realloc(sizeof(graphNode*) * n->succMaxSize * 2)

// Something like ...
graphNode *n;
n->succSize = 0;
n->succMaxSize = 0; // set to 0
n->succ = NULL;  // Initialize to NULL

// Then, if OP wants to add a successor to the node
if (n->succSize <= n->succMaxSize){
  n->succ = realloc(n->succ, sizeof(graphNode*) * n->succMaxSize * 2);
  n->succMaxSize *= 2;
} 
n->succ[succSize++] = n2;

与所有内存分配一样，检查NULL返回。在realloc()中，应该保存原始值，因此如果realloc()失败，原始指针不会丢失。

于 2013-10-17T22:36:06.787 回答
1

通常，当您看到结构定义的最后一个字段是大小为 0 或 1 的数组时，这意味着作者将在分配结构时使用 malloc 做一些微妙的事情。

例如

struct foo {
   int x;
   :
   : 
   type a[0];
};

使用 malloc 之类的

  struct foo *p = malloc(sizeof(*p) + (n * sizeof(type));

它的作用是为结构和尾随数组分配一块连续的内存。在这种情况下，数组大小为 n。所以在这种情况下对数组的引用是：

p->a[i] // where i >= 0 and i < n

这样做的一个原因是为了节省内存。

我确信在 StackOver 上有更好的解释；这是一个非常常见的 C 习语。

当数组是动态的时，通常不使用它。相反，当在 malloc() 时知道数组大小时使用它。当然，您可以动态使用，但您必须重新分配整个内存块，而不仅仅是结构或数组本身。要将大小增加到 2n 你会说

  p = realloc(p, sizeof(*p) + (2 * n * sizeof(type)));

现在你的数组是原来的两倍，它仍然是一块内存。

于 2013-10-17T22:38:56.977 回答
0

如果您只想要一个数组，只需创建succ一个指针并仅使用 malloc/realloc 等为数组分配内存。

graphNode* succ;

你正在做的事情几乎肯定会失败。

于 2013-10-17T22:03:01.413 回答
0

我也是 C 的新手，但有些东西我可以立即看到。首先，您不能重新分配数组。在 c89 中，它们是编译时固定大小的。在 C99 和 C11 中，它们可以动态分配，但不能重新分配（据我所知）。因此，为此，您需要分配一个

graphnode *succ;

指针和 malloc(nodes * sizeof(node))。

graphNode* succ[1];

这将创建一个大小为 1 的数组，而不是最大索引为 1 的数组。因此，它在功能上（几乎）与

graphNode* succ;

只是一旦你做了就不能改变它的大小。

我认为您想要的是制作一棵树，具有可动态重新分配数量的分支。在这种情况下，您只需要重新分配 graphNode* 指针的大小，然后像访问数组一样通过索引访问每个元素。

于 2013-10-17T22:06:00.810 回答