为什么我在尝试将顶点添加到邻接列表时遇到分段错误？
Why am I reaching a segmentation fault when trying to add vertices to the adjacency list?
我正在编写一个程序，我试图在其中尝试使用邻接表构建图形数据结构。图形结构中的顶点有一个 ID、x 和 y 坐标，以及一个关联的邻接列表，其中包含有关子顶点是什么以及到达它们所花费的权重的信息。
我已经尝试使用打印语句进行调试，例如图中的 for 循环 class，但是我无法打印关于我已 push_back 进入的顶点的任何信息矢量称为图形。此外，我知道坐标文件的所有内容都已读入，但每当我尝试从边缘文件创建邻接表时，我都会收到 Segmentation fault (core dumped)。我试图在 Visual Studio 代码上使用调试器，但它说程序能够 运行 没有任何错误，尽管我在编译后遇到了分段错误。
如何才能停止出现此分段错误？我也试过调整我的数组大小，但这也不起作用。我在尝试创建的 for 循环中遇到了分段错误。我不确定为什么顶点对象没有添加到我创建的向量中。有人可以指导我如何实际添加它们吗？
#ifndef VERTEX_H
#define VERTEX_H
#include <vector>
#define INF 1000000000
using namespace std;
class Vertex {
public:
int id;
Vertex* parent;
bool visited; // Flag to see if this vertex has been visited
vector<pair<Vertex*, int>> children; // Connecting vertices to this vertex
float g; // Path cost from source vertex to this vertex
float h; // Heuristic ost from this node to goal node
int x; // x-coordinate of vertex in graph space
int y; // y-coordinate of vertex in graph space
// Constructor
Vertex(int id, int x, int y) {
this->id = id;
this->x = x;
this->y = y;
this->g = INF;
this->h = INF;
parent = NULL;
visited = false;
}
// Add an edge to the vertex, populate the adjacency list
void addEdge(Vertex* child, int weight) {
children.push_back(make_pair(child, weight));
}
// Generic heuristic value calculation
float f() {
return g + h;
}
};
#endif
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <sstream>
#include <vector>
using std::ifstream;
#include "Vertex.h"
using namespace std;
class Graph {
public:
vector<Vertex*> graph;
int vertexCount;
string edges;
string coordinates;
// Constructor
Graph(string edges, string coordinates, int vertexCount) {
this->edges = edges;
this->coordinates = coordinates;
this->vertexCount = vertexCount;
this->graph = createGraph(edges, coordinates, vertexCount);
};
vector<Vertex*> createGraph(string edges, string coordinates, int vertexCount) {
vector<Vertex*> graph;
// Read in coordinate information of vertices
ifstream coordinateInput(coordinates);
string line1, tempString1, tempString2, tempString3;
int vertex; // Member ID of the vertex
float x, y;
while (getline(coordinateInput, line1)) {
stringstream ss(line1);
getline(ss, tempString1, ',');
if (tempString1 == "--------------") break;
vertex = stoi(tempString1);
if (vertex >= graph.size()) {
graph.resize(vertex + 1); // Resize
}
getline(ss, tempString2, ',');
x = stof(tempString2);
getline(ss, tempString3, ',');
y = stof(tempString3);
graph.push_back(new Vertex(vertex, x, y));
}
coordinateInput.close();
for (Vertex* v : graph) {
std::cout << "here" << endl;
std::cout << v->id << ' ' << v->x << v->y << endl;
}
std::cout << "Finished" << endl;
// Read in edge information and add them to the graph
ifstream edgeInput(edges);
int src, dest, weight;
string line2, tempString4, tempString5, tempString6;
while (getline(edgeInput, line2)) {
stringstream ss(line2);
getline(ss, tempString4, ',');
if (tempString4 == "--------------") break;
src = stoi(tempString4);
getline(ss, tempString5, ',');
dest = stoi(tempString5);
getline(ss, tempString6, ',');
weight = stoi(tempString6);
std::cout << graph[src]->id << endl;
std::cout << src << ' ' << dest << ' ' << weight << endl;
graph[src]->addEdge(graph[dest], weight);
}
edgeInput.close();
return graph;
}
};
#endif
我正在尝试读入的数据：
坐标：
1,42.66,73.78
2,33.76,84.40
3,30.30,97.75
4,42.32,71.09
5,42.90,78.85
6,51.00,114.00
7,35.21,80.83
8,41.84,87.68
9,41.48,81.67
10,32.80,96.79
11,39.73,104.97
12,41.59,93.62
13,31.79,106.42
14,48.87,-2.33
15,32.74,97.33
16,29.76,95.38
17,39.79,86.15
18,30.32,81.66
19,35.68,220.23
20,39.08,94.56
21,24.56,81.78
22,30.19,82.64
23,36.19,115.22
24,34.03,118.17
25,42.33,122.86
26,35.12,89.97
27,25.79,80.22
28,44.96,93.27
29,37.3,120.9
30,45.50,73.67
31,29.97,90.06
32,40.70,73.92
33,28.53,81.38
34,40.72,76.12
35,33.53,112.08
36,38.07,122.81
37,45.52,122.64
38,35.82,78.64
39,39.53,119.82
40,38.56,121.47
41,29.45,98.51
42,37.76,122.44
43,37.30,121.87
44,46.49,84.35
45,47.63,122.33
46,37.69,97.34
47,39.76,84.20
48,35.27,120.66
49,27.97,82.46
50,30.45,84.27
51,43.65,79.38
52,38.91,77.01
53,40.75,111.89
--------------
边缘：
1,30,226
1,2,1003
1,32,153
1,4,166
1,5,212
2,4,1075
2,26,456
2,50,308
3,16,186
3,13,577
3,15,190
3,41,79
3,31,511
4,5,455
4,32,215
4,30,161
4,28,1391
5,51,105
5,9,191
6,52,605
6,32,829
6,51,2116
7,18,432
7,38,165
7,8,987
8,28,511
8,46,361
9,34,476
9,47,214
9,51,292
9,10,1341
10,11,792
10,15,20
10,16,248
10,41,374
11,46,523
11,35,466
11,35,386
12,44,135
12,28,246
12,4,933
12,26,789
12,50,310
12,13,1132
13,41,580
13,35,320
13,35,328
14,34,3939
14,19,5313
15,44,314
15,17,413
16,15,101
16,31,321
17,18,1014
17,20,502
17,50,432
18,33,146
18,22,113
19,36,5131
19,48,5451
20,44,249
20,46,190
20,21,1092
20,22,1231
21,49,446
21,22,2341
21,29,892
22,27,902
22,49,169
22,50,104
22,23,421
23,24,275
23,53,486
23,39,439
24,43,124
24,48,182
24,29,328
25,37,275
25,36,365
26,44,413
27,33,235
27,49,282
27,21,159
28,32,463
28,25,1920
29,40,80
30,51,401
30,29,1080
31,50,388
31,32,1901
32,34,101
32,53,1311
32,24,1531
33,49,84
33,32,1343
34,14,3548
34,52,147
35,43,518
36,37,642
36,24,962
36,42,635
36,40,115
36,48,271
37,45,174
37,53,777
38,52,371
39,53,520
39,40,133
40,41,140
40,42,95
41,48,895
41,42,2093
42,43,50
42,48,232
43,48,168
44,32,882
44,51,436
45,52,115
46,53,335
47,17,165
47,46,795
47,9,212
48,51,2751
48,50,133
48,52,232
51,18,486
52,51,2095
49,50,275
49,51,1335
49,53,2328
50,11,795
50,52,2095
51,15,201
51,16,248
52,41,373
52,19,4869
53,52,2084
53,26,1243
53,51,2343
36,43,519
15,32,643
46,24,962
46,42,633
38,40,113
26,48,222
16,19,3431
27,40,123
35,43,1131
25,45,220
15,11,341
25,42,1232
--------------
这是一个带有嵌入式数据的精简版本，演示了我可能如何解决这个问题。由于嵌入的数据集，我不得不进行一些修改，但您应该能够很容易地调整它以从文件中读取。流毕竟是蒸汽。
Vertexclass需要注意的一个修改：
int x; // x-coordinate of vertex in graph space
int y; // y-coordinate of vertex in graph space
Vertex(int id, int x, int y) {
我将成员类型和构造函数参数更改为 float。数据被解析为浮点数，但在传递给构造函数时被截断。如果您打算这样做，那很好，但对我来说似乎很奇怪。
您解析数据的方式并没有什么特别的问题，我只是更改它以显示替代方案。您应该知道，如果无法解析数据，stoi 和 stof 将抛出异常。您也不需要文件和 if (tempString4 == "--------------") break; 中的最后一行，因为 std::getline 将失败并在到达末尾时中断循环。
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#define INF 1000000000
using namespace std;
class Vertex {
public:
int id;
vector<pair<Vertex*, int>> children; // Connecting vertices to this vertex
float x; // x-coordinate of vertex in graph space
float y; // y-coordinate of vertex in graph space
Vertex(int id, float x, float y) {
this->id = id;
this->x = x;
this->y = y;
}
void addEdge(Vertex* child, int weight) {
children.push_back(make_pair(child, weight));
}
};
class Graph {
public:
vector<Vertex*> graph;
int vertexCount;
Graph(std::istream& edges, std::istream& coordinates) {
graph = createGraph(edges, coordinates);
vertexCount = static_cast<int>(graph.size()) - 1;
};
~Graph()
{
for (auto& v : graph)
{
delete v;
}
}
vector<Vertex*> createGraph(std::istream& edges, std::istream& coordinates) {
vector<Vertex*> ret(1);
string line;
while (getline(coordinates, line)) {
stringstream ss(line);
int vertex;
float x;
float y;
char comma;
if (ss >> vertex >> comma >> x >> comma >> y && ss.eof())
{
ret.push_back(new Vertex(vertex, x, y));
}
else
{
std::cout << "Data error parsing vertex from '" << line << "'\n";
}
}
for (Vertex* v : ret) {
if (v)
{
std::cout << v->id << ' ' << v->x << ", " << v->y << endl;
}
}
while (getline(edges, line)) {
stringstream ss(line);
int src;
int dest;
int weight;
char comma;
if (ss >> src >> comma >> dest >> comma >> weight && ss.eof())
{
if (src < static_cast<int>(ret.size()) && ret[src])
{
//hack to force dest into range 1, 10 of limited dataset
dest = 1 + dest % 10;
ret[src]->addEdge(ret[dest], weight);
}
else
{
std::cout << "Data error: src " << src << " invalid\n";
}
}
else
{
std::cout << "Data error parsing edge from '" << line << "'\n";
}
}
return ret;
}
};
int main()
{
std::istringstream coordinates(
"1, 42.66, 73.78\n"
"2, 33.76, 84.40\n"
"3, 30.30, 97.75\n"
"4, 42.32, 71.09\n"
"5, 42.90, 78.85\n"
"6, 51.00, 114.00\n"
"7, 35.21, 80.83\n"
"8, 41.84, 87.68\n"
"9, 41.48, 81.67\n"
"10, 32.80, 96.79");
std::istringstream edges(
"1, 20, 226\n1, 2, 1003\n1, 32, 153\n1, 4, 166\n1, 5, 212\n"
"2, 4, 1075\n2, 26, 456\n2, 50, 308\n"
"3, 16, 186\n3, 13, 577\n3, 15, 190\n3, 41, 79\n3, 31, 511\n"
"4, 5, 455\n4, 32, 215\n4, 30, 161\n4, 28, 1391\n"
"5, 51, 105\n5, 9, 191\n"
"6, 52, 605\n6, 32, 829\n6, 51, 2116\n7, 18, 432\n7, 38, 165\n7, 8, 987\n"
"8, 28, 511\n8, 46, 361\n"
"9, 34, 476\n9, 47, 214\n9, 51, 292\n9, 10, 1341\n"
"10, 11, 792\n10, 15, 20\n10, 16, 248\n10, 41, 374"
);
Graph g(edges, coordinates);
for (const auto& v : g.graph)
{
if (v)
{
std::cout << "\n";
std::cout << v->id << ", " << v->x << ", " << v->y << "\n";
for (const auto& e : v->children)
{
std::cout << "\t";
std::cout << e.first->id << ", " << e.first->x << ", " << e.first->y << ", " << e.second << "\n";
}
}
}
}
我正在编写一个程序，我试图在其中尝试使用邻接表构建图形数据结构。图形结构中的顶点有一个 ID、x 和 y 坐标，以及一个关联的邻接列表，其中包含有关子顶点是什么以及到达它们所花费的权重的信息。
我已经尝试使用打印语句进行调试，例如图中的 for 循环 class，但是我无法打印关于我已 push_back 进入的顶点的任何信息矢量称为图形。此外，我知道坐标文件的所有内容都已读入，但每当我尝试从边缘文件创建邻接表时，我都会收到 Segmentation fault (core dumped)。我试图在 Visual Studio 代码上使用调试器，但它说程序能够 运行 没有任何错误，尽管我在编译后遇到了分段错误。
如何才能停止出现此分段错误？我也试过调整我的数组大小，但这也不起作用。我在尝试创建的 for 循环中遇到了分段错误。我不确定为什么顶点对象没有添加到我创建的向量中。有人可以指导我如何实际添加它们吗？
#ifndef VERTEX_H
#define VERTEX_H
#include <vector>
#define INF 1000000000
using namespace std;
class Vertex {
public:
int id;
Vertex* parent;
bool visited; // Flag to see if this vertex has been visited
vector<pair<Vertex*, int>> children; // Connecting vertices to this vertex
float g; // Path cost from source vertex to this vertex
float h; // Heuristic ost from this node to goal node
int x; // x-coordinate of vertex in graph space
int y; // y-coordinate of vertex in graph space
// Constructor
Vertex(int id, int x, int y) {
this->id = id;
this->x = x;
this->y = y;
this->g = INF;
this->h = INF;
parent = NULL;
visited = false;
}
// Add an edge to the vertex, populate the adjacency list
void addEdge(Vertex* child, int weight) {
children.push_back(make_pair(child, weight));
}
// Generic heuristic value calculation
float f() {
return g + h;
}
};
#endif
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <sstream>
#include <vector>
using std::ifstream;
#include "Vertex.h"
using namespace std;
class Graph {
public:
vector<Vertex*> graph;
int vertexCount;
string edges;
string coordinates;
// Constructor
Graph(string edges, string coordinates, int vertexCount) {
this->edges = edges;
this->coordinates = coordinates;
this->vertexCount = vertexCount;
this->graph = createGraph(edges, coordinates, vertexCount);
};
vector<Vertex*> createGraph(string edges, string coordinates, int vertexCount) {
vector<Vertex*> graph;
// Read in coordinate information of vertices
ifstream coordinateInput(coordinates);
string line1, tempString1, tempString2, tempString3;
int vertex; // Member ID of the vertex
float x, y;
while (getline(coordinateInput, line1)) {
stringstream ss(line1);
getline(ss, tempString1, ',');
if (tempString1 == "--------------") break;
vertex = stoi(tempString1);
if (vertex >= graph.size()) {
graph.resize(vertex + 1); // Resize
}
getline(ss, tempString2, ',');
x = stof(tempString2);
getline(ss, tempString3, ',');
y = stof(tempString3);
graph.push_back(new Vertex(vertex, x, y));
}
coordinateInput.close();
for (Vertex* v : graph) {
std::cout << "here" << endl;
std::cout << v->id << ' ' << v->x << v->y << endl;
}
std::cout << "Finished" << endl;
// Read in edge information and add them to the graph
ifstream edgeInput(edges);
int src, dest, weight;
string line2, tempString4, tempString5, tempString6;
while (getline(edgeInput, line2)) {
stringstream ss(line2);
getline(ss, tempString4, ',');
if (tempString4 == "--------------") break;
src = stoi(tempString4);
getline(ss, tempString5, ',');
dest = stoi(tempString5);
getline(ss, tempString6, ',');
weight = stoi(tempString6);
std::cout << graph[src]->id << endl;
std::cout << src << ' ' << dest << ' ' << weight << endl;
graph[src]->addEdge(graph[dest], weight);
}
edgeInput.close();
return graph;
}
};
#endif
我正在尝试读入的数据： 坐标：
1,42.66,73.78
2,33.76,84.40
3,30.30,97.75
4,42.32,71.09
5,42.90,78.85
6,51.00,114.00
7,35.21,80.83
8,41.84,87.68
9,41.48,81.67
10,32.80,96.79
11,39.73,104.97
12,41.59,93.62
13,31.79,106.42
14,48.87,-2.33
15,32.74,97.33
16,29.76,95.38
17,39.79,86.15
18,30.32,81.66
19,35.68,220.23
20,39.08,94.56
21,24.56,81.78
22,30.19,82.64
23,36.19,115.22
24,34.03,118.17
25,42.33,122.86
26,35.12,89.97
27,25.79,80.22
28,44.96,93.27
29,37.3,120.9
30,45.50,73.67
31,29.97,90.06
32,40.70,73.92
33,28.53,81.38
34,40.72,76.12
35,33.53,112.08
36,38.07,122.81
37,45.52,122.64
38,35.82,78.64
39,39.53,119.82
40,38.56,121.47
41,29.45,98.51
42,37.76,122.44
43,37.30,121.87
44,46.49,84.35
45,47.63,122.33
46,37.69,97.34
47,39.76,84.20
48,35.27,120.66
49,27.97,82.46
50,30.45,84.27
51,43.65,79.38
52,38.91,77.01
53,40.75,111.89
--------------
边缘：
1,30,226
1,2,1003
1,32,153
1,4,166
1,5,212
2,4,1075
2,26,456
2,50,308
3,16,186
3,13,577
3,15,190
3,41,79
3,31,511
4,5,455
4,32,215
4,30,161
4,28,1391
5,51,105
5,9,191
6,52,605
6,32,829
6,51,2116
7,18,432
7,38,165
7,8,987
8,28,511
8,46,361
9,34,476
9,47,214
9,51,292
9,10,1341
10,11,792
10,15,20
10,16,248
10,41,374
11,46,523
11,35,466
11,35,386
12,44,135
12,28,246
12,4,933
12,26,789
12,50,310
12,13,1132
13,41,580
13,35,320
13,35,328
14,34,3939
14,19,5313
15,44,314
15,17,413
16,15,101
16,31,321
17,18,1014
17,20,502
17,50,432
18,33,146
18,22,113
19,36,5131
19,48,5451
20,44,249
20,46,190
20,21,1092
20,22,1231
21,49,446
21,22,2341
21,29,892
22,27,902
22,49,169
22,50,104
22,23,421
23,24,275
23,53,486
23,39,439
24,43,124
24,48,182
24,29,328
25,37,275
25,36,365
26,44,413
27,33,235
27,49,282
27,21,159
28,32,463
28,25,1920
29,40,80
30,51,401
30,29,1080
31,50,388
31,32,1901
32,34,101
32,53,1311
32,24,1531
33,49,84
33,32,1343
34,14,3548
34,52,147
35,43,518
36,37,642
36,24,962
36,42,635
36,40,115
36,48,271
37,45,174
37,53,777
38,52,371
39,53,520
39,40,133
40,41,140
40,42,95
41,48,895
41,42,2093
42,43,50
42,48,232
43,48,168
44,32,882
44,51,436
45,52,115
46,53,335
47,17,165
47,46,795
47,9,212
48,51,2751
48,50,133
48,52,232
51,18,486
52,51,2095
49,50,275
49,51,1335
49,53,2328
50,11,795
50,52,2095
51,15,201
51,16,248
52,41,373
52,19,4869
53,52,2084
53,26,1243
53,51,2343
36,43,519
15,32,643
46,24,962
46,42,633
38,40,113
26,48,222
16,19,3431
27,40,123
35,43,1131
25,45,220
15,11,341
25,42,1232
--------------
这是一个带有嵌入式数据的精简版本，演示了我可能如何解决这个问题。由于嵌入的数据集，我不得不进行一些修改，但您应该能够很容易地调整它以从文件中读取。流毕竟是蒸汽。
Vertexclass需要注意的一个修改：
int x; // x-coordinate of vertex in graph space
int y; // y-coordinate of vertex in graph space
Vertex(int id, int x, int y) {
我将成员类型和构造函数参数更改为 float。数据被解析为浮点数，但在传递给构造函数时被截断。如果您打算这样做，那很好，但对我来说似乎很奇怪。
您解析数据的方式并没有什么特别的问题，我只是更改它以显示替代方案。您应该知道，如果无法解析数据，stoi 和 stof 将抛出异常。您也不需要文件和 if (tempString4 == "--------------") break; 中的最后一行，因为 std::getline 将失败并在到达末尾时中断循环。
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#define INF 1000000000
using namespace std;
class Vertex {
public:
int id;
vector<pair<Vertex*, int>> children; // Connecting vertices to this vertex
float x; // x-coordinate of vertex in graph space
float y; // y-coordinate of vertex in graph space
Vertex(int id, float x, float y) {
this->id = id;
this->x = x;
this->y = y;
}
void addEdge(Vertex* child, int weight) {
children.push_back(make_pair(child, weight));
}
};
class Graph {
public:
vector<Vertex*> graph;
int vertexCount;
Graph(std::istream& edges, std::istream& coordinates) {
graph = createGraph(edges, coordinates);
vertexCount = static_cast<int>(graph.size()) - 1;
};
~Graph()
{
for (auto& v : graph)
{
delete v;
}
}
vector<Vertex*> createGraph(std::istream& edges, std::istream& coordinates) {
vector<Vertex*> ret(1);
string line;
while (getline(coordinates, line)) {
stringstream ss(line);
int vertex;
float x;
float y;
char comma;
if (ss >> vertex >> comma >> x >> comma >> y && ss.eof())
{
ret.push_back(new Vertex(vertex, x, y));
}
else
{
std::cout << "Data error parsing vertex from '" << line << "'\n";
}
}
for (Vertex* v : ret) {
if (v)
{
std::cout << v->id << ' ' << v->x << ", " << v->y << endl;
}
}
while (getline(edges, line)) {
stringstream ss(line);
int src;
int dest;
int weight;
char comma;
if (ss >> src >> comma >> dest >> comma >> weight && ss.eof())
{
if (src < static_cast<int>(ret.size()) && ret[src])
{
//hack to force dest into range 1, 10 of limited dataset
dest = 1 + dest % 10;
ret[src]->addEdge(ret[dest], weight);
}
else
{
std::cout << "Data error: src " << src << " invalid\n";
}
}
else
{
std::cout << "Data error parsing edge from '" << line << "'\n";
}
}
return ret;
}
};
int main()
{
std::istringstream coordinates(
"1, 42.66, 73.78\n"
"2, 33.76, 84.40\n"
"3, 30.30, 97.75\n"
"4, 42.32, 71.09\n"
"5, 42.90, 78.85\n"
"6, 51.00, 114.00\n"
"7, 35.21, 80.83\n"
"8, 41.84, 87.68\n"
"9, 41.48, 81.67\n"
"10, 32.80, 96.79");
std::istringstream edges(
"1, 20, 226\n1, 2, 1003\n1, 32, 153\n1, 4, 166\n1, 5, 212\n"
"2, 4, 1075\n2, 26, 456\n2, 50, 308\n"
"3, 16, 186\n3, 13, 577\n3, 15, 190\n3, 41, 79\n3, 31, 511\n"
"4, 5, 455\n4, 32, 215\n4, 30, 161\n4, 28, 1391\n"
"5, 51, 105\n5, 9, 191\n"
"6, 52, 605\n6, 32, 829\n6, 51, 2116\n7, 18, 432\n7, 38, 165\n7, 8, 987\n"
"8, 28, 511\n8, 46, 361\n"
"9, 34, 476\n9, 47, 214\n9, 51, 292\n9, 10, 1341\n"
"10, 11, 792\n10, 15, 20\n10, 16, 248\n10, 41, 374"
);
Graph g(edges, coordinates);
for (const auto& v : g.graph)
{
if (v)
{
std::cout << "\n";
std::cout << v->id << ", " << v->x << ", " << v->y << "\n";
for (const auto& e : v->children)
{
std::cout << "\t";
std::cout << e.first->id << ", " << e.first->x << ", " << e.first->y << ", " << e.second << "\n";
}
}
}
}