c - C 中的二叉搜索树出现奇怪的故障

Question

我的程序从文件中读取行并用它构建树。从我的 main 中，我调用函数 loadFromFile，它完成了所有工作。此函数调用 insert 方法，该方法又调用该函数来比较字符串。这是使用的结构:

typedef struct Node {
    char *key;
    int count;
    struct Node *left, *right;
} node;

这是 loadFromFile 函数，它有两个参数，第一个参数是读取数据所需的文件地址，第二个参数是比较字符串的模式。您会注意到，我稍后使用 printf 向您展示输出:

node * loadFromFile(char * address, int mode){

    FILE * file;
    char * line_readed;
    size_t len = 0;
    ssize_t read;
    node * new_node;
    node * tmp = NULL;

    file = fopen(address, "r");
    if (file == NULL){
        printf("File \"%s\" doesn't exist.\n", address);
        exit(EXIT_FAILURE);
    }

    while ((read = getline(&line_readed, &len, file)) != -1) {
        new_node = get_node();
        line_readed[strlen(line_readed)-1] = 0;
        new_node->key = line_readed;
        printf("line readed: %s\n", line_readed);
        if(tmp != NULL){
            printf("- tmp->key: %s \n", tmp->key);
            tmp = insert(tmp, new_node, mode);
        }else{
            tmp = new_node;
            printf("- tmp->key: %s \n", tmp->key);
        }
    }

    fclose(file);
    printBST(tmp);
    return tmp;
}

要创建一个新节点，需要使用函数get_node()，其代码如下:

node * get_node() {
    node *temp;
    temp = (node *) malloc(sizeof(node));
    temp -> left = NULL;
    temp -> right = NULL;
    temp -> count = 1;
    return temp;
}

插入的代码是这样的:

node * insert(node *root, node *new_node, int mode) {
    int comparison;
    if(mode){
        comparison = my_strcmp(new_node->key, root->key);
        if (comparison == -1){
            if (root->left == NULL){
                root->left = new_node;
            }else
                insert(root->left, new_node, mode);
        }
        else if (comparison == 1)
            if (root->right == NULL){
                root->right = new_node;
            }else
                insert(root->right, new_node, mode);
        else{
            root->count++;
        }
    }else{
        comparison = my_strignorecasecmp(new_node->key, root->key);   
        if (comparison == -1){
            if (root->left == NULL){
                root->left = new_node;
            }else
                insert(root->left, new_node, mode);
        }
        else if (comparison == 1)
            if (root->right == NULL){
                root->right = new_node;
            }else
                insert(root->right, new_node, mode);
        else{
            root->count++;
        }
    }   
    return root;
}

最后但并非最不重要的一点是打印 BST 的代码:

void printBST(node * root){
    if(root != NULL){
        printBST(root->left);
        printf("%s\n",root->key);
        printBST(root->right);
    }
}

输出如下:

line readed: asddassdfgsdfgdfghx
- tmp->key: asddassdfgsdfgdfghx  
line readed: bb
- tmp->key: bb 
line readed: adassss
- tmp->key: adassss 
line readed: zasx
- tmp->key: zasx 
line readed: www
- tmp->key: www 
www

我独立检查了比较字符串函数，它们工作得很好，所以我假设问题与指针有关，但我看不出在哪里，或者如何修复它。变量 tmp 应该是根，它获取了我正在阅读的行的所有值，但我不明白为什么；也许因为我来自JAVA，这些东西对我来说有点不同。我认为问题不在于 insert 也不在于 printBST。

Answer 1

您的问题归结为您对 getline() 的使用:

getline() 查看传入的双指针，并检查该地址是否有足够的空间(由 len 参数指示)来存储下一行。如果您传入 NULL 指针(的地址)或者当前缓冲区没有足够的空间容纳下一行，它会自动尝试分配(更多)内存。

但是，在您的代码中，line_readed 从未被赋值:

char *line_readed;

此时line_readed是一个未定义的指针，它可能指向任何地方。任何对该指针值的使用都是未定义的行为。

现在您在此指针上调用getline()。 getline() 将(可能我们不知道)非 NULL 未定义 line_readed 解释为指向 malloc()ed 内存的指针剩余容量为零(因为len == 0)。

因此它在未定义的指针上调用realloc()。

所有的赌注都从这里开始。您在 UB 国家/地区。

然而，可能发生的是，getline()为line_readed分配新内存(然后释放旧指针，导致未定义的行为)。

需要注意的是，如果有足够的空间，getline() 首先会尝试写入您传入的地址。由于您的第一个键相当长，因此在初始(不正确)realloc()之后，缓冲区可能永远不需要调整大小。

如果您仔细观察，这也意味着您的所有 node->key 引用将仅指向同一内存位置，该位置也会被新数据重复覆盖。

如果您在循环中打印 line_readed 的地址，它可能会在第一次迭代时发生变化，之后就不会发生变化。

你可以尝试一下

new_node->key = strdup(line_readed);

这会将字符串从 line_readed 复制到新的内存位置，并将该新地址填充到 new_node->key 中。

您还需要初始化

char *line_readed = NULL;

也可以在创建每个节点后重置 len = 0; 和 line_readed = NULL;，其作用几乎相同但避免了字符串复制。

另外:不要忘记您需要显式手动释放每个分配的内存块。没有垃圾收集。这包括最后的 free(line_readed);，释放每个节点和每个节点的 key (如果已分配)。