c++ - 在 C++ 中使用邻接表的图形

Question

我正在尝试用 C++ 实现一个图形。我使用包含两个变量的结构表示图中的一个节点 -
a) 一个包含节点一些信息的整数。
b) 一个列表，包含与其相连的其他顶点的索引。
代码如下。

// Graphs using adjacency list

#include <iostream>
#include <list>
#include <cstdlib>
using namespace std;

// structure to represent a vertex(node) in a graph
typedef struct vertex{
    int info;
    list<int> adj;   // adjacency list of edges contains the indexes to vertex
} *vPtr;             

int main(){
    vPtr node = (vPtr)malloc(sizeof(struct vertex));
    node->info = 34;            // some arbitrary value
    (node->adj).push_back(2);   // trying to insert a value in the list
    return 0;
}

代码编译正常，但在推回列表中的元素时出现运行时错误。我的结构有什么问题吗？
我正在使用代码块和 GNU GCC、C++ 98 编译器来编译我的代码。

Answer 1

malloc 是一个 C 函数 - 它不应该与 C++ 对象一起使用，which is very well explained here (简短的回答:在 C++ 中，当您不处理 POD 类型时，std::list 在您的情况下，您必须调用对象的构造函数以使实际对象准备好使用, 而 malloc() 不会那样做)。

You should used new instead .虽然 malloc 只分配一个大小为 vertex 的内存块，但 new 会这样做并初始化 std::list以及通过调用它的构造函数(有趣的是，当您调用 delete() 时，您也在调用对象的析构函数)。

尽管我建议您开始在 C++ 项目中使用更多 C++ 功能，但这里有一段代码适用于您的情况:

#include <iostream>
#include <list>
#include <cstdlib>
#include <new>

using namespace std;

// structure to represent a vertex(node) in a graph
typedef struct vertex{
    int info;
    list<int> adj;   // adjacency list of edges contains the indexes to vertex
} *vPtr;             

int main(){
    cout << "allocating memory for our vertex struct... \n";
    vPtr node = new vertex();
    node->info = 34;            // some arbitrary value
    (node->adj).push_back(2);   // trying to insert a value in the list
    cout << "cleaning allocated memory... \n";
    delete(node);

    return 0;
}