代码之家 › 专栏 › 技术社区 › Daniel Wood

在C中释放双重链接列表

free memory c

Daniel Wood · 技术社区 · 14 年前

我在C中有一个双重链接的列表,我对如何释放它感到困惑。我知道我必须遍历列表以释放每个节点。混淆的地方在于我的每个节点都有一个指向其他数据的指针,我不确定该如何释放它。

我的双重链接列表如下:

typedef struct Node_ Node;
typedef struct List_ List;

struct Node_ {
    void *data;
    Node *next;
    Node *prev;
};

struct List_ {
    Node *firstNode;
    Node *lastNode;
};

为了释放列表,我创建了一个名为list_free()的函数,它遍历列表,用node_free()释放每个节点。这些函数如下所示:

void *List_free(List *list)
{
    Node *next = list->firstNode;

    while(next)
    {
        Node *node = next;
        next = node->next;
        Node_free(node);
    }

    free(list);
}

void Node_free(Node *node)
{
    free(node->data);
    free(node);
}

这将下降的地方是node->数据指向另一个本身包含指针的结构的指针。在我的例子中,我使用相同的列表代码来存储两个不同的结构。

在我看来,我有以下选择:

创建节点保存特定数据的列表。不太可重复使用。
找到另一种跟踪节点数据中指针的方法。

我是沿着正确的路线思考,还是错过了一些明显的东西?这是我在C的第一次尝试,所以如果这一切都是完全错误的,我不会感到惊讶。

8 回复 | 直到 14 年前

Johan Kotlinski 14 年前

一种解决方案是提供一个函数指针,负责正确释放节点。

typedef void(*NodeDataFreeFn)(void*);

列表自由修改如下:

void *List_free(List *list, NodeDataFreeFn data_free)
{
    Node *next = list->firstNode;

    while(next)
    {
        Node *node = next;
        next = node->next;
        (*data_free)(node->data);
        free(node);
    }
    free(list);
}

示例数据自由:

void data_free_fn(void* data_ptr) {
    // Add your custom stuff here.
    free(data_ptr);
}

列表自由调用示例:

List_free(my_list, data_free_fn);

如果不想通过参数传递无数据函数指针,可以将其存储到列表结构中,如下所示:

struct List_ {
   Node *firstNode;
   Node *lastNode;
   NodeDataFreeFn data_free;
};

免责声明:我没有测试这个代码,它可能有问题…

jv42 14 年前

你没有错,这是OOP特别是C++解决的问题之一。

您可以在结构中添加一个指向函数成员的指针,用于释放其数据。基本上用手添加C++析构函数。这样就可以保持遗传性而不会有太多的重复。

Bart van Ingen Schenau 14 年前

如果应用程序可以在列表中存储任意数据,那么应用程序也有责任安排适当的清理。
这可以通过两种方式实现:

呼叫前 List_free 应用程序必须清除列表中的所有元素。
将另一个参数添加到 免费列表 (和) Node_free ,这是指向删除程序函数的指针:
```
typedef void (deleter_t*)(void*);

void Node_free(Node* node, deleter_t deleter)
{
    if (deleter) (*deleter)(node->data);
    free(node);
}
```
对于不必显式释放的数据,应用程序可以传递一个空删除程序,用于可以使用单个 free 调用,该函数可以作为deleter传递。对于更复杂的数据,应用程序必须传递执行正确操作的函数。

Gintautas Miliauskas 14 年前

正如问题所示,您的问题不在双重链接列表中,而是在复合动态结构中。这就是手动内存管理的工作原理:您必须跟踪已分配的内容。最好每次都坚持使用相同结构的节点数据,这样预定义的例程就可以释放它。或者,在结构上使用标记并在运行时切换标记以在不同结构的解除分配例程之间进行选择(或者只使用函数指针来模拟C++析构函数)。

pmg 14 年前

hmmm:创建 Data_free 函数并为数据指针调用它。

void Data_free(void *ptr)
{
    /* first identify what data type ptr really is */
    /* and then deallocate memory used by ptr */
}

void Node_free(Node *node)
{
    /*free(node->data);*/
    Data_free(node->data);
    free(node);
}

编辑: 改变 struct Node_ 定义,使其更类似于C++类:

struct Node_ {
    void *data;
    void (*freedata)(void*);
    struct Node_ *next;
    struct Node_ *prev;
}

sanjoyd 14 年前

您可能想要尝试的一种方法是实现内存池;如果您不打算单独释放节点,那么实现内存池就非常简单。

简单地 malloc (或) mmap 可能是为了 /dev/zero )一个大的块,然后您可以通过一个简单的指针加法为一个节点“分配”内存。那么,取消整个列表的分配就是 free ING(或 munmap ing)大块。

如果操作正确,这也可能会稍微提高性能。

Robie Basak 14 年前

正如其他人所说,您已经确定了一些在C语言中手工操作是很痛苦的事情,但是必须要做。您可以使用函数指针使释放机制成为数据的通用机制,但是您仍然必须实现该机制,以便在每个节点中沿着数据的层次结构向下移动,以释放所有内容。

这是一个很好的练习,值得为学习体验而做。

但是还有一个非常有用的库可以为您处理所有这些问题: talloc . 它为您跟踪层次结构,因此释放顶层会自动释放底层的所有内容。它有很好的记录。它是为桑巴开发的,现在仍在那里使用,所以维护得很好。

Mike Dunlavey 14 年前

问题不在于清单上 prev 指针。问题是每种不同的 Node 删除内容的方式不同。

所以需要有一个通用的 Node_free 例程(您拥有),它需要在节点类型上调度。因此,要么节点需要包含一个通用类型代码,要么它需要包含一个指向为该节点类型定制的析构函数例程的指针。

无论哪种方式,你基本上都在做C++所做的事情。