如何为c语言中的双链表程序释放内存

Question

过去几天我一直在学习我的c++技能。我在看我的数据结构书，然后我想为什么不实现双链表程序。我写了程序;令人惊讶的是，它也工作得很好，但是，我不确定我是否写对了。我不知道如何释放我分配的内存。请帮帮我，伙计们。

如果你们谁能解释一下这个"while(linkNode!=0)"，我将非常感激。

#include<stdio.h>
#include<malloc.h>
struct node
{
    int x;
    struct node * next;
    struct node * prev;
};
struct head
{
    unsigned int count;
    struct node * hd;
    struct node * tl;
};

void main()
{
    int i =0;
    struct node * linkNode;
    struct head *hdd;
    hdd = (head *)malloc(sizeof(head));
    linkNode = (node *) malloc(sizeof(node));
    hdd->count = 1;
    hdd->hd = linkNode;
    linkNode->prev = 0;
    linkNode->next = 0;
    linkNode->x = 0;

    for(;i<10;i++)
    {
        linkNode->next = (node *) malloc(sizeof(node));
        linkNode->next->prev = linkNode;
        linkNode = linkNode->next;
        linkNode->next = 0;
        linkNode->x = i;
        hdd->count+=1;
        hdd->tl = linkNode;
    }
    linkNode = hdd->hd;
    printf("priniting in next directionn");
    while(linkNode!=0)
    {
        printf("%dn",linkNode->x);
        linkNode = linkNode->next;
    }

    linkNode = hdd->tl;
    printf("priniting in prev directionn");
    while(linkNode!=0)
    {
        printf("%dn",linkNode->x);
        linkNode = linkNode->prev;
    }
    linkNode = hdd->hd;
    while(linkNode!=0)
    {
        free(linkNode->prev);
        linkNode = linkNode->next;
    }
    free(hdd);

}

Answer 1

你的链表看起来像这样:

+------+----+----+
| Head | hd | tl | ---------->--------
+------+----+----+                    
         |               ---->------   |           NULL
         |             /              |             |
     +------+-----+------+------+   +------+-----+------+------+
     | Node | x=0 | next | prev |   | Node | x=1 | next | prev |
     +------+-----+------+------+   +------+-----+------+------+
         |                  |                             |
                          NULL                          /
           -----------------------<----------------------

(我已将其简化为两个节点)。

现在，我们可以写出这段代码的作用:

linkNode = hdd->hd;
while(linkNode!=0) {
    free(linkNode->prev);
    linkNode = linkNode->next;
}

1. linkNode = hdd->hd使linkNode指向第一个节点
2. (linkNode!=0)是true(第一个节点不是NULL)，所以我们进入while循环
3. free(linkNode->prev)自hdd->hd->prev == NULL之后调用free(NULL)(您像这样显式地设置了第一个节点)。这很好，但是什么也做不了。
4. linkNode = linkNode->next使linkNode指向最后一个节点
5. linkNode!=0仍然为真(最后一个节点也不是NULL)，所以我们再次进行循环
6. free(linkNode->prev)释放前一个节点(这是第一个节点)
linkNode = linkNode->next离开linkNode == NULL
7. linkNode!=0现在为假，因此循环终止。

所以，我们释放了除最后一个节点外的所有节点。没有节点的prev成员指向该节点，因此调用free(linkNode->prev)永远不能释放它。但是，您可以通过hdd->tl释放它。

Answer 2

您已经按照与链表尾部相反的顺序释放了分配给链表节点的内存。这一行就是这样做的。

free(linkNode->prev);

程序中存在内存泄漏。列表中的最后一个节点未被释放。

只包含

free(linkNode);

在释放硬盘之前。

说明:

while(linkNode!=0)

这是为了确保您正在解引用NULL指针。因为解引用NULL指针可能导致undefined behaviours .

这些是解引用操作

linkNode->x
linkNode->prev