c - 将项目插入树时程序崩溃

Question

我是 C 编程新手，正在编写一个带有树的程序。用户提供字符串输入，程序将这些字符串拆分为单词并将这些单词插入树中。当这些单词之一等于“eoi”时，程序停止。当我给出第一个输入时， v->item (实际上这是 root->item)被正确打印。但是当我给出第二个输入时， v->item 的值错误(它不再具有 root->item 值，而是新输入的值)。

这是我的代码:

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

typedef struct treeNode TreeNode;

typedef struct treeNode {
  char* item;
  TreeNode *left;
  TreeNode *right;
  int freq;

  int rank; 
} TreeNode;

TreeNode* insertItem(TreeNode *root, char* x);

int main(int argc, char** argv) {

    TreeNode *root = NULL;

    char str[100];

    printf("Enter input text : ");
    gets(str);
    printf("Input : %s\n", str);  
    char *tok;
    tok = strtok(str, " ");
    int i,j;
    i = j = 1;

    while((strcmp(tok, "eoi") != 0))
    {           
        printf("%d %s\n", i, tok);          
        i++;
        root = insertItem(root, tok);
        tok = strtok (NULL, " ");       
        while(tok != NULL)
        {
            if(strcmp(tok, "eoi") != 0)
            {
                printf("%d %s\n", i, tok);
                i++;
                root = insertItem(root, tok);
            } 
            else
            {
                j = 0;
                break;
            }  
            tok = strtok (NULL, " ");
        }
        if(j == 0)
        {
            break;
        }
        gets(str);
        printf("Input : %s\n", str);  
        tok = strtok(str, " ");
        i = 1;      
    }   


    return (EXIT_SUCCESS);
}

TreeNode* insertItem(TreeNode *root, char* x) {  

   TreeNode *tmp;
   TreeNode *v = root;  
   TreeNode *pv = NULL; 
   while (v != NULL) {  
      pv = v; 
      printf("v->item : %s\n",v->item);
      if (strcmp(x, v->item) < 0) v=v->left;
      else if (strcmp(x, v->item) > 0) v=v->right;
           else { 
                  printf("%s already exists.\n", x);
                  tmp->freq++;
          return root;
           }   
   }

   tmp = (TreeNode *)malloc((strlen(x) + 1) * sizeof(TreeNode));
   tmp->item=x; tmp->left=tmp->right=NULL;
   tmp->freq = 1;
   if (root != NULL) { 
      if (strcmp(x, pv->item) < 0) pv->left=tmp;
         else pv->right=tmp;
   } else root=tmp;
   printf("root->item: %s", root->item);
   return root; 
}

例如，一开始使用输入:一二 现在 v-> 项是 1 然后输入:五六 v->item 是 5 但 i 应该是 1 然后程序崩溃了。

有人可以帮我解决这个问题吗？

Answer 1

问题是缓冲区的重用char str[100];在main() ，以及未初始化指针 tmp 的取消引用在insertItem() :

在 main() , gets() (您绝对永远不应该使用)填充 char str[100] -buffer 与第一个输入，然后您就地标记缓冲区，因此 str现在包含

"one\0two\0[garbage]" .

您将标记插入树中，效果很好，因为两个字符串比较不相等。但是，当您读取下一个输入时，缓冲区将被重用。标记化后，str包含

"five\0six\0[garbage]" ,

现有树节点中的指针指向此缓冲区! 特别地，第一个树节点有 char *item指向"five\0" ，所以strcmp()比较 equal，正如我的评论中指出的，它取消引用 tmp在insertItem()在初始化之前。

您可能实际上并不想分配 tmp = (TreeNode *)malloc((strlen(x) + 1) * sizeof(TreeNode));在insertItem() ，而是

tmp = malloc(sizeof(*tmp)); // == sizeof(TreeNode)
tmp->item = strdup(x); // or tmp->item = malloc(strlen(x)+1); strcpy(tmp->item, x);