C++でカスタムグラフデータ構造を作成しようとしています。私はstd :: setを使って頂点を追跡しています。新しい頂点を挿入するときにセットをチェックして、まだグラフにないことを確認します。 C++での私の経験は少ないので、これを正しく実装するのに問題があります。問題は、contains
の機能のようです。ここでは、グラフのためのコードは次のとおりです。頂点をカスタムグラフのデータ構造に追加しようとすると、セグメンテーションフォルトが発生しますか?
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#ifndef GRAPH_H
#define GRAPH_H
/*
Graph - Templated graph class
*/
template <typename T>
struct AdjListNode {
T data;
int index;
struct AdjListNode<T> *next;
};
template <typename T>
struct AdjList {
struct AdjListNode<T> *head;
};
template <class T>
class Graph {
private:
std::vector< AdjList<T>* > m_adj_list; //Adjacency list
std::set<T> m_node_set;
std::map<T, int> m_index_map;
int m_num_vertices;
bool m_is_directed;
void addDirectedEdge(T src, T dest);
bool contains(T vertex);
public:
Graph(bool isDirected=true);
bool isDirected();
int numVertices();
bool addVertex(T vertex);
void addEdge(T src, T dest);
std::string printGraph();
AdjListNode<T>* getAdjacent(T vertex);
};
#endif
CPPファイル:
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include "Graph.h"
template <class T>
Graph<T>::Graph(bool is_directed) {
m_num_vertices = 0;
m_is_directed = is_directed;
}
template <class T>
bool Graph<T>::isDirected() {
return m_is_directed;
}
template <class T>
int Graph<T>::numVertices() {
return m_num_vertices;
}
template <class T>
bool Graph<T>::addVertex(T vertex) {
//check to make sure node is not in graph
if (contains(vertex)) { //segfault occurs here
AdjListNode<T> *newNode = new AdjListNode<T>;
newNode->index = m_adj_list.size();
AdjList<T> *newAdjList = new AdjList<T>;
newAdjList->head = newNode;
m_adj_list.push_back(newAdjList);
m_num_vertices++;
return true;
} else {
return false;
}
}
template <class T>
void Graph<T>::addDirectedEdge(T src, T dest) {
if (contains(src)) {
AdjListNode<T> *newNode = new AdjListNode<T>;
newNode->data = dest;
newNode->next = NULL;
AdjList<T> *list = m_adj_list[m_index_map[src]];
AdjList<T> *currentNode = list->head;
while (currentNode->next != NULL) {
currentNode = currentNode->next;
}
//insert at the end of adjacency list
currentNode->next = newNode;
}
}
template <class T>
bool Graph<T>::contains(T vertex) {
return m_node_set.find(vertex) == vertex;
}
template <class T>
void Graph<T>::addEdge(T src, T dest) {
addDirectedEdge(src, dest);
if (!m_is_directed) {
addDirectedEdge(dest, src);
}
}
template <class T>
std::string Graph<T>::printGraph() {
return "";
}
template <class T>
AdjListNode<T>* Graph<T>::getAdjacent(T vertex) {
if (*m_node_set.find(vertex) == vertex) {
AdjListNode<T>* list = m_adj_list[m_index_map[vertex]];
return list->head->next;
} else {
return NULL;
}
}
は、誰もがこの問題を解決する正しい方向に私を指すことができますか?ありがとう。あなたはヘッダファイルにすべての実装を置くべきテンプレートを使用する場合contains
方法で
すべきではありません。そうしないと、リンカの「未解決」エラーが発生します。 – CodeFuller
m_node_set.find(頂点)==頂点が正しくありません。 m_node_set.find(vertex)!= m_node_set.end – CodeFuller
@CodeFullerヒントをお寄せいただきありがとうございます。私は先に進んで少しリファクタリングします。 –