c-递归结构和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()。

编辑：这就是我希望能够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)将内存初始化为零。这相当于用第二个参数0调用memset(3)。在这种情况下，它将所有成员变量初始化为空指针。bzero被认为是不推荐使用的，所以您应该用memset替换它的使用；或者，您可以只调用calloc(3)而不是malloc，它会在成功后自动将返回的内存清零。

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

要理解递归，必须首先理解递归。如果你想避免无限分配内存，请确保你有一个合适的基本情况。

Answer 2

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

为了初始化结构，我建议创建一个函数，该函数将一个指向dict的指针和mallocs每个子对象，然后调用自己来初始化它：

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只是将内存归零。CCD_ 22与CCD_。至于你为什么要使用它，据我所见，大约有一半的时间使用它，这只是因为有人认为将记忆归零似乎是个好主意，尽管它并没有真正起到任何作用。在这种情况下，效果似乎是将一些指针设置为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树，填充一个节点，当它达到极限时，将其一分为二，并将中间项提升到父节点。当这个节点到达树的顶部，并且根节点已经满时，就可以分配一个新节点。