使用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; 
}; 

這應該解決您的問題。只要確保在完成後即可釋放所有內容！