c++ - 图的链表实现

Question

我是 C++ 的新手。

我正在尝试创建一个带有链接节点的图的邻接表实现，视觉上它看起来像这样:

[Headnode Vertex | Next Node] -> [Adjacent Node Vertex | Next] -> etc
[0 | ]-> [1 | ]-> [2 | ]-> [NULL node]
[1 | ]-> [0 | ]-> [2 | ]-> [NULL node]
[2 | ]-> [0 | ]-> [1 | ]-> [NULL node]

3 个节点的图，顶点编号为 0-2，对吗？

下面是我正在实现的代码:

struct node {
    int vertex;
    node *next;
};

node *headnodes;
bool *Visited;
bool cycles = false;// determine if a graph has cycles.

class Graph {

    private: 
        int n; // number of vertices
        int e; // number of edges
        //node *headnodes;

    public:  
        Graph(int nodes) // construtor
        {
            n = nodes;
            headnodes = new node[n]; // headnodes is an array of nodes.
            for (int i = 0; i < n; i++)
            {
                headnodes[i].vertex = i;
                headnodes[i].next = 0; //points null
            }
        }

        //This function is based off lecture notes (Lecture 13)
        //node graph
        int Graph::create()
        {
            //iterate through the head nodes
            for (int i = 0; i < n; i++) {
                cout << "Initializing " << i << "-th node.\n";
                if (i == 0){
                    //headnode 0 points to its adjacent nodes 1, and 2
                    headnodes[n].next = new node; //initialize new node
                    node link = headnodes[n]; //assign to new variable
                    link.vertex = 1;
                    link.next->vertex = 2;
                    link.next->next = 0;
//This works
                    cout << "vertex of first node: " << headnodes[n].next->vertex; 
                } else if (i == 1){
                    headnodes[n].next = new node; //initialize new node
                    node link = headnodes[n];
                    link.vertex = 0; //the first node
                    link.next->vertex = 3; //the second node
                    //the 3rd node
                    /*link.next = new node;
                    node *link2 = link.next;
                    link.next->next->vertex = 4;
                    link.next->next->next = 0;*/
                } else if (i == 2){
                    headnodes[n].next = new node; //initialize new node
                    node link = headnodes[n];
                    link.vertex = 0;
                    link.next->vertex = 3;
                    link.next->next = 0;
                }
            }
//This doesn't?
            cout << "Checking vertex";
            cout << "First node's link vert: " << headnodes[0].next->vertex; //ERROR, Access Violation!
            return 0;
        }
};

我认为因为 headnodes 变量是全局的，所以它会很好，但它会导致运行时错误(访问冲突)，显然它指向一个空节点(但它是全局的所以 wth)？我不明白哪里出了问题。

有人能指出我正确的方向吗？我觉得我很接近。

Answer 1

您的问题很简单。在你的create您尝试遍历邻接列表的函数，但是您不断索引 n-th headnode你可能知道它在数组的边界之外。

您将 3 作为 nodes 传递并将其分配给 n并在您的循环中继续将其索引为 headnodes[n] .您可以通过添加 cout << n << endl; 来验证这一点在每次访问 headnodes 之前;你会看到3每一次。

您可能希望根据 i 为它们编制索引因为那将是迭代索引。