c - C. 递归插入中的 Trie 工作不当

Question

下面是我的递归函数的实现，用于将单词插入到 trie 中并搜索它。问题在于插入效果不佳。例如，当将单词“on”传递给 SearchWord() 时，我返回“Found”，但对于任何其他单词，它是“NotFound”。我知道 main() 末尾应该有 free() 内存，但首先我想关注插入的正确实现。有人可以查看代码，特别是通过 InsertIntoTrie() 函数并向我解释其失败的原因吗？我想问题出在这个函数上。

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

//declaration of struct TrieNode
typedef struct TrieNode
{
    struct TrieNode* Children[27];
    bool endOfWord;
}
TrieNode;

//declaration of Root
TrieNode* Root = NULL;

//Recursive inserting word into the trie
void InsertIntoTrie(TrieNode* current, char* word, int index)
{
    if(index == strlen(word))
    {
        current -> endOfWord = true;
        return;
    }
    int ch = ((word[index] == '\'') ? 26 : (word[index] - 97));
    //printf("%d\n", ch);
    if(current -> Children[ch] == NULL)
    {
        current -> Children[ch] = (TrieNode*) malloc(sizeof(TrieNode));
        current = current -> Children[ch];
    }
    InsertIntoTrie(current, word, index + 1);
}

void InsertWord(char* word)
{   
    Root = (TrieNode*) malloc(sizeof(TrieNode));
    InsertIntoTrie(Root, word, 0);
}

//Recursive search into trie
bool SearchIntoTrie(TrieNode* current, char* word, int index)
{
    if (index == strlen(word))
    {
        return current -> endOfWord;
    }
    int ch = ((word[index] == '\'') ? 26 : (tolower(word[index]) - 97));
    //printf("search[%d] = %d\n", index, ch);
    current = current -> Children[ch];
    if (current == NULL)
    {
        return false;
    }
    //printf("search[%d] = %d\n", index, ch);
    return SearchIntoTrie(current, word, index + 1);
}


bool SearchWord(char* word)
{
    return SearchIntoTrie(Root, word, 0);
}

int main(void)
{
    //File declaration for testing
    FILE *fp;
    fp = fopen ("file.txt", "w+");
    fputs("alice\nwas\nbeg''inning\nto\nget\nvery\ntired\nof\nsitting\nby\nher\nsister\non\n", fp);
    rewind(fp);

    char word[LENGTH + 1];
    while(fscanf(fp, "%s", word) != EOF)
    {
        InsertWord(word);
        //printf("next word\n");
    }

    SearchWord("was") ? printf("Found\n") : printf("NotFound\n");
    fclose(fp);
}

Answer 1

您的“InsertWord”函数在每次调用时都会分配一个新的 TrieNode。正如评论中所建议的，您还需要初始化内存:

Root = (TrieNode*) malloc(sizeof(TrieNode));

应该是:

if(Root == NULL)
    Root = (TrieNode*) calloc(1, sizeof(TrieNode));