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)メモリをゼロに初期化します。It's equal to calling memset(3)with a second parameter of 0. この場合、すべてのメンバー変数を null ポインターに初期化します。 は非推奨と見なされるため、その使用を;bzeroに置き換える必要があります。または、代わりに をmemset呼び出すこともできます。これは、成功時に返されたメモリを自動的にゼロにします。calloc(3)malloc

作成した 2 つのキャストのいずれも使用しないでください。C では、void*ポインターを他のポインター型に暗黙的にキャストでき、任意のポインター型を に暗黙的にキャストできますvoid*。 mallocを返すので、キャストせずに変数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 ツリー バリアントを使用するのがかなり一般的です。その場合、上記のコードは通常まったく適用されません。B ツリーでは、ノードを埋めます。制限に達したら、それを半分に分割し、中間のアイテムを親ノードに昇格させます。これがツリーの最上部に達し、ルート ノードがすでにいっぱいになったら、新しいノードを割り当てます。

于 2011-11-27T18:34:20.713 に答える
1

一般に、コンパイラが何を生成しているのか不明な場合は、printf を使用して構造体のサイズを報告することをお勧めします。この場合、dict のサイズは 2 * M * ポインターのサイズにする必要があります。この場合、bzero は dict をゼロで埋めます。つまり、children 配列と words 配列のすべての 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 に答える