C++：初始化指针队列时出现段错误

问题描述：

我试图实现CLRS中描述的BFS算法。并具备以下条件：C++：初始化指针队列时出现段错误

#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 < nodeCount; 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; 
}

当我运行此不过，我只当队列被初始化得到下面的输出后跟一个segfault：

[email protected]:~/Code/cpp/dijkstra$ ./dijkstra 
3 
1 2 1 3 1 
2 3 1 
3 1 1 

performing bfs 
All nodes painted white 
Segmentation fault

我用下面的命令编译：

g++ -Wall -o dijkstra dijkstra.cpp

使用调试器，做一个堆栈跟踪。按照：http://stackoverflow.com/questions/3911814/c-in-g-segmentation-fault-when-not-using-pointers/3911873#3911873 – nsanders

如果你有一个segfault创建队列容器，那么最有可能堆已损坏。你有关于创建邻接表的评论，但这可能是问题所在。你正在分配一个节点数组，但你是否还分配了单个节点？ –

关于风格的评论：使用变量名“l”（小写字母L）只会导致混淆（因为每个人都会认为它是“1”（数字1））。所以，请你帮个忙，用另一个名字。 –

答

list<Node*> bfs(...

当你返回：

return l;

也没有必要以供参考：在这里你指出没有发生

Node** &nodes

与段错误。 I/O缓冲区没有fulshed因为它和它loooks这样

cout << "initialised a queue" << endl; 
list<Node*> l; 
cout << "initialised a list" << endl;

未执行

OP声明了返回的名为“l”（小写的L）的局部变量，而不是“1”（数字1）。 –

当绘制节点为白色时，问题出现在循环计数器中。我从零开始，但没有名称为0的节点！初始化为1可解决问题。 –

C++：初始化指针队列时出现段错误

相关推荐