在c ++中使用Adjacency List的图表

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++对象一起使用,这里有很好的解释 (简答:在C++中,当你不处理POD类型时,std::list在你的情况下,你必须调用对象的构造函数来使用准备使用的实际对象,并malloc()没有这样做).

你应该用new代替.虽然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;
}