Я написал одну простую таблицу Adj Matrix из одного списка Adj из gitHub.
Первый - это список Adj, второй - матрица Adj.
Первый работает хорошо. Но второе неверно с int Num
, который представляет число вершин, подобное первому int numOfVertices
. Это семя как 'int Num' становится переменной только для чтения. Это врезается в Process finished with exit code 11
.
Я искал вики, чтобы найти «сегментация по умолчанию», есть 4 причины, одна из которых пытается изменить переменную только для чтения.
Затем я отменяю изменение для «Num»в конструкторе для Adj Matrix. Это хорошо работает.
Но я не знаю, почему первое хорошо, а второе неправильно? И как это решить? Потому что мне нужно изменить значение Num ...
Код списка Adj
#ifndef ALTHGORITHM_GRAPH_ADJ_LIST_H
#define ALTHGORITHM_GRAPH_ADJ_LIST_H
#include <iostream>
#include <vector>
#include <queue>
namespace graph_adj_list {
template <class dataType> // Type of data vertex will hold
class Graph {
int numOfVertices; // number of vertices.
struct Vertex; // forward declaration of vertex structure
struct Node { // linkedlist for mapping edges in the graph
Vertex * vertexPtr; // points to the vertex to which the edge is adjecent
Node * next; // points to the next edge belonging to same vertex
};
enum visitedState{ // Enum representing visited state of vertex
WHITE, // not yet visited
GRAY, // being visited
BLACK // visited
};
struct Vertex {
visitedState state; // state of vertex, visited/being visited/done
dataType data; // the template data
Node * list; // Pointer to all edges (linkedlist)
};
std::vector<Vertex> vertices; // vector of all vertices.
//private methods
Node * getNode( Vertex * ); // allocate and initialize a newnode for the adj list.
void insertAtEnd( Node * & , Vertex * ); // insert at the end of adjacency list of vertex.
void deleteAllAfter( Node * ); // delete the adjacency list of the vertex.
public:
Graph() = default; // Default constructor
Graph(std::vector<dataType> &);
~Graph();
}
template <typename dataType>
typename Graph<dataType>::Node *
Graph<dataType>::getNode(Vertex * v) // allocate and initialize a newnode for the adj list.
{
Node * newNode = new Node;
newNode->vertexPtr = v;
newNode->next = nullptr;
return newNode;
}
template <typename dataType>
void Graph<dataType>::insertAtEnd( Node * & node, Vertex * v) // insert at the end of adjacency list of vertex.
{
Node *newNode = getNode(v);
if ( node == nullptr ) {
node = newNode;
} else {
Node * temp = node;
while( temp->next != nullptr ) {
temp = temp->next;
}
temp->next = newNode;
}
}
template <typename dataType>
void Graph<dataType>::deleteAllAfter( Node * node ) // delete the adjacency list of the vertex.
{
Node * nextNode;
while( node != nullptr ) {
nextNode = node->next;
delete(node);
node = nextNode;
}
}
template <typename dataType>
Graph<dataType>::Graph(std::vector<dataType> & values) // Non default constructor, takes a vector of vertices data
: numOfVertices(values.size()),
vertices(numOfVertices)
{
for ( int i = 0; i < numOfVertices; ++i ) {
vertices[i].data = values[i];
vertices[i].list = nullptr;
vertices[i].state = WHITE;
}
}
template <typename dataType>
Graph<dataType>::~Graph()
{
for( int i = 0; i < numOfVertices; ++i ) {
deleteAllAfter(vertices[i].list);
}
}
} //end of namespace graph
Код матрицы Adj
#ifndef ALTHGORITHM_GRAPH_ADJ_MATRIX_H
#define ALTHGORITHM_GRAPH_ADJ_MATRIX_H
#include <iostream>
#include <vector>
namespace graph_adj_matrix {
template<typename T>
class Graph {
int Num ;
enum visitedState {
NO_VISIT,
VISITING,
VISITED
};
struct vertex {
T data;
visitedState state;
};
std::vector<std::vector<int>> Matrix;
std::vector<vertex> matrix_list;
public:
Graph() = default;
Graph(std::vector<T> &);
~Graph();
void setMatrix(size_t index1, size_t index2);
void display();
};
template<typename T>
Graph<T>::Graph(std::vector<T> &values) :
Num(values.size())
,matrix_list(Num){
for (typename std::vector<T>::size_type i = 0; i < Num; ++i)
{
matrix_list[i].data = values[i];
matrix_list[i].state = NO_VISIT;
}
for (typename std::vector<T>::size_type i = 0; i < Num; ++i)
for (typename std::vector<T>::size_type j = 0; j < Num; ++j)
Matrix[i].push_back(0);
}
template<typename T>
void Graph<T>::setMatrix(size_t index1, size_t index2) {
for (size_t i = 0; i < Num; ++i) {
if (i == index1 || i == index2) {
for (size_t j = 0; j < Num; ++j) {
if (((i == index1) && (j == index2)) || ((i == index2) && (j == index1))) {
Matrix[i][j] = 1;
break;
}
}
break;
}
}
}
template<typename T>
void Graph<T>::display() {
for (size_t i = 0; i < Num; ++i) {
for (size_t j = 0; j < Num; j++)
std::cout << Matrix[i][j] << " ";
std::cout << std::endl;
}
}
template <typename T>
Graph<T>::~Graph() {}
}
#endif //ALTHGORITHM_GRAPH_ADJ_MATRIX_H
Cpp:
#include "Graph_Adj_List.h"
#include "Graph_Adj_Matrix.h"
int main() {
std::vector<std::string> myVec{"ABC","DEF","GHI","ZZZ"};
graph_adj_list::Graph<std::string> myGraph(myVec);
graph_adj_matrix::Graph<std::string> myGraph_matrix(myVec);
}
У меня есть отладчик, программа
graph_adj_list::Graph<std::string> myGraph(myVec);
работает хорошо. Но
graph_adj_matrix::Graph<std::string> myGraph_matrix(myVec);
останавливается на
#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
void
vector<_Tp, _Allocator>::push_back(value_type&& __x)
{
if (this->__end_ < this->__end_cap())
{
__RAII_IncreaseAnnotator __annotator(*this);
__alloc_traits::construct(this->__alloc(),
_VSTD::__to_raw_pointer(this->__end_),
_VSTD::move(__x));
__annotator.__done();
++this->__end_;
}
else
__push_back_slow_path(_VSTD::move(__x));
}
Функция из векторного заголовка Row с 1635 по 1653. Отладчик сообщает об этом
Exception = EXC_BAD_ACCESS (code=1, address=0x8)
this = {std::_11::vector<int,std::_1::allocator> * |0x0 } NULL
Когда я вхожу в телокоторый устанавливает `` `Matrix [i] .push_back (0) '' '. Это приводит к аварийному завершению.