当我们不知道开始时的确切大小时，如何避免重新分配指针数组

Question

我正在尝试设计一个类似数据结构的二叉树，除了每个节点可以拥有的子节点没有限制。现在，在每个节点中，我可以这样声明节点结构：

struct node {
  int id;
  int num_children;
  struct node ** child;
};

我的问题是有没有办法避免使用：

1. 在这种情况下进行realloc，以便在释放和重新分配时不会在内存中产生大量碎片？每次我添加一个新孩子都需要经历这个过程
2. 在数组中静态分配有限数量的指针，这意味着（a）在某个点我将无法添加到它＆（b）某些节点不会有子节点，所以这是一种浪费

Answer 1

首先分配固定数量的子指针，并添加一个成员来存储列表的当前容量。当您向列表添加子项时，如果列表是容量，则大小加倍。这最大限度地减少了您需要进行的重新分配的数量。

因此节点被修改为如下所示：

struct node {
  int id;
  int capacity;
  int num_children;
  struct node ** child;
};

创建节点：

struct node newnode = malloc(sizeof *newnode);
newnode->num_children = 0;
newnode->capacity = 10;
newnode->child = malloc(sizeof *newnode->child * newnode->capacity);

要在容量满时添加孩子：

if (current->capacity == current->num_children) {
    current->capacity *= 2;
    current->child = realloc(current->child , sizeof *current->child * newnode->capacity);
}
current->child[current->num_children++] = new_child;

注意：为简洁起见，省略了错误检查。