无法让我的插入函数在字母二叉字符串树中工作

Question

我正在尝试构建一个二叉树，它将按字母顺序保存文件中的单词，并计算文件中单词出现的次数。然后我必须能够替换原始文本文件中的单词。现在我只是尝试设置我的二叉树并将单词放入其中。字符串标记有效，它将打印每行的单词和标点符号。我还必须将标点符号存储在字符数组中并计算其出现次数。我的插入功能遇到问题，但我不确定我做错了什么。我遇到段错误。

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

/*
Name: Marcus Lorenzana
*/

//binary tree struct to hold left and right node
//as well as the word and number of occurrences
typedef struct node
{
    char* word;
    int count;
    struct node *left;
    struct node *right;
}
node;

node *insert(node *item, char *word);
char* readFile(char* filename);

int main()
{
    FILE *fin;
    char *word;
    fin = fopen("data.txt", "r");


    char* filecontents = readFile("data.txt");

    //create dictionary node
    node *dictionary; 
    dictionary = NULL;

    //read words and punctuation in from the text file
    word = strtok (filecontents, " \n");
    int i = 0;
    while (word != NULL)
    {

        printf("%s\n",word);
        insert(dictionary,word);
        printf("%s",dictionary->word); 
        word = strtok (NULL, " \n");
        i++;
    }




    return 0;
}

//not sure if works
node *insert(node *item, char *word)
{
    if(item==NULL)
    {
        item= (node*) malloc(sizeof(node));
        strcpy(item->word, word);
        item->left=NULL;
        item->right=NULL;
        item->count++;
    }
    else
    {
        if(strcmp(word, item->word)<0)
        {
            item->left=insert(item->left, word); 
            item->count++;
        }
        else if(strcmp(word, item->word)>0)
        {
            item->right=insert(item->right, word);
            item->count++;
        }
        else
        {
            item->count++;
        }
    }
    return item;
}


char* readFile(char* filename)
{
    FILE* file = fopen(filename,"r");
    if(file == NULL)
    {
        return NULL;
    }

    fseek(file, 0, SEEK_END);
    long int size = ftell(file);
    rewind(file);

    char* content = calloc(size + 1, 1);

    fread(content,1,size,file);

    return content;
}

Answer 1

您的 insert 函数存在两个问题。

1. 如果您打算改变指针，则应将双指针传递给结构节点，否则，如果您打算改变，则应在每次递归调用时返回使用指向结构节点的单个指针。
2. 创建新节点时，您不会为单词malloc内存。

要查找代码其他部分的问题，请使用 valgrind ( here )。它是调试内存泄漏或段错误的绝佳工具。

<小时/>

为了解决问题 1，我将展示传递单个指针并返回的示例(仍在变化)。您的插入函数(问题 2 已解决)应如下所示:

node *insert( node *item, char *word ) {
  if ( item == NULL ) {
    node *new_item = malloc( sizeof( struct node ) );

    new_item->word = malloc( sizeof( char ) * ( strlen( word ) + 1 ) ); // Note, this line (p2).

    strcpy( new_item->word, word );

    new_item->count = 1; // << Note change here.
    new_item->left = NULL;
    new_item->right = NULL;

    return new_item;
  } else {
    int cmp_result = strcmp( word, item->word );

    if ( cmp_result < 0 ) {
      item->left = insert( item->left, word );
      item->count++;
    } else if ( cmp_result > 0 ) {
      item->right = insert( item->right, word );
      item->count++;
    } else { 
      // Node already exists, do what you see fit here.
    }
  }

  return item;
}

为了解决问题 2，错误位于创建新节点的代码块中。看这里:

item = ( node* )malloc( sizeof( node ) );
strcpy( item->word, word ); // << Here, invalid (error).

...您没有为该字malloc内存块。您正在做的是覆盖结构内的内存，并可能覆盖您尚未分配的其他内存地址(取决于垃圾值何时为 0 以模拟 NULL 终止符)。这是未定义的行为。

解决方案是执行以下操作:

item = ( node* ) malloc( sizeof( node ) );
item->word = malloc( sizeof( char ) * ( strlen( word ) + 1 ) ); // << Fix.
strcpy( item->word, word ); // << Now, valid.

...注意 + 1 以确保有 NULL 终止符的空间，因为 strlen 返回数组的字符串长度传递给它的字符数。

备注:

• 强制转换 malloc 的结果也不是一个好主意，但这完全取决于您，因为它不会导致错误(但可能会在出现错误时不显示错误消息)应该)。
• 同样重要的是，您的 main 函数具有 void 参数类型，main( void ) 而不是 main( ) ，除非您打算使用该功能。