1

我有一个递归struct，它是：

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

以这种方式初始化：

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

我想知道bzero()这里到底做了什么，我怎样才能malloc()为孩子们递归。

编辑：这就是我希望能够malloc()和：childrenwords

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);
    }
}
4

3 回答 3

2

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

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

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

于 2011-11-27T18:24:19.107 回答
1

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-tree 变体是相当普遍的，在这种情况下，我上面给出的代码通常根本不适用——使用 B-tree，你填充一个节点，当它达到极限时，你将它分成两半并将中间项目提升到父节点。当它到达树的顶部时，您分配一个新节点，并且根节点已经满了。

于 2011-11-27T18:34:20.713 回答
1

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

要初始化结构，我建议创建一个函数，该函数接受一个指向 dict 的指针并对每个孩子进行 malloc，然后调用自身来初始化它：

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。（提示：它有一个无限递归错误，需要一个规则来告诉它子树需要多深才能停止递归。）

于 2011-11-27T18:34:57.187 回答