使用邻接表实现的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;
}

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

- Nishant

---

vPtr声明有点可疑。 - Jiminion

@Jim：我认为不是这样的，因为只有在将元素插入列表时代码才会出问题。如果删除该行，则代码可以正常工作。 - Nishant

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;
}

- Natan Streppel

---

确实，它会大幅改变代码。但我相信这是必要的，因为问题的本质是使用了不合适的工具。 - Natan Streppel

我完全同意。但是，这是一个有趣的学术练习，可以看到malloc和STL如何相互作用（或不相互作用）。关于malloc不运行构造函数的洞见很有趣。 - Jiminion

是的，我认为你的回答更好，因为它解决了问题。Streppel绕过了这个问题，这可能是正确的做法，但没有解释清楚。我会给你点赞，这是我能做的最少的事情... - Jiminion

@Jim，malloc函数是否不能为STL对象执行所需的操作？ - Bhupesh Pant

我认为STL可以做任何事情，但有些熟悉不同方法的人有时想要混合它们。总的来说，这可能不是最好的做法，但这种情况确实会发生。 - Jiminion

Answer 2

几个要点：

1. 由于您正在使用malloc，因此永远不会调用constructor，因此非原始成员adj从未构造并且为NULL。

2. 您正在泄漏内存，因为您从未释放/删除任何动态分配的内存。

3. 如果您正在使用C ++，为什么要使用malloc而不是new和delete？

4. 在C ++中，您不必在sizeof中说结构体顶点。

要修复它，您可以执行：

vPtr node = new struct vertex(); // also change to delete instead of free

或者

// use current malloc line, change adj to be a pointer to a list and new it
// but this will cause additional problems for you since you really need to use a constructor for STL::list
node->adj = new list<int>;

底线是，在这里您真的不应该使用malloc。

- UpAndAdam

---

也许他不应该，但了解这些相互作用还是很好的。 - Jiminion

我认为 node->adj = new list<int>; 不会编译通过。 - Jiminion

哎呀，没错，当你把adj定义为指针时就会出现这种情况。 - Jiminion

是的，这正是我在评论中告诉你要做的 :-) - UpAndAdam

@Jim 不用担心，老兄！干杯并感谢你的点赞！我的第一篇帖子回答是正确的，但从来没有得到过爱 :-p 还找到了一些很好的你发的帖子，我也费了些力才看懂。有趣的是，有时候你会遇到这样的情况，必须混合使用它们，尤其是如果你还不能使用放置 new 并且出于其他性能原因必须混合使用它们（调用 new 和 malloc 对延迟不利）… 是的，我意识到 STL 通常也是如此。 - UpAndAdam

Answer 3

这是UpAndAdam完整撰写的答案。

// 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->adj = new list<int>;
    node->info = 34;            // some arbitrary value
    (node->adj)->push_back(2);  // trying to insert a value in the list
    return 0;
}

- Jiminion