使用OOP/C++实现后缀Trie

Question

我正在尝试在C++中为编程任务实现后缀trie。现在我认为我有正确的想法，但是我一直在发生分段错误，而且我一直无法找到造成它的原因。

对于这个任务，我们鼓励使用VIM /其他一些基本的文本编辑器，并从控制台编译程序。尽管如此，我已经下载了CLion来尝试和调试代码，所以我可以找到错误。

现在，在克利翁运行时，我得到的消息

terminate called after throwing an instance of 'std::bad_alloc' 
    what(): std::bad_alloc 

试图运行调试器会的消息

Error during pretty printers setup: 
Undefined info command: "pretty-printer". Try "help info". 
Some features and performance optimizations will not be available. 

我是新来的克利翁，我不知道该怎么办关于这个（我使用的唯一的JetBrains IDE是Pycharm）。你能帮我解决这个问题吗？

现在程序本身由三个类组成，Trie,Edge和Node，其实现可以在下面看到。实施Trie背后的主要思想是在Trie.cpp的构造函数中。

该代码详述如下。我感谢任何帮助。

---

Main.cpp的

#include <iostream> 
using namespace std; 

#include "Trie.hpp" 

int main(){ 

    string s = "Stef"; 
    Trie trie(s); 


    return 0; 
} 

Trie.hpp

#ifndef TRIE_HPP 
#define TRIE_HPP 

#include <string> 
#include "Node.hpp" 
#include "Edge.hpp" 
using namespace std; 

class Trie{ 

    private: 
     string T; 
     vector<Node> nodes; 
     void addWord(Node*, string); 

    public: 
     Trie(string);  

}; 

#endif 

Trie.cpp

#include <iostream> 
#include <cstring> 
#include "Trie.hpp" 
using namespace std; 

Trie::Trie(string T){ 
    T += "#";       //terminating character  
    this->T = T; 

    vector<string> suffix;    //array of suffixes 
    for(unsigned int i = 0; i < T.length(); i++) 
     suffix.push_back(T.substr(i, T.length()-i)); 

    //Create the Root, and start from it 
    nodes.push_back(Node(""));   //root has blank label 
    Node* currentNode = &nodes[0]; 

    //While there are words in the array of suffixes 
    while(!suffix.empty()){ 

     //If the character under consideration already has an edge, then this will be its index. Otherwise, it's -1. 
     int edgeIndex = currentNode->childLoc(suffix[0].at(0));  

     //If there is no such edge, add the rest of the word 
     if(edgeIndex == -1){ 
      addWord(currentNode, suffix[0]);    //add rest of word 
      suffix.erase(suffix.begin());     //erase the suffix from the suffix array 
      break;           //break from the for loop 
     } 

     //if there is 
     else{ 
      currentNode = (currentNode->getEdge(edgeIndex))->getTo();  //current Node is the next Node 
      suffix[0] = suffix[0].substr(1, suffix[0].length());      //remove first character 
     }   
    } 
} 

//This function adds the rest of a word 
void Trie::addWord(Node* parent, string word){ 
    for(unsigned int i = 0; i < word.length(); i++){    //For each remaining letter 
     nodes.push_back(Node(parent->getLabel()+word.at(i)));  //Add a node with label of parent + label of edge 
     Edge e(word.at(i), parent, &nodes.back());     //Create an edge joining the parent to the node we just added 
     parent->addEdge(e);           //Join the two with this edge 
    } 
} 

Node.hpp

#ifndef NODE_HPP 
#define NODE_HPP 

#include <string> 
#include <vector> 
#include "Edge.hpp" 
using namespace std; 

class Node{ 

    private: 
     string label;   
     vector<Edge> outgoing_edges; 

    public: 
     Node(); 
     Node(string); 
     string getLabel(); 
     int childLoc(char); 
     void addEdge(Edge); 
     Edge* getEdge(int); 
}; 

#endif 

Node.cpp

#include "Node.hpp" 
using namespace std; 

Node::Node(){ 
} 

Node::Node(string label){ 
    this->label = label; 
} 

string Node::getLabel(){ 
    return label; 
} 

//This function returns the edge matching the given label, returning -1 if there is no such edge. 
int Node::childLoc(char label){ 
    int loc = -1; 
    for(unsigned int i = 0; i < outgoing_edges.size(); i++) 
     if(outgoing_edges[i].getLabel() == label) 
      loc = i; 
    return loc; 
} 

void Node::addEdge(Edge e){ 
    outgoing_edges.push_back(e); 
} 

Edge* Node::getEdge(int n){ 
    return &outgoing_edges[n]; 
} 

Edge.hpp

#ifndef EDGE_HPP 
#define EDGE_HPP 

#include <string> 
using namespace std; 

class Node;   //Forward definition 

class Edge{ 

    private: 
     char label; 
     Node* from; 
     Node* to; 

    public: 
     Edge(char, Node*, Node*); 
     char getLabel(); 
     Node* getTo(); 
     Node* getFrom();  
}; 

#endif 

Edge.cpp

#include "Edge.hpp" 
using namespace std; 

Edge::Edge(char label, Node* from, Node* to){ 
    this->label = label; 
    this->from = from; 
    this->to = to; 
} 

char Edge::getLabel(){ 
    return label; 
} 

Node* Edge::getFrom(){ 
    return from; 
} 

Node* Edge::getTo(){ 
    return to; 
} 

Answer 1

&nodes[0];，&nodes.back() - 你存储的指针为vector以备后用，当你添加元素，它的向量的基础存储被重新安置这些变得无效。

阅读有关指针的一般信息，以及特别是在您最喜爱的C++书籍中的动态分配。
如果您还没有最喜欢的C++书籍，请从this list中挑选一本。