在C++中創建有向圖的困惑

Question

我想通過讀取一個文本文件創建一個有向圖，其中每行有兩列，第一列是尾部頂點，第二列是頭頂點。目前只是爲了測試我的代碼是否工作，我正試圖填充圖表並將其打印出來。

我在每次插入節點後打印圖形。直到我插入第三個節點「4」後，圖形打印工作良好，之後第一個節點從1變爲0.我沒有任何線索爲什麼。我想知道是否在邊緣存儲節點指針是個好主意。我這樣做是因爲我已經在「節點」向量中有節點信息，因此不想複製它。

輸入測試文件：

1 2 
4 5 

我的數據結構是： 節點：其保持節點ID和與布爾變量節點髒 邊緣：用於保持指針尾節點和根節點 圖表：保持矢量所有節點和邊緣

的

輸出：

Pushing :1 
print called 
Nodes are: 
1 

Pushing :2 
print called 
Nodes are: 
1 
2 

Pushing :4 
print called 
0(0) --> 2(0)  // Problem this should have been 1(0) --> 2(0) 
Nodes are: 
1 
2 
4 



#include <iostream> 
#include <vector> 
#include <fstream> 
#include <string> 
#include <sstream> 

using namespace std; 

class node { 
public: 
    node() {} 
    node(int _nodeId, bool dirty); 
    int nodeId; 
    bool dirty; 
    void operator=(node rhs); 
    bool operator==(node rhs); 
}; 

class edge { 
public: 
    edge(node *_startNode, node *_endNode): startNode(_startNode), endNode(_endNode) {} 
    node *startNode, *endNode; 
}; 



node :: node(int _nodeId, bool _dirty) { 
    nodeId = _nodeId; 
    dirty = _dirty; 
} 

void node :: operator=(node rhs) { 
    this->dirty = rhs.dirty; 
    this->nodeId = rhs.nodeId; 
} 

bool node :: operator==(node rhs) { 
    if (this->nodeId == rhs.nodeId) { 
     return true; 
    } 
    return false; 
} 



class graph { 
public: 
    void print(); 
    void addEdge(node startNode, node endNode); 
    void addNode(node n); 
    void dfs(node s); 
private: 
    vector<edge> edges; 
    vector<node> nodes; 
}; 

void graph :: addNode(node n) { 
    // only add this node if it does not exist in the graph 
    if (find(nodes.begin(), nodes.end(), n) == nodes.end()) { 
     //print(); 
     cout << "Pushing :"<<n.nodeId<<endl; 
     nodes.push_back(n); 
    } 
    print(); 
    cout << endl; 
} 

void graph :: dfs(node s) { 
    // Search node s and mark it as dirty 


} 
void graph :: print() { 
    cout << "print called\n"; 
    vector<edge>::iterator itr = edges.begin(); 
    while (itr != edges.end()) { 
     cout << itr->startNode->nodeId << "("<< itr->startNode->dirty<<") --> "; 
     cout << itr->endNode->nodeId << "("<< itr->endNode->dirty<<")"<<endl; 
     ++itr; 
    } 

    cout << "Nodes are:\n"; 
    for (int i=0; i< nodes.size(); ++i) { 
     cout << nodes.at(i).nodeId << endl; 
    } 
} 

void graph :: addEdge(node startNode, node endNode) { 
    vector<node>::iterator itrStartNode; 
    itrStartNode = find(nodes.begin(), nodes.end(), startNode); 
    vector<node>::iterator itrEndNode; 
    itrEndNode = find(nodes.begin(), nodes.end(), endNode); 
    edge e(&(*itrStartNode), &(*itrEndNode)); 
    edges.push_back(e); 
} 


int main(int argc, char *argv[]) { 
    graph g; 
    // Read the file here 
    ifstream file; 
    file.open("test.txt", ios::in); 
    string line; 
    while (getline(file, line)) { 
     int startNodeId, endNodeId; 
     istringstream is(line); 
     is >> startNodeId >> endNodeId; 
     node startNode(startNodeId, false); 
     node endNode(endNodeId, false); 
     g.addNode(startNode); 
     g.addNode(endNode); 
     g.addEdge(startNode, endNode); 
    } 
    file.close(); 
    g.print(); 
    return 0; 
} 

Answer 1

你正在創建臨時變量iables，

 node startNode(startNodeId, false); 
     node endNode(endNodeId, false); 

和

edge e(&(*itrStartNode), &(*itrEndNode)); 

和存儲指向臨時實例到您的容器中，例如

edge e(&(*itrStartNode), &(*itrEndNode)); 
    edges.push_back(e); 

一旦退出在其中創建的那些情況下的本地作用域（while環或addEdge方法），堆棧存儲器中存儲的那些實例被用於收回由程序的其它地方。但是，您的指針仍然指向有效的內存地址（由程序還是不回收），因此可能仍然指向有效數據。這可能是怎麼回事，，即爲什麼你看到有效的，但不正確的頂點。

使用new運算符可創建持續超出本地循環和函數範圍的實例，並適當地清理它們（通過delete）。