Trie trouver/ajouter fonction ne fonctionne pas correctement

Question

J'essaye d'implémenter une fonction de recherche pour ma structure de données trie tree. Je suis confus sur la façon de mettre en œuvre correctement, car je suppose que ma logique semble correcte en ce moment ... même si je suis encore un débutant dans ce domaine. Si quelqu'un peut jeter un coup d'œil à ma fonction et suggérer des améliorations, ce serait grandement apprécié. Le principal prend en gros fichiers de mots et recherche ensuite des mots pour tester la fonction. En ce moment, il renvoie false pour un mot qui devrait être dans l'objet trie.

exemple un message d'erreur

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

fonction de recherche:

//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 Noeud:

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

Vous avez mu ltiple bug dans votre implémentation.

Votre fonction addWord n'est pas correcte. Celui-ci devrait être mieux:

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 
} 

L'autre bug vous totalement manqué: "jean-pierre" contient des caractères non un z :) et votre getIndex échouera pour tout omble chevalier qui est hors de portée [a-z].

Les autres points:

• ne pas hardcode valeurs comme 26, parce que si vous devez mettre à jour votre gamme de [a-z] code ailleurs, silencieusement l'échec.
• utilisez assert pour vérifier les hypothèses d'entrée.

Quelque chose comme ceci:

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