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

來源

2011-09-27 Jonno_FTW

使用調試器，做一個堆棧跟蹤。按照：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;

未執行

來源

2011-09-27 06:22:56 GreenScape

OP聲明瞭返回的名爲「l」（小寫的L）的局部變量，而不是「1」（數字1）。 –

當繪製節點爲白色時，問題出現在循環計數器中。我從零開始，但沒有名稱爲0的節點！初始化爲1可解決問題。 –

C++：初始化指針隊列時出現段錯誤

回答

相關問題