Освобождение динамически выделенных узлов графа в C
Я хочу построить граф, который создает новый родительский узел путем слияния двух дочерних узлов. Код ниже должен объединить узлы a и b в родительский узел c. Затем узлы a и c для создания родительского узла d:
a b
|---|
|
a c
|---|
|
d
Когда я пытаюсь освободить граф, начинающийся с узла d, я получаю ошибку сегментации, и я не знаю, почему. Каким-то образом это работает, если я не использую один и тот же узел дважды в графе. Однако я хочу иметь возможность использовать один и тот же узел более одного раза. Может кто-нибудь, пожалуйста, скажите мне, что мне здесь не хватает?
#include <stdlib.h>
struct Node {
int data;
struct Node *child1;
struct Node *child2;
};
struct Node *NewNode(double data) {
struct Node *node = NULL;
node = malloc(sizeof(*node));
if (node == NULL) {
return node;
}
node->data = data;
node->child1 = NULL;
node->child2 = NULL;
return node;
}
struct Node* merge(struct Node *self, struct Node *other) {
struct Node *node = NewNode(-1);
node->child1 = self;
node->child2 = other;
return node;
}
void free_graph(struct Node **node) {
if (*node != NULL) {
free_graph(&(*node)->child1);
free_graph(&(*node)->child2);
free(*node);
*node = NULL;
}
}
int main(void){
struct Node *a = NewNode(1);
struct Node *b = NewNode(2);
struct Node *c = merge(a, b);
struct Node *d = merge(a, c);
free_graph(&d);
}
@klutt Я хочу использовать один и тот же узел дважды. Однако не совсем уверен, что вы имеете в виду под стоимостью. Из узла d и c мне нужен прямой доступ к узлу a.
Ну, тогда то, что вы хотите, это не дерево :)
Хорошо, тогда, наверное, это график? Я обновил вопрос.
Ответы 2
Вы дважды помещаете a в намеченное дерево, поэтому free_graph пытается освободить его дважды. Вызов free дважды по одному и тому же адресу из одного и того же исходного распределения является неправильным.
Если вы хотите иметь настоящее дерево, не помещайте в него ни один узел дважды. Если вы хотите иметь структуру данных, которая может иметь один и тот же узел дважды, либо используйте отдельные копии узла (например, два разных выделения для struct Node с одинаковым значением для data), либо предусмотрите структуру данных, чтобы избежать освобождения его дважды (например, добавьте счетчик ссылок к struct node, чтобы подсчитать, сколько раз он находится в дереве в данный момент, и освободите узел только тогда, когда его счетчик ссылок достигнет нуля).
Я хотел бы иметь структуру данных без создания копии, так как это усложнило бы дальнейшую работу. Не совсем уверен, как счетчик ссылок работает в C. Я пытался установить указатель на узел NULL, чтобы он не освобождался более одного раза. Почему это не работает в моем случае?
@Gilfoyle: Re «Я пытался установить указатель на узел NULL, чтобы он не освобождался более одного раза. Почему это не работает в моем случае?»: когда a как дочерний элемент d освобождается, free_graph рекурсивно вызывает себя, чтобы освободить своих дочерних элементов, одним из которых является c, а один из дочерних элементов c указывает на a. В этом рекурсивном вызове память для a освобождается. Когда рекурсивные вызовы завершены, free_graph все еще находится в процессе освобождения a и вызывает free(*node) для a, но память для a уже освобождена при рекурсивном вызове.
Это не работает, потому что ваше «дерево» не соответствует вашей иллюстрации и на самом деле технически не является деревом. То, что у вас есть, выглядит так:
Вам нужно сделать копию вместо повторного использования узла, если вы хотите дерево.
Чтобы освободить все на таком графике, я бы предложил иметь отдельный связанный список, чтобы отслеживать все, что вам нужно освободить.
Если вы не хотите этого делать или не можете этого сделать по какой-либо причине, все становится сложнее. Выполнение операции для всех узлов в дереве тривиально, но для общего ориентированного графа это немного сложнее. Я думаю, этот ответ может помочь, а если нет, то, по крайней мере, даст вам представление о том, что искать:
Поиск списка всех узлов в ориентированном графе
Я предполагаю, что вы могли бы сделать что-то вроде этого псевдо:
getAllNodes(root, nodes)
if root // NULL check
if not node in nodes // If it's the first time we visit the node
// Add this node to the list of visited nodes
nodes = nodes + [root]
// And then call this function recursively on the children
getAllNodes(root->left, nodes)
getAlLNodes(root->right, nodes)
nodes = []
getAllNodes(root, nodes)
for node in nodes
free(node)
У деревьев есть приятная особенность: они никогда не содержат петель. Но ориентированные графы это делают, поэтому вам нужно проверить, не посещался ли уже узел. Обратите внимание, что для того, чтобы это работало, его нужно вызывать из корня. Или, если быть более точным, каждый узел должен быть доступен из узла. Но это не так уж отличается от дерева.
Я думаю, вы могли бы каким-то образом переместить свободную часть внутрь, чтобы создать функцию freeAllNodes(), но это более гибко. Возможно, вам нужен список для других целей. Поэтому мое предложение в таком случае — просто сделать freeAllNodes() звонок getAllNodes().
Я мог бы написать реализацию вышеописанного, но, поскольку C не предоставляет библиотечных функций для связанных списков, это означало бы включение большого количества дополнительного кода.
Что я могу сделать, чтобы график, который я хочу создать, соответствовал моей иллюстрации? Я хотел бы избежать создания копии, так как это усложнило бы дальнейшую работу.
Вы действительно хотите использовать один и тот же узел дважды? Или вы хотите использовать одно и то же значение дважды?