爲什麼這些詞不包含在我的詞典（C++ trie）中？

我認爲我的trie實現有問題。我用蘋果這個詞來測試它。雖然我的測試文件dict.txt包含單詞apple，但它返回false。什麼是錯誤？爲什麼這些詞不包含在我的詞典（C++ trie）中？

class Trie{ 

private: 

    class Node{ 

    public: 
     Node* next[26]; 
     bool isWord; 
     Node(){ isWord = false; } 
    }; 
    Node* root; 

public: 

    Trie() { 
     root = new Node(); 
    } 

    void load(const string& line) { 

     Node* node = root; 

     for(int i = 0; i < line.size(); i++){ 
      char x = line[i]; 
      if(node->next[x-'a'] == nullptr)      
       node->next[x-'a'] = new Node(); 
      node = node->next[x-'a']; 
     } 

     node->isWord = true; 
    } 

    bool contains(const string& word) { 
     Node* node = root; 

     for(int i = 0; i < word.size(); i++){ 
      char x = word[i]; 
      if(node->next[x-'a'] == nullptr) 
       return false; 
      else 
       node = node->next[x-'a']; 
     } 

     return node->isWord; 
    } 

    bool startWith(const string& prefix) { 
     Node* node = root; 

     for(int i = 0; i < prefix.size(); i++){ 
      char x = prefix[i]; 
      if(node->next[x-'a'] == nullptr) 
       return false; 
      else 
       node = node->next[x-'a']; 
     } 
     return true; 
    } 
}; 


int main() { 

    Trie trie; 

    ifstream inFile; 
    string line; 
    while(getline(inFile, line)){ 
     trie.load(line); 
    } 
    cout << trie.contains("apple") << endl; 
    cout << trie.startWith("cata") << endl; 

    return 0; 
}

來源

2016-04-03 Hongshen

在代碼中使用調試器並單步執行。是的，代碼檢查是一件好事，但我認爲您可以通過調試器更快地解決此問題，而不是等待StackOverflow上的回覆。 –

你忘了初始化'next'，給你一個未定義的程序。 – molbdnilo

你忘了初始化指針Node* next[26]到nullptr秒。而且，因此，可能會錯誤地添加單詞。但不知道。

來源

2016-04-03 18:35:51

是的，你說得對，我應該初始化它們，謝謝！ – Hongshen

請檢查我的建議。我還不確定這是否是你的原因。 –

嗨，這是事情，我的測試詞典（dict.txt）實際上不包含單詞「apple」。然後我嘗試了一些包含在dict.txt中的單詞來測試我的輪胎，它工作正常！但令我驚訝的是，無論指針是否被初始化，它都能正常工作。 – Hongshen

-1

我試過在CodeBlocks上用gcc11運行你的代碼，一切正常。我沒有使用dict.tx t文件，我只是運行命令trie.load("apple");，一切正常。也許，在從文件讀取行的同時，您還可以閱讀一些特殊符號。嘗試打印您從文件中讀取的內容。

來源

2016-04-03 19:09:11

他的程序包含未定義的行爲。它碰巧用你的編譯器做你期望的事情就沒有意義。 –

感謝您的回答和嘗試。我的測試dict.txt不包含蘋果這個詞，直到我直接在測試文件中搜索蘋果，我才意識到這一點。其他一切工作正常，沒有錯誤。 – Hongshen

爲什麼這些詞不包含在我的詞典（C++ trie）中？

回答

相關問題