プログラミングの割り当てのために、C++ でサフィックス trie を実装しようとしています。今は正しい考えを持っていると思いますが、セグメンテーション違反が発生し続けており、その原因を見つけることができませんでした.
この課題では、VIM/その他の基本的なテキスト エディターを使用し、コンソールからプログラムをコンパイルすることをお勧めします。それにもかかわらず、エラーを見つけることができるように、コードを試してデバッグするために 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現在、プログラム自体は 、 、およびの 3 つのクラスで構成されてEdgeおりNode、その実装を以下に示します。Trie の実装の背後にある主なアイデアは、 のコンストラクタにありTrie.cppます。
コードの詳細は以下のとおりです。助けていただければ幸いです。
メイン.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
}
}
ノード.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;
}