递归结构和 malloc()

Question

我有一个递归struct，它是：

typedef struct dict dict;
struct dict {
    dict *children[M];
    list *words[M];
};

这样初始化：

dict *d = malloc(sizeof(dict));
bzero(d, sizeof(dict));

我想知道bzero()在这里到底做了什么，以及我如何malloc()< /code> 对于孩子来说是递归的。

编辑：这就是我希望能够 malloc() children 和 words 的方式：

void dict_insert(dict *d, char *signature, unsigned int current_letter, char *w) {
    int occur;
    occur = (int) signature[current_letter];
    if (current_letter == LAST_LETTER) {
        printf("word found : %s!\n",w);
        list_print(d->words[occur]);
        char *new;
        new = malloc(strlen(w) + 1);
        strcpy(new, w);
        list_append(d->words[occur],new);
        list_print(d->words[occur]);
    }
    else {
        d = d->children[occur];
        dict_insert(d,signature,current_letter+1,w);
    }
}

Answer 1

bzero(3) 将内存初始化为零。相当于使用第二个参数调用 memset(3)为 0。在这种情况下，它将所有成员变量初始化为空指针。 bzero 已被视为已弃用，因此您应该将其替换为 memset；或者，您可以只调用 calloc(3) 而不是malloc，成功后会自动将返回的内存清零。

您不应该使用您编写的两个强制转换中的任何一个 - 在 C 中，void* 指针可以隐式强制转换为任何其他指针类型，并且任何指针类型都可以隐式强制转换为 void *。 malloc 返回一个 void*，因此您可以将其分配给您的 dict *d 变量，而无需进行强制转换。同样，bzero 的第一个参数是 void*，因此您可以直接将您的 d 变量传递给它，而无需进行强制转换。

要理解递归，首先要理解递归。如果您想避免无限分配内存，请确保您有适当的基本情况。

Answer 2

一般来说，当您不确定编译器为您生成什么时，最好使用 printf 来报告结构的大小。在这种情况下，dict的大小应该是2 * M * 指针的大小。在这种情况下，bzero 将用零填充字典。换句话说，children 和 Words 数组的所有 M 个元素都将为零。

为了初始化该结构，我建议创建一个函数，该函数接受一个指向字典的指针并分配每个子项，然后调用自身来初始化它：

void init_dict(dict* d)
{
    int i;
    for (i = 0; i < M; i++)
    {
        d->children[i] = malloc(sizeof(dict));
        init_dict(d->children[i]);

        /* initialize the words elements, too */
    }
}

如果您能明白为什么此代码无法按原样工作，请+1。 （提示：它有一个无限递归错误，需要一个规则来告诉它子树需要多深才能停止递归。）

Answer 3

bzero 只是将内存归零。 bzero(addr, size) 本质上等同于 memset(addr, 0, size)。至于为什么要使用它，从我所看到的大约一半的使用时间来看，这只是因为有人认为将内存归零似乎是一个好主意，尽管它并没有真正完成任何事情。在这种情况下，看起来效果是将一些指针设置为 NULL（尽管为此目的它并不完全可移植）。

要递归分配，您基本上只需跟踪当前深度，并分配子节点，直到达到所需的深度。按此顺序编写一些代码就可以完成这项工作：

void alloc_tree(dict **root, size_t depth) { 
    int i;
    if (depth == 0) {
        (*root) = NULL;
        return;
    }

    (*root) = malloc(sizeof(**root));

    for (i=0; i<M; i++)
        alloc_tree((*root)->children+i, depth-1);       
}

我应该补充一点，我无法想象像这样进行递归分配。在典型情况下，您插入数据，并根据需要分配新节点来保存数据。具体细节将取决于您是否（以及如何）保持树平衡。对于像这样的多路树，使用某些 B 树变体是相当常见的，在这种情况下，我上面给出的代码通常根本不适用——使用 B 树，您可以填充一个节点，当它达到极限时，将其分成两半并将中间项提升到父节点。当新节点到达树的顶部并且根节点已满时，您将分配一个新节点。