c - 如何释放c中双向链表程序的内存

Question

过去几天我正在练习我的 c\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 direction\n");
    while(linkNode!=0)
    {
        printf("%d\n",linkNode->x);
        linkNode = linkNode->next;
    }


    linkNode = hdd->tl;
    printf("priniting in prev direction\n");
    while(linkNode!=0)
    {
        printf("%d\n",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) 调用 free(NULL) 因为 hdd->hd->prev == NULL (您设置第一个节点像这样明确地向上)。这很好，但什么也没做。
4. linkNode = linkNode->next 使 linkNode 指向最后一个节点
5. linkNode!=0 仍然为 true(最后一个节点也不为 NULL)，因此我们再次循环
6. free(linkNode->prev) 释放前一个节点(即第一个节点)
7. linkNode = linkNode->next 离开 linkNode == NULL
8. linkNode!=0 现在为 false，因此循环终止。

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