使用fgets读取文件中的行到二叉搜索树

Question

当前我试图将我的文件中的每个单独的行存储到一个字符串中，然后将其存储在二叉搜索树中，但会出现问题。出于某种原因，当我打印我的BST时，只输出最后一行，而不是前三行。下面是我的代码。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 


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

struct node *newNode(char* item) 
{ 
    struct node* temp = (struct node*)malloc(sizeof(struct node)); 
    temp->key = item; 
    temp->left = NULL; 
    temp->right = NULL; 
    temp->count = 1; 
    return temp; 
}; 

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

struct node* insert(struct node* node, char* key) 
{ 
    if(node == NULL)//When tree is empty 
     return newNode(key); 
    if(strcmp(key, node->key) < 0) 
     node->left = insert(node->left, key); 
    if(strcmp(key, node->key) > 0) 
     node->right = insert(node->right, key); 

    return node; 

}; 


int main() 
{ 

    struct node *root = NULL; 


    int i = 0; 
    char str[100]; 
    FILE* fp; 
    fp = fopen("textFile.txt", "r"); 
    if ((fp = fopen("textFile.txt","r")) == NULL) 
    { 
     printf("Could not open textFile.txt\n"); 
     exit(1); 
    } 

    while(fgets(str, 100, fp) != NULL) 
    { 
     ++i; 
     root = insert(root, str); 
     printf("%3d: %s", i, str); 

    } 


    printf("bst printed\n"); 
    printInorder(root); 

    return 0; 
} 

TextFile.txt的包含

bob is working. 
david is a new hire. 
alice is bob's boss. 
charles doesn't like bob. 

而当BST被印刷，其输出是最后一个 查尔斯不喜欢鲍勃唯一线。

任何帮助真的不胜感激。

Answer 1

注意，当您创建newNode一个节点，存储传递给它的指针的的副本，而不是字符串拷贝正指向。这意味着每次向树中插入一个值时，它都会在main中存储一个指向str缓冲区的指针。换句话说，你做你的第一次插入后，事情是这样的：

+------------+ 
| BST Node |       str 
+------------+   +---+---+---+---+---+...+---+ 
| key  | ---------> | b | o | b | | i | | 0 | 
+------------+   +---+---+---+---+---+...+---+ 

当你再读取该文件的下一行，你覆盖str与该行的内容，所以画面看起来像这样：

+------------+ 
| BST Node |       str 
+------------+   +---+---+---+---+---+...+---+ 
| key  | ---------> | d | a | v | i | d | | 0 | 
+------------+   +---+---+---+---+---+...+---+ 

请注意，您的BST现任虽然它包含“大卫是一个新员工”，即使你从来没有插入该值。因此，当您尝试在BST中插入“大卫是新雇员”时，没有任何反应。

同样的事情发生在未来数读取，直到最后你读文件的最后一行时，事情是这样的：

+------------+ 
| BST Node |       str 
+------------+   +---+---+---+---+---+...+---+ 
| key  | ---------> | c | h | a | r | l | | 0 | 
+------------+   +---+---+---+---+---+...+---+ 

这就是为什么你只看到查理线最后 - BST正在引导您访问缓冲区的单个共享副本。

为了解决这个问题，让BST存储传递给它的字符串的副本，或者在将它们存储在树中之前复制字符串。例如，你可能有newNode函数调用strdup，以获得自己的字符串拷贝到店：

struct node *newNode(char* item) 
{ 
    struct node* temp = (struct node*)malloc(sizeof(struct node)); 
    temp->key = strdup(item); // <--- here! 
    /* TODO: Error-handling! */ 
    temp->left = NULL; 
    temp->right = NULL; 
    temp->count = 1; 
    return temp; 
}; 

这应该解决您的问题。只要确保在完成后即可释放所有内容！