Autocomplete unter Verwendung von Trie

Question

Ich versuche, eine Art Autocomplete-Funktion in C++ zu machen. Zuerst benutze ich ein Trie und sobald das funktioniert (und am wichtigsten, ich weiß, wie alles funktioniert) werde ich es mit einem Ternary-Baum versuchen. Aber jetzt bekomme ich einen Segmentierungsfehler, wenn ich Wörter hinzufüge, die mit einem anderen Zeichen beginnen als die bereits im Trie.

Eg. wir fügen "abc", "abcd" und "abcde" hinzu, das ist kein Problem. Später, wenn ich hinzufügen möchte (während die "abc" usw. noch in der Trie sind) "xfce", "xfced" tritt ein Segmentierungsfehler auf.

Ich debugging dies seit einiger Zeit und scheint nicht das Problem zu finden.

Ich denke, das Problem liegt irgendwo in Trie.cpp, so dass die Datei, die ich hier bereitstellen werde. Allerdings könnte es in der Hauptfunktion als gut sein, aber ich will nicht angebrüllt bekommen zu viel Code veröffentlichen ...

#include "Trie.h" 
#include <iostream> 

Trie::Trie() 
{ 
    this->root = new Node(false); 
} 

Trie::~Trie() 
{ 

} 

Trie::Node::Node(bool isLeaf) 
{ 
    this->isLeaf = isLeaf; 
} 

void Trie::insert(const std::string& word) 
{ 
    Node* crawler = this->root; 
    int index; 

    for(int i = 0; i < word.length(); ++i) 
    { 
     index = CHAR_TO_INDEX(word.at(i)); 

     if(!crawler->children[index]) 
     { 
      crawler->children[index] = new Node(false); 
     } 
     crawler = crawler->children[index]; 
    } 
    crawler->isLeaf = true; 
} 

int Trie::contains(const std::string& word) 
{ 
    int index; 
    Node* crawler = this->root; 

    for(int i = 0; i < word.length(); ++i) 
    { 
     index = CHAR_TO_INDEX(word.at(i)); 

     if(!crawler->children[index]) 
     { 
      return -1; 
     } 
     crawler = crawler->children[index]; 
    } 

    return (crawler != NULL && crawler->isLeaf); 
} 

std::vector<std::string> Trie::possibleSuffixes(std::string& prefix) 
{ 
    Node* crawler = this->root; 
    int index; 
    std::vector<std::string> result; 

    for(int i = 0; i < prefix.length(); ++i) 
    { 
     index = CHAR_TO_INDEX(prefix.at(i)); 
     crawler = crawler->children[index]; 
    } 

    traverse(prefix, crawler, result); 

    return result; 
} 

void Trie::traverse(std::string prefix, Node* node, std::vector<std::string>& v) 
{ 
    if(node->isLeaf) 
    { 
     v.push_back(prefix); 
    } 

    for(int i = 0; i < ALPHABET; ++i) 
    { 
     if(node->children[i]) 
     { 
      traverse(prefix + (char)('a' + i), node->children[i], v); 
     } 
    } 
} 

Entire Trie-Klasse:

#ifndef TRIE_H 
#define TRIE_H 

#include <string> 
#include <vector> 

#define ARRAYSIZE(a) sizeof(a/sizeof(a[0])) 
#define ALPHABET 26 
#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 

class Trie 
{ 
    private: 
     struct Node 
     { 
      Node(bool isLeaf); 
      struct Node *children[ALPHABET]; 
      bool isLeaf; 
     }; 

     Node *root; 
     void traverse(std::string prefix, Node* node, std::vector<std::string>& v); 

    public: 
     Trie(); 
     ~Trie(); 
     int contains(const std::string& word); //Checks the existance of a specific word in the trie 
     void insert(const std::string& word);  //Inserts new word in the trie if not already there 
     std::vector<std::string> possibleSuffixes(std::string& prefix); 

}; 

Answer 1

Obwohl Sie nicht erwähnt diese über Ihre Node Klasse, gehe davon aus I -

class Node { 
public: 
    bool isLeaf; 

    // must be >= 25 as you're inserting lowercase letters 
    // assuming your CHAR_TO_INDEX(ch) returns 0 based index 
    // e.g. 'a' => 0, 'b' => 1 ... 'z' => 25 
    Node* children[30]; 

    // default constructor should be like this 
    Node(): isLeaf(false) { 
      for(int i = 0; i < 26; i++) { 
       children[i] = NULL; 
      } 
    } 

    ~Node() { 
     for(int i = 0; i < 26; i++) { 
      if(children[i]) { 
       delete children[i]; 
       children[i] = NULL; 
      } 
     } 
     delete this; 
    } 
}; 

Bitte vergleichen Sie Ihre Node Klasse/Struktur, ob seine so etwas wie dieses.