通过使用 sscanf 提取数据在 BST 插入函数中传递参数

Question

我正在编写一个程序，它从文本文件（逐行）中读取学生（id、姓名、姓氏、年级），然后使用 id 作为键将它们存储到二叉搜索树中。要阅读每一行，我使用 fgets() 并从该行中提取单词使用 sscanf().

struct TreeNode* root = NULL;
FILE *text;
char *id, *onoma, *epitheto, *word, *line;
onoma = (char *)malloc(20 * sizeof(char));
epitheto = (char *)malloc(30 * sizeof(char));
id = (char *)malloc(9 * sizeof(char));
float vathmos;

text = fopen("students.txt", "r");
if (text == NULL) {
    printf("Cannot read from the file!");
    exit(1);
}

这是为每个学生提取数据的循环：

while (fgets(line, 50, text) != NULL) {
    printf("%d \n", root);
    sscanf(line, "%s %s %s %f", id, onoma, epitheto, &vathmos);
    printf("%s  %s  %s  %.3f \n", id, onoma, epitheto, vathmos);
    root = Insert(root, id);
}

这是节点的插入函数：

TreeNode *Insert(struct TreeNode* root, char *data) {
    if (root == NULL) { // empty tree
        root = CreateNewNode(data);
    }
    // if data to be inserted is lesser, insert in left subtree.
    else if ((strcmp(data, root->id)) <= 0) {
        root->left = Insert(root->left,data);
    }
    // else, insert in right subtree.
    else if ((strcmp(data, root->id)) > 0) {
        root->right = Insert(root->right,data);
    }
    return root;
}

当我插入节点时 "by hand" 例如：

root = Insert(root, "AY881159");
root = Insert(root, "AA564510");
root = Insert(root, "AB784123");

程序运行，节点已创建，树可以被操作。

但是当通过从 sscanf() 获取数据在 fgets() 循环中创建树时，就会出现问题。虽然变量正确存储了数据（这就是为什么我在 sscanf() 之后有 printf() 来检查这一点），但 root 似乎已重置并且只有最后一个学生保留在树中。

有什么想法吗？

节点的代码是：

typedef struct TreeNode {
    char *id;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

和

TreeNode *CreateNewNode(char *data) {
    struct TreeNode *NewNode = (TreeNode *)malloc(sizeof(TreeNode));
    NewNode->id = data;
    NewNode->left = NewNode->right = NULL;
    return NewNode;
}

Answer 1

您 post 编写的代码无法编译，这使得回答问题变得更加困难。

您从同一个 id 缓冲区创建循环中的所有节点。您需要制作缓冲区的副本，无论是在调用 Insert 还是最好在 CreateNewnode() 函数中。您没有 post 代码，也没有 post 类型 TreeNode 的定义。这是一种可能性：

TreeNode *CreatNewNode(const char *data) {
    TreeNode *node = calloc(1, sizeof(*node));
    if (node != NULL) {
        node->id = strdup(data);
        node->left = node->right = NULL;
    }
    return node;
}

不需要为解析阶段分配数组，本地 char 数组对此很好，但是存储到树中的数据应该被复制，这样您就可以重用解析代码中的缓冲区.使 Insert 的参数成为 const char *data 以指示缓冲区不会被修改，也不会在调用后由树拥有。

您必须将额外信息传递给 scanf 以防止缓冲区溢出。

这里是调用代码的修改版本：

int main(void) {
    struct TreeNode *root = NULL;
    FILE *text;
    char id[9], onoma[20], epitheto[30], line[256];
    float vathmos;

    text = fopen("students.txt", "r");
    if (text == NULL) {
        printf("Cannot read from the file!");
        exit(1);
    }

    // This is the loop where the data are extracted for each student:
    while (fgets(line, sizeof line, text) != NULL) {
        printf("%d \n", root);
        if (sscanf(line, "%8s %19s %29s %f", id, onoma, epitheto, &vathmos) == 4) {
            printf("%s  %s  %s  %.3f \n", id, onoma, epitheto, vathmos);
            root = Insert(root, id);
        } else {
            printf("invalid line: %s", line);
        }
        // I'm curious how you are going to store the other data...
    }
    ...
}

Insert函数可以简化为：

TreeNode *Insert(struct TreeNode *root, const char *data) {
    if (root == NULL) { // empty tree
        root = CreateNewNode(data);
    } else {
        if (strcmp(data, root->id) <= 0) {
            // if data to be inserted is lesser or equal, insert in left subtree.
            root->left = Insert(root->left, data);
        } else {
            // else insert in the right subtree
            root->right = Insert(root->right, data);
        }
    }
    return root;
}

对于 InsertNode 更好的 API 将采用指向 root 指针的指针和 return 指向新节点的指针：

TreeNode *Insert(struct TreeNode **nodep, const char *data) {
     while (*nodep != NULL) {
        if (strcmp(data, (*nodep)->id) <= 0) {
            nodep = &(*nodep)->left;
        } else {
            nodep = &(*nodep)->right;
        }
    }
    return *nodep = CreateNewNode(data);
}

通过使用 sscanf 提取数据在 BST 插入函数中传递参数

Passing arguments in a BST insert function by extracting data using sscanf

c

scanf

fgets

binary-search-tree