c - Trie实现逻辑错误？

Question

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

1. 从文本文件中读取单词
2. 逐个字符地迭代该单词
3. 将该角色的字母索引号附加到新节点并将其附加到根节点

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

你看，我在第三步中想做的是:

1. 如果需要，创建一个新节点(如果需要的节点已存在，则跳过步骤 2)
2. 将该新节点附加到根的子数组，其中它附加到扫描字符字母索引的位置例如如果要扫描“a”，则新节点将附加到 root->children[a 的字母索引
3. 移动到根中的下一个节点，以便下一个节点将附加到该节点

为了进一步缩小问题范围，我仍在试图弄清楚第二、第三和第四个问题。

对于第二步，到目前为止我尝试过的是:

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];

您在这里修改了root。因此，对于下一个word，root将不是实际的根，而是插入数据的最后一个节点.需要保持原来的root。