Trie 实现逻辑错误？

Question

我目前正在开发一个 trie 实现：

从文本文件中读取单词
逐个字符遍历该单词
将该字符的字母索引编号附加到新节点并将其附加到根节点

我在执行第 3 步时遇到问题。

你看，第三步我要做的是：

如果需要的话创建一个新节点（如果需要的节点已经存在，跳过第2步）
将该新节点附加到 root 的子数组，它附加到扫描字符字母索引的位置 e.g.如果要扫描 "a"，新节点将附加到 root->children[a 的字母索引
移动到根中的下一个节点，以便下一个节点将附加到该节点

为了进一步缩小问题的范围，第 2 个第 3 个和第 4 个问题我仍在努力弄清楚。

对于第二步，我目前尝试的是：

if(root->children[index] == NULL) root->children[index] = makeNewNode();

假设 root 和 index 以及 makeNewNode() 已经定义，它将新节点初始化为 NULL

第三步，我做了：

root = root->children[index];

设置 root 使其成为下一个节点

我在这些陈述中是否犯了任何逻辑错误？

trie 节点结构和根声明

typedef struct trieNode
{
    bool endOfWord;
    // 27 not 26 because an apostrophe also counts as a character
    struct trieNode *children[27];

} trieNode;

//Make a new node function prototype.
trieNode* makeNewNode();

trieNode *root;

加载函数

bool load(const char *dictionary)
{
    // open dictionary file
    FILE *file = fopen(dictionary, "r");

    // check if file opened successfully
    if(file == NULL)
    {
        fprintf(stderr, "Can't open file.\n");
        unload();
        return false;
    }

    // initialize root
    root = makeNewNode();

    char word[LENGTH + 1];
    int index = 0;

    // load a word in line by line
    while(fscanf(file, "%s", word) != EOF)
    {
        printf("Word loaded %s\n", word);

        // scan loaded word character by character
        for(int i = 0; i < strlen(word); i++)
        {
            // remove any capital letters
            if(isalpha(word[i]) && isupper(word[i])) tolower(word[i]);

            // set current character in word to it's alphabetical index (apostrphes index is 26)
            index = word[i] - 'a';
            if(word[i] == '\'') index = 26;

            printf("Char being searched %c Index %i\n", word[i], index);

            // if character does not exist, create a new node and point root to it
            if(root->children[index] == NULL) root->children[index] = makeNewNode();

            // move to next node
            root = root->children[index];

            printf("Children's value: %p\n", (void *) root->children[index]);
        }
    // indicate leaf or end of branch
    root->endOfWord = true;
}

// close dictionary
fclose(file);

return true;
}

makeNewNode 函数

// function to automate initialization of nodes
trieNode* makeNewNode()
{
    // give some space for the new node
    struct trieNode* newNode = malloc(sizeof(trieNode));

    newNode->endOfWord = false;

    // initialize all children pointers to NULL.
    for (int i = 0; i < 27; i++) newNode->children[i] = NULL;

    return newNode;
}

Answer 1

 if(root->children[index] == NULL) root->children[index] = makeNewNode();

            // move to next node
            root = root->children[index];

您为下一个 word 修改 root here.So，root 将不是真正的根节点，而是 inserted.You 需要数据的最后一个节点保持原根。

Trie 实现逻辑错误？

Trie Implementation Logic Errors?

c

trie

cs50

trie 节点结构和根声明

加载函数

makeNewNode 函数