6

K&R C の本を読んでいて、質問があります。140 ～ 141 ページの構造体に関する第 6 章に、次のようなコードがあります (関連のない部分をいくつか削除しました)。

/*
the program loops through a tree looking for some word
if it finds the word itll incremenet the count by 1 
if it doesnt itll add a new node
*/

 struct node {
    char *word;
    int count;
    struct node *left;
    struct node *right;
}

 main() {
    struct node *root;
    char word[1000];

    root = NULL;
    while(getword(word, MAXWORD) != EOF) /* getword just grabs 1 word at a time from a file of words */
        if(isalpha(word[0])) /* isalpha checks to see if it is a valid word */
            root = addNode(root, word);

    treeprint(root); /* prints the tree */
    return 0;
}

struct node *addNode(struct node *p, char *w) {
    int cond;

    if(p == NULL) {
        p = malloc(sizeof(struct node)); /* allocates memory for the new node */
        p -> word = strdup(w);
        p -> count = 1;
        p -> left = p -> right = NULL;
    }

    else if ((cond = strcmp(w, p -> word)) == 0)
        p -> count++;

    else if(cond < 0)
        p -> left = addNode(p -> left, w);

    else
        p -> right = addNode(p -> right, w);

    return p;
}

そして、私の混乱は root = addNode(root, word) の main() 関数にあります

addNode が新しく追加されたノード (または、既にツリー内にある場合は単語が存在するノード) へのポインターを返す場合、ツリーの上のすべてのデータが「失われる」のではないでしょうか? ルートはツリーのルートのままであるべきではありませんか?

ありがとう！

4

2 に答える 2

5

root常にツリーのルートとして残ります。rootが最初のパラメータとして渡されるのは、それが である場合addNodeのみです。つまり、が初めて渡された場合です。後の呼び出しでは、変更されず、変更されるか、または. 再帰呼び出しでは渡されないことに注意してください。むしろ、左または右の子が渡されます。紙と鉛筆/ペンでツリーを調べてみると、ノードがどのように追加されているかがわかります。mallocNULLrootrootcountleftrightaddNodep

于 2011-07-03T07:39:43.353 に答える
3

あなたの誤解は の振る舞いにありaddNodeます。新しく追加されたノードへのポインターは返しません。むしろ、渡されたノードへのポインターを返しますp(それが でない場合NULL)。

root == NULL最初の単語が追加されたときだけrootが、その時点から同じ値になり、同じ値が何度も割り当てられます。NULLこれは、ポインターで表される空のツリーを処理するエレガントな方法です。

ただし、の再帰呼び出しごとにの値がaddNode異なることpに注意してください。これがローカル変数の仕組みです。それらは、関数全体ではなく、関数の特定の呼び出しに対してローカルです。たぶん、これが関数の動作についての誤解につながったのでしょう。

于 2011-07-03T07:38:40.867 に答える