尝试只插入单词的第一个字母，而不是整个单词

Question

我目前正在开发一个将单词插入到 trie 中的程序。目前我的插入函数只添加单词的第一个字母然后停止。从我查阅的所有内容来看，我的代码看起来是正确的，所以我不明白问题出在哪里。

我尝试将 temp-> wordEnd = true 移动到 for 循环的外部和函数的不同位置。因为我相信这就是问题所在，因为我的插入函数中的其他所有内容看起来都是正确的。

这是我的插入函数：

bool Trie::insert(string word)
{
    TrieNode *temp = root;
    temp->prefixAmount++;

    for (int i = 0; i < word.length(); ++i)
    {
        int currentLetter = (int)word[i] - (int)'a';
        if (temp->child[currentLetter] == NULL)
        {
            temp->child[currentLetter] = new TrieNode();
            temp->child[currentLetter]->prefixAmount++;
            temp = temp->child[currentLetter];
        }
        temp->wordEnd = true;
        return true;
    }
}

也为了帮助大家更好的遵循我的代码这是我的 TrieNode 结构：

  struct TrieNode
   {
     int prefixAmount;
     struct TrieNode *child[ALPHA_SIZE];
    bool wordEnd;

   };

这是我的 Trie 构造函数：

   Trie::Trie()
    {
      root = new TrieNode();
      root->wordEnd = false;
     root->prefixAmount = 0;

     }

预期的结果应该是整个单词都被插入了。实际发生的是只添加了单词的第一个字母。

Answer 1

我已经为您重新格式化了代码，现在您应该可以看到主要问题了。

您 return 在 for 循环中的块末尾。这意味着它运行是 for 循环的第一次迭代，只是 return 而不考虑其余字母。

一个简单的解决方法是将 return 放在 for 循环之外 但还有另一个问题，如果当前字母已经存在，则您无法正确更新 Trie在里面。您的 NULL 检查是正确的，但您应该只 new 在 NULL 上启动 TrieNode 但您还想运行所有后续行，即使它不是NULL。固定代码如下所示：

bool Trie::insert(string word)
{
    TrieNode *temp = root;
    temp->prefixAmount++;

    for (int i = 0; i < word.length(); ++i)
    {
        int currentLetter = (int)word[i] - (int)'a';
        if (temp->child[currentLetter] == NULL)
        {
            temp->child[currentLetter] = new TrieNode();
        }
        temp->child[currentLetter]->prefixAmount++;
        temp = temp->child[currentLetter];
    }
    temp->wordEnd = true;
    return true;
}

（代码中的其他小问题超出了问题的范围 - 更喜欢 nullptr 而不是 NULL，为什么 return a bool 如果它总是 true，如果您的字符串包含 a-z 之外的任何内容，那么您将在数组边界之外读取，更喜欢 unique_ptr 和 make_unqiue 而不是原始 new/delete ).

尝试只插入单词的第一个字母，而不是整个单词

Trie only inserting first letter of a word, not the whole word

c++

insert

trie