使用 OOP/C++ 实现后缀特里

Question

我正在尝试在 C++ 中为编程作业实现一个后缀特里树。现在我认为我的想法是正确的，但我一直遇到分段错误，而且我一直无法找到导致它的原因。

对于此作业，我们鼓励使用 VIM/some 其他基本文本编辑器，并从控制台编译程序。不过，我已经下载了 CLion 来尝试调试代码，以便找到错误。

现在运行在 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.

我是 CLion 的新手，我不确定该怎么做（我唯一使用的 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 中选择一本。

使用 OOP/C++ 实现后缀特里

Implementing a Suffix Trie using OOP/C++

c++

oop

clion

suffix-tree

suffix