C 深度首次使用前缀参数对Trie进行了搜索

Question

我正在尝试实现一个可以用给定前缀打印出单词频率的trie。

编辑：感谢 @kaidul-islam找到我的错误，以下错误：

new_word->child[letter]->prefixes_++;

以下是固定的代码：

trie类：

class Trie
{
public:
    Trie(): prefixes_(0), is_leaf_(false), frequency_(0)
    {
        for (int i=0; i<26; i++)
        {
            child[i] = nullptr;
        }
    }
    virtual ~Trie();
    //Child nodes of characters from a-z
    Trie *child[26];
    //vector<Trie> child;
    int prefixes_;
    //accessor & mutator functions
    bool GetIsLeaf() { return is_leaf_; }
    void SetIsLeaf(bool val) { is_leaf_ = val; }
    int GetFrequency() { return frequency_; }
    void SetFrequency(int val) { frequency_ = val; }
    int GetPrefixes() { return prefixes_; }
    void SetPrefixes(int val) { prefixes_ = val; }
    bool is_leaf_;
private:
    //bool is_leaf_;
    int frequency_;
};

函数中的功能：

void AddWord(string &word, Trie *root)
{
    Trie *new_word = root;
    new_word->prefixes_++;
    for(unsigned int i = 0 ; i < word.length(); i++)
    {
        int letter = (int)word[i] - (int)'a';   //extract character of word
        if(new_word->child[letter] == nullptr)
        {
            new_word->child[letter] = new Trie;
        }
        /*cout << "not value of x: " << new_word->child[letter]->GetPrefixes() << endl;
        int x = (new_word->child[letter]->GetPrefixes())+1;
        cout << "value of x: " << x << endl;
        new_word->child[letter]->SetPrefixes(x);*/
        new_word->child[letter]->prefixes_++;
        new_word = new_word->child[letter];
    }
    new_word->SetFrequency(new_word->GetFrequency()+1);
    /*
    cout << "Word: " << word << endl;
    cout << "frequency: " << new_word->GetFrequency() << endl;
    cout << "prefixes: " << new_word->GetPrefixes() << endl;
    cout << "is leaf: " << new_word->GetIsLeaf() << endl << endl;
    */
}

Answer 1

快速检查后，我发现您没有在构造函数中初始化成员变量。

Trie(): prefixes_(0),
        is_leaf_(false),
        frequency_(0) {
    for(int i = 0; i < 26; i++) {
        child[i] = nullptr;
    }
}

与全局变量不同，不能保证prefixes_在声明上默认为0。child[i]也不能保证为nullptr。您需要初始化所有内容。