1

我使用链表创建了一个图形数据结构。使用此代码：

typedef struct vertexNode *vertexPointer;
typedef struct edgeNode *edgePointer;

void freeGraph(vertexPointer); /* announce function */

struct edgeNode{
    vertexPointer connectsTo;
    edgePointer next;
};

struct vertexNode{
    int vertex;
    edgePointer next;
};

然后我创建一个图，其中有 4 个节点，比如说 A、B、C 和 D，其中：A 通过 B 连接到 D，A 通过 C 连接到 D。使用链表，我想它看起来像这样：

图表是什么样子的

最后，我尝试使用 freeGraph(graph) 释放图形。

void freeEdge(edgePointer e){
    if (e != NULL) {
        freeEdge(e->next);
        freeGraph(e->connectsTo);
        free(e);
        e = NULL;
    }
}

void freeGraph(vertexPointer v){
    if (v != NULL) {
        freeEdge(v->next);
        free(v);
        v = NULL;
    }
}

这就是 valgrind 开始抱怨“大小为 4 的无效读取”、“地址 0x41fb0d4 是大小为 8 的块内的 4 个字节 free'd”和“无效的 free()”的地方。它还说它做了8个mallocs和9个frees。

我认为问题在于节点 D 的内存已经被释放，然后我试图再次释放它。但是我看不出有任何方法可以在不改变数据结构的情况下做到这一点。

如果可能，无需更改数据结构，防止这些错误并正确释放图形的最佳方法是什么？此外，如果此代码有任何其他问题，请告知。谢谢！

问候，分号

4

5 回答 5

2

缺乏了解所有参考资料使这有点困难。有点 hack，但面对同样的问题，我可能会使用指针集（唯一值列表，在本例中为指针）。

  • 遍历整个图，仅当节点指针不存在时才将节点指针推入集合（这是“集合”的定义）
  • 遍历集合，释放每个指针（因为它们是唯一的，所以没有双重释放问题）
  • 设置graph为 NULL。

我确信对此有一个优雅的递归解决方案，但是面对所述的任务，这似乎是可行的，而且并不过于复杂。

于 2012-10-19T18:05:08.357 回答
2

您可以将它们分配到内存池中，而不是在全局堆上分配节点和边。要释放图形，请释放整个池。

于 2012-10-19T18:14:37.373 回答
1

我会通过设计一种方法来解决这个问题，在释放它之前首先从图中干净地删除每个节点。要清楚地做到这一点，您必须弄清楚哪些其他节点正在引用您将要删除的节点并删除这些边。删除边缘后，如果您碰巧遇到了之前引用已删除节点的另一个节点，则该边缘将已经消失，您将无法再次尝试删除它。

最简单的方法是修改您的数据结构以保存对“传入”边缘的引用。这样你就可以做类似的事情：

v->incoming[i]->next = null; // do this for each edge in incoming
freeEdge(v->next);
free(v);
v = NULL;

如果您不想更新数据结构，那么您将面临一个难题，即在图形中搜索与要删除的节点具有边的节点。

于 2012-10-19T18:03:41.353 回答
0

这是因为您在这里进行了两次递归，并且它们相互踩踏。 freeGraph被调用一次以释放 D（例如，从 B），然后当初始调用freeGraph从 回来时freeEdge，您尝试释放v- 这已经在更深层得到处理。没有插图，这是一个糟糕的解释，但你去吧。

您可以摆脱一个递归，这样它们就不会“交叉”，或者您可以在每个空闲之前检查该节点是否已被递归的另一个分支处理。

于 2012-10-19T18:07:15.893 回答
0

是的，问题是 D 可以通过两条路径到达并释放两次。

您可以分两个阶段进行： 阶段 1：将您到达的节点插入“集合”数据结构。阶段 2：释放“集合”数据结构中的节点。

该设置数据结构的可能实现，需要扩展您的数据结构：用布尔标志标记数据结构中的所有节点，这样您就不会将它们插入两次。对所有节点的第二个链表使用另一个“下一个”指针。一个简单的。

另一种实现，无需扩展您的数据结构：类似于 C++ std::set<>

另一个问题：当你从 A 开始时，你确定所有节点都可以到达吗？为避免此问题，请在创建时将所有节点插入“集合”数据结构中（那么您将不需要标记）。

于 2012-10-19T18:13:07.780 回答