6

所以我一直在阅读 K&R C 的书并且有一个问题.. 在第 6 章第 140-141 页的结构中，有看起来像这样的代码（我去掉了一些更不相关的部分）

/*
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只有malloc当它是NULL时root才会传递，即第一次传递的时候。在以后的调用中它不会改变root，只会修改count，left或者right。请注意，在递归addNode调用p中不传递，而是传递它的左或右孩子。试着用纸和铅笔/钢笔穿过树，你会意识到节点是如何被添加的。

于 2011-07-03T07:39:43.353 回答
3

您的误解在于addNode. 它不返回指向新添加节点的指针；相反，它返回一个指向传入节点的指针p（除非是NULL）。

因为唯一的时间root == NULL是添加第一个单词时，从那一刻起root将具有相同的值，并且一遍又一遍地被分配这个相同的值。这只是处理由NULL指针表示的空树的一种优雅方式。

但是请记住，对于 的每个递归调用addNode都有不同的值p。这就是局部变量的工作方式；它们是函数的特定调用的局部变量，而不是整个函数的局部变量。也许这导致您对函数的行为产生误解。

于 2011-07-03T07:38:40.867 回答