pourquoi cette implémentation C++ Trie montre un comportement étrange?

Question

J'ai implémenté cette classe pour créer une structure de données. La fonction

unsigned long Insert(string) //inserts the string in trie & return no of words in trie 

void PrintAllWords(); // prints all words in trie separated by space in dictionary order 

application fonctionne correctement et imprime tous les mots insérés dans un fichier texte de mots du dictionnaire anglais lorsque le nombre de mots est pas très grande, mais quand fourni avec un fichier avec quelques 350k mots il imprime seulement abcd jusqu'à z.

variables privées

struct TrieTree 
{ 
    std::map<char,struct TrieTree*> map_child; 
    std::map<char,unsigned long> map_count; //keeps incrementing count of char in map during insertion. 
    bool _isLeaf=false; // this flag is set true at node where word ends 
}; 

struct TrieTree* _root=NULL; 
unsigned long _wordCount=0; 
unsigned long _INITIALIZE=1; 

Ci-dessous la mise en œuvre complète avec le programme pilote. Le programme est exécutable.

#include<iostream> 
#include<map> 
#include<fstream> 
class Trie 
{ 
private: 

    struct TrieTree 
    { 
     std::map<char,struct TrieTree*> map_child; 
     std::map<char,unsigned long> map_count; 
     bool _isLeaf=false; 
    }; 

    struct TrieTree* _root=NULL; 
    unsigned long _wordCount=0; 
    unsigned long _INITIALIZE=1; 

    struct TrieTree* getNode() 
    { 
     return new TrieTree; 
    }; 


    void printWords(struct TrieTree* Tptr,std::string pre) 
    { 
     if(Tptr->_isLeaf==true) 
     { 
      std::cout<<pre<<" "; 
      return; 
     } 

     std::map<char,struct TrieTree*>::iterator it; 
     it=Tptr->map_child.begin(); 
     while(it!=Tptr->map_child.end()) 
     { 
      pre.push_back(it->first); 
      printWords(it->second,pre); 
      pre.erase(pre.length()-1); //erase last prefix character 
      it++; 
     } 

    } 


public: 

    Trie() 
    { 
     _root=getNode(); 
    } 
    unsigned long WordCount() 
    { 
     return _wordCount; 
    } 
    unsigned long WordCount(std::string pre) //count words with prefix pre 
    { 
     if(WordCount()!=0) 
     { 
      struct TrieTree *Tptr=_root; 
      std::map<char,unsigned long>::iterator it; 
      char lastChar; 
      for(int i=0;i<pre.length()-1;i++) 
      { 
       Tptr=Tptr->map_child[pre[i]]; 
      } 
      lastChar=pre[pre.length()-1]; 
      it=Tptr->map_count.find(lastChar); 
      if(it!=Tptr->map_count.end()) 
      { 
       return Tptr->map_count[lastChar]; 
      } 
      else 
      { 
       return 0; 
      } 
     } 
     return 0; 
    } 

    unsigned long Insert(std::string key) //return word count after insertion 
    { 
     struct TrieTree *Tptr =_root; 
     std::map<char,struct TrieTree*>::iterator it; 

     if(!SearchWord(key)) 
     { 
      for(int level=0;level<key.length();level++) 
      { 
       it=Tptr->map_child.find(key[level]); 
       if(it==Tptr->map_child.end()) 
       { 
        //alphabet does not exist in map 
        Tptr->map_child[key[level]]=getNode(); // new node with value pointing to it 
        Tptr->map_count[key[level]] = _INITIALIZE; 
        Tptr=Tptr->map_child[key[level]];  //assign pointer to newly obtained node 
        if(level==key.length()-1) 
         Tptr->_isLeaf=true; 
       } 
       else 
       { //alphabet exists at this level 
        Tptr->map_count[key[level]]++; 
        Tptr=Tptr->map_child[key[level]]; 
       } 
      } 
      _wordCount++; 
     } 
     return _wordCount; 
    } 

    bool SearchWord(std::string key) 
    { 
     struct TrieTree *Tptr =_root; 
     std::map<char,struct TrieTree*>::iterator it; 
     for(int level=0;level<key.length();level++) 
     { 
      it=Tptr->map_child.find(key[level]); 
     // cout<<" "<<Tptr->map_child.size()<<endl; //test to count entries at each map level 

      if(it!=Tptr->map_child.end()) 
      { 
       Tptr=Tptr->map_child[key[level]]; 
      } 
      else 
      { 
       return false; 
      } 
     } 
     if(Tptr->_isLeaf==true) 
      return true; 
     return false; 
    } 

    void PrintAllWords() 
    { //print all words in trie in dictionary order 
     struct TrieTree *Tptr =_root; 
     if(Tptr->map_child.empty()) 
      { 
       std::cout<<"Trie is Empty"<<std::endl; 
       return; 
      } 

     printWords(Tptr,""); 

    } 
    void PrintAllWords(std::string pre) 
    { //print all words in trie with prefix pre in Dictionary order 
     struct TrieTree *Tptr =_root; 
     if(Tptr->map_child.empty()) 
      { 
       std::cout<<"Trie is Empty"<<std::endl; 
       return; 
      } 

     for(int i=0;i<pre.length();i++) 
     { 
      Tptr=Tptr->map_child[pre[i]]; 
     } 

     printWords(Tptr,pre); 

    } 


}; 

int main(){ 
Trie t; 

std::string str; 
std::fstream fs; 
fs.open("words.txt",std::ios::in); 

while(fs>>str){ 
    t.Insert(str); 
} 

t.PrintAllWords(); 

return 0; 
} 

Je ne comprends pas la sortie, s'il vous plaît jeter un oeil sur le code et suggérer une solution. Merci

Answer 1

Lorsque vous ajoutez le mot «a», s'il n'y a pas de mot commençant par «a» dans l'arborescence, vous allez ajouter un nœud «feuille» avec la valeur «a». Si vous ajoutez ensuite un mot commençant par 'a', tel que "an", vous ajouterez le noeud 'n' en tant qu'enfant du noeud 'a'. Cependant, lorsque vous imprimez tous les mots, vous arrêtez d'être récursif lorsque vous frappez un nœud feuille, ce qui signifie que vous ignorez tous les autres mots commençant par ce mot.

Solution simple: retirez le return de printWords.

De même, si vous avez déjà "an" dans l'arborescence, lorsque vous ajoutez "a", vous ne le marquez pas comme une feuille, donc il ne sera jamais sorti.

solution simple: Set _isLeaf lors de l'ajout d'un mot, même si le nœud existe déjà (à savoir ajouter Tptr->_isLeaf=true; à la clause else dans Insert

Je pense que vous seriez mieux changer _isLeaf à quelque chose comme _isWord comme il semble