2

过去几天我正在研究我的 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);


}
4

2 回答 2

3

您的链接列表如下所示：

+------+----+----+
| 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)为真（第一个节点不为NULL），所以我们进入while循环
  3. free(linkNode->prev)调用free(NULL)以来hdd->hd->prev == NULL（您像这样明确设置第一个节点）。这很好，但什么也没做。
  4. linkNode = linkNode->next叶子linkNode指向最后一个节点
  5. linkNode!=0仍然为真（最后一个节点也不是 NULL），所以我们再次循环
  6. free(linkNode->prev)释放前一个节点（这是第一个）
  7. linkNode = linkNode->next树叶linkNode == NULL
  8. linkNode!=0现在是假的，所以循环终止。

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

于 2013-01-21T18:42:09.410 回答
1

您已经从链表尾部以相反的顺序释放分配给链表节点的内存。这条线正在这样做。

free(linkNode->prev);

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

只包括

free(linkNode);

在释放硬盘之前。

解释： 

while(linkNode!=0)

这是为了确保您取消引用NULL指针。由于取消引用 NULL 指针可能会导致undefined behaviours.

这些是取消引用操作

linkNode->x
linkNode->prev
于 2013-01-21T17:56:24.103 回答