c++: Getting a segfault when initialising a queue of pointers
I am trying to implement the BFS algorithm described in CLRS. And have the following:
#include <iostream>
#include <list>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
struct Node{
char colour;
int numNbr;
Node* parent;
int distance;
int* neighbours;
int* costs;
int name;
Node(int _numNbr,int _name){
name = _name;
colour = 'w';
parent = 0;
distance = -1;
neighbours = new int[_numNbr];
costs = new int[_numNbr];
numNbr = _numNbr;
}
};
list<Node*> bfs(Node** &nodes,int numNodes,int startNode) {
cout << "performing BFS\n";
for(int i = 0; i < numNodes;i++) {
nodes[i]->colour = 'w';
nodes[i]->parent = 0;
}
cout << "All nodes painted white" <<endl;
queue<Node*> q; // segfault occurs here
cout << "initialised a queue" << endl;
list<Node*> l;
cout << "initialised a list" << endl;
nodes[startNode]->colour = 'g';
nodes[startNode]->distance = 0;
q.push(nodes[startNode]);
Node* u;
Node* v;
while(!q.empty()){
u = q.front();
for(int i = 0;i < u->numNbr; i++) {
v = nodes[u->neighbours[i]];
if(v->colour == 'w'){
v->colour = 'g';
v->distance = (u->distance)+1;
v->parent = u;
q.push(v);
}
}
l.push_front(u);
u->colour = 'b';
q.pop();
}
return l;
}
int main(){
int nodeCount;
cin >> nodeCount;
cin.ignore();
Node** nodes = new Node*[nodeCount+1];
for(int i = 0; i < 开发者_如何学CnodeCount; i++){
.... // build up the nodes in the adjacency list
}
list<Node*> l = bfs(nodes,nodeCount,1);
cout << "BFS of nodes\n";
for(list<Node*>::iterator it = l.begin();it != l.end();it++){
cout << (*it)->name << " ";
}
cout << endl;
return 0;
}
When I run this however, I only get the following output followed by a segfault
when the queue is initialised:
jonathan@debian:~/Code/cpp/dijkstra$ ./dijkstra
3
1 2 1 3 1
2 3 1
3 1 1
performing bfs
All nodes painted white
Segmentation fault
I am compiling with the following command:
g++ -Wall -o dijkstra dijkstra.cpp
list<Node*> bfs(...
while you return:
return l;
also, no need for reference here:
Node** &nodes
And segfault didn't occur where you pointed. I/O buffers were not fulshed because of it and it loooks like this
cout << "initialised a queue" << endl;
list<Node*> l;
cout << "initialised a list" << endl;
wasn't executed
精彩评论