如何释放链表中的节点？

Question

我该如何释放在另一个函数中分配的节点？

struct node {
    int data;
    struct node* next;
};

struct node* buildList()
{
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;

    head = malloc(sizeof(struct node));
    second = malloc(sizeof(struct node));
    third = malloc(sizeof(struct node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    return head;
}  

我在main()函数中调用了buildList函数。

int main()
{
    struct node* h = buildList();
    printf("The second element is %d\n", h->next->data);
    return 0;
}  

我想要释放头部、第二个和第三个变量。
谢谢。

更新：

int main()
{
    struct node* h = buildList();
    printf("The element is %d\n", h->next->data);  //prints 2
    //free(h->next->next);
    //free(h->next);
    free(h);

   // struct node* h1 = buildList();
    printf("The element is %d\n", h->next->data);  //print 2 ?? why?
    return 0;
}

两行代码都打印2。调用free(h)不应该删除h吗？如果是这样，为什么h->next->data仍然可以使用，如果h已经被释放了呢？当然，“second”节点没有被释放。但是既然头部已经被删除了，就应该能够引用下一个元素。这里出了什么问题？

- user235273

---

你在解除元素链接或释放它们方面遇到了问题吗？如果是后者，你需要使用从malloc()返回的值来调用free()。 - vhallac

free()函数并不会擦除内存的内容，它只是允许这些内容稍后被重用。指针h->next之所以仍然有效是因为你free()的那块内存尚未被重用，这只是巧合。 - Heath Hunnicutt

Luzhin：是的，这就是我想的。但请看更新后的main()函数。我运行了它，但不知何故我们的理论似乎不起作用。就像Heath Hunnicutt所说的那样，也许它仍然存在。但我仍然不明白为什么。 - user235273

@jase21 嗯，Heath已经回答了这个问题。当你尝试使用它时，它确实可以工作，但不能保证将来或在另一台机器上也能正常工作。在另一台机器上执行 h->next->data 可能会导致分段错误。好的，假设你有一个包含以下数据的 h：h->next = 0x12341281; h->data = 1，当你执行 free(h) 时，你只是让机器知道在未来的 malloc 中可以覆盖 h，即 h 不再被程序使用。但是数据 h->next = 0x12341281; h->data = 1 似乎仍然存在，这并不意味着你应该使用它们。 - insumity

@jase21 或许在未来的 malloc 中，会保存 h->next 和 h->data 之外的其他内容。那么当执行 h->next->data 时，可能会导致分段错误。 - insumity

Answer 1

一个迭代函数用于释放您的列表：

void freeList(struct node* head)
{
   struct node* tmp;

   while (head != NULL)
    {
       tmp = head;
       head = head->next;
       free(tmp);
    }

}

该函数的作用如下：

1. 检查head是否为NULL，如果是，则链表为空，直接返回

2. 将head保存在tmp变量中，并使head指向列表中的下一个节点（这在head = head->next中完成）

3. 现在我们可以安全地释放tmp变量，并且head仅指向列表的其余部分，回到步骤1

- insumity

---

在调用此函数后，请确保将链表头指针设置为null。实际上，在释放节点之前，将每个节点的下一个指针也设置为null是一个好主意。 - David R Tribble

如果节点中的数据也是使用 malloc 创建的，那么在释放 temp 之前，我们需要先释放它吗？例如：free(tmp->data); free(tmp); - Robert Cardona

是的，完全正确！如果你先释放了 tmp，那么 tmp->data 可能会指向垃圾值，导致段错误。 - insumity

也许更好的方法是通过引用传递头指针，并直接在FreeList函数中将指针设置为NULL。因此，它应该是void freeList（struct node ** head）{blah; blah; *head = NULL;}。这将避免David提到的问题。 - m_a_s

你们都忽略了一个非空头指针根本不会打破循环。 - Dario Rodriguez

Answer 2

仅需遍历列表即可：

struct node *n = head;
while(n){
   struct node *n1 = n;
   n = n->next;
   free(n1);
}

- elcuco

Answer 3

一个函数就可以完成这项任务。

void free_list(node *pHead)
{
    node *pNode = pHead, *pNext;

    while (NULL != pNode)
    {
        pNext = pNode->next;
        free(pNode);
        pNode = pNext;
    }

}

- Mehul

Answer 4

struct node{
    int position;
    char name[30];
    struct node * next;
};

void free_list(node * list){
    node* next_node;

    printf("\n\n Freeing List: \n");
    while(list != NULL)
    {
        next_node = list->next;
        printf("clear mem for: %s",list->name);
        free(list);
        list = next_node;
        printf("->");
    }
}

- Manolis

Answer 5

你可以像这样递归地完成它：

void freeList(struct node* currentNode)
{
    if(currentNode->next) freeList(currentNode->next);
    free(currentNode);
}

- Bradley Swain

---

递归看起来很不错，但实际上它的内存和CPU需求比像我或jase21所使用的简单循环大得多。当节点数为1328786时，展开堆栈的代价是不菲的。 - elcuco

@elcuco 我其实是同意的。就像问题所提供的情况，它会表现得很好，但如果你在处理如此大的列表时，毫无疑问，使用循环会让你处于更好的位置。 - Bradley Swain

这在能够进行尾递归的编程语言中是可以的。而 C 语言不行。 - Tomáš Nesrovnal

这段代码不是尾递归的。 (它在递归之后做了一些事情) 并且无法从尾递归优化中受益。 - HAL9000

我认为如果在一个空节点上调用此函数会导致错误。也许应该在定义的第一行放置一个空检查，而不是检查下一个节点是否为空？ - Brent Pappas

Answer 6

int delf(Node **head)
{
    if(*head==NULL)
    {
        printf("Empty\n");
        return 0;
    }
    else
    {
        Node *temp=*head;
        *head=temp->next;
        free(temp);
    }
    return 0;
}
 while(head!=NULL)
    {
        delf(&head);
    }

- 35 AK AMOGH.KULKARNI

---

你的回答可以通过提供更多支持性信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人能够确认你的回答是否正确。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - Community