Trieの検索/追加機能が正しく動作しない

Question

私のトライツリーデータ構造の検索機能を実装しようとしています。私はこれを適切に実装する方法を混乱させています。私の論理は今正しいと思われるので...私はまだこれの初心者ですが。誰かが私の機能を見て改善すべき場所を示せばそれは大いに感謝します。メインは大きな単語ファイルを取り込み、その中の単語を検索して基本的に機能をテストします。今は、トライオブジェクト内にある単語に対してfalseを返します。

例のエラーメッセージ

Error: jean-pierre is not in the spellcheck and it should have been 

検索機能：

//looks up the word in the SpellCheck object. If it is in the SpellCheck object,true is returned. 
//You can assume that the word will be all lower case. 
bool lookup(const string& word) const { 

    if (!root_) { 
      return false; 
    } 

    Node* curr = root_; 

    if (word[0] == '\0') { 
      return curr->isTerminal_ == true; 
    } 


    for (int i = 0; i < word.length(); i++) 
    { 
      int idx = curr->getIndex(word[i]); 

      if (idx < 0 || idx >= 26){ 
        return false; 
      } 
      // Search top level for node that 
    // matches first character in key 

      if (curr->children_[idx] == nullptr) { 
        return false; 
      } 
      curr = curr->children_[idx]; 

    } 
    return curr->isTerminal_ == true; 
} 

ノード構造体：

struct Node { 
      bool isTerminal_; 
      char ch_; 
      Node* children_[26]; 
      Node(char c = '\0') { 
        isTerminal_ = false; 
        ch_ = c; 
        for (int i = 0; i < 26; i++) { 
          children_[i] = nullptr; 
        } 
      } 
      //given lower case alphabetic charachters ch, returns 
      //the associated index 'a' --> 0, 'b' --> 1...'z' --> 25 
      int getIndex(char ch) { 
        return ch - 'a'; 
      } 
    }; 
    Node* root_; 

Answer 1

あなたが持っているムーあなたの実装における複数のバグ。

addWord機能が正しくありません。 この1つは良いはずです：

void addWord(const string& newWord, int currChar, Node* rt) 
{ 
    //check if currChar index is still in newWord 
    if (currChar < newWord.length()) { 
     //find index of currChar 
     char currLetter = newWord[currChar]; 
     int idx = rt->getIndex(currLetter); 

     //if no letter at that index create a new node 
     if (!rt->children_[idx]) 
      //make a new node 
      rt->children_[idx] = new Node(currLetter); 
     //continue to add 
     addWord(newWord, currChar + 1, rt->children_[idx]); 
    } 
    else 
     rt->isTerminal_ = true; //last char 
} 

あなたが完全に逃した他のバグ："jean-pierre"が非Zの文字が含まれています:)とあなたのgetIndexが[a-z]範囲内ではありません任意の文字のために失敗します。

他のポイント：あなたが他の場所[a-z]コードからご 範囲を更新する必要がある場合は黙って失敗するので

• は、26のような値をハードコードしないでください。
• assertを使用して入力の前提を確認してください。

このような何か：

int getIndex(char ch) 
{ 
    assert(ch >= 'a' && ch <= 'z'); 
    return ch == '-' ? 26 : ch - 'a'; 
}