使用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中挑選一本。