C语言链表销毁函数

Question

我正在尝试学习C语言，就像许多人一样，我在指针方面遇到了一些困难。无论如何，我创建了一个递归函数来销毁我的链表，但是我调试时发现，当函数返回后，链表的头并不是Null，而应该是Null的，所以我猜测这是关于指针的一些基本误解。以下是这个函数的代码：

void destroy(struct node *n) {
   if (!n) return;
   destroy(n->next);
   free(n);
   n = NULL;
}

- C. Porto

---

n是一个局部变量，所以n = NULL只有局部影响，也就是说它根本没有任何影响，因为它在函数末尾。 - ruakh

请展示一些代码，证明头部不为空。 - Oliver Charlesworth

深入探讨@ruakh所说的，如果你想修改一个指针，你必须传递一个指向该指针的指针（即struct node **），就像你想修改其他任何东西一样，你必须传递一个指针。 - Dennis Meng

我以为使用指针不会产生局部变量的影响...看来我还不知道如何实现... - C. Porto

@C.Porto 指针也是局部变量。 - Dennis Meng

不要使用递归。有更好的方法使用循环，你将获得更好的性能。 - Ed Heal

Answer 1

void deleteList(struct node** head_ref)
{  
  struct node* current = *head_ref;
  struct node* next;
  while (current != NULL) {
    next = current->next;
    free(current);
    current = next;
  }
  *head_ref = NULL;
}

试试这样做...你可以根据需要更改名称。如果你还需要帮助，请让我知道。

- spt025

---

避免使用递归（如果大小足够大，则会导致堆栈溢出），建议使用其他方法。 - Mats Petersson

@Mats：他从http://breakinterview.com/write-a-function-to-delete-a-linked-list/抄袭了这个答案。更有甚者，他甚至没有尝试用自己的技术术语来解释问题和解决方案。很明显，这个答案只是他在谷歌上幸运地找到的一堆代码，再加上一个怀疑的“试试这个……”。 - BalusC

@BalusC head_ref 是列表的起始点...然后下一个指针指向当前的下一个，之后空间被释放并且当前指向下一个，下一个指向当前的下一个地址。 同时不断检查它是否为空...;) 我没有运气，我知道我写了什么...否则我就不会写了，FYI它没有使用递归，这是显而易见的，这就是为什么我喜欢Ed Heal的评论。 - spt025

如果将 struct node* next; 更改为 struct node* next = current->next; 并替换 while 循环的第一行，这段代码会有什么不同吗？ - Hatefiend

Answer 2

当此函数结束时，头指针已被释放，但它不是空指针。在C语言中，所有内容都是按值传递的。因此，在调用"destroy"函数时，将head的位置的副本传入。该内存被释放，但head没有改变。

你可以这样编写代码：

destroy(&head);

void destroy(struct node** n){
   if(!*n) return;
   destroy(&((*n)->next));
   free(*n);
   *n = NULL; 
}

- dcaswell

Answer 3

您需要使用指向列表的指针，并调用destroy(&n)来进行操作：

// clear complete list 
void destroy(struct node **n)
{
    if (*n == NULL)
        return;

    if ((*n)->next == NULL)
    {
        free(*n);
        *n= NULL;
        return;
    }

    struct node *iter = *n;
    struct node *prev = NULL;

    // get last item and the previous one
    while (iter->next != NULL)
    {
        prev = iter;
        iter = iter -> next;
    } 

    prev->next = NULL;
    free(iter);

    destroy(n);
}

希望这能对你有所帮助。

- pzaenger

---

你对 clear() 的调用不太清楚；你是想再次调用 destroy() 吗？在释放某些东西之前找到结尾并再次以简单的尾递归方式调用函数的循环似乎有点奇怪。我认为它会工作（我没有测试过），但原始代码使用递归而没有循环更简单 - 尽管它可能比你的代码递归更深。 - Jonathan Leffler

哦，我的错。确实应该是destroy()。是的，我的函数有点绕弯子，我会看一下这里发布的其他解决方案来改进我的函数。不过，它确实有效 ;) - pzaenger

Answer 4

您的递归destroy函数无法修改调用者框架中的head变量。

语句n = NULL仅影响函数参数，它是destroy函数的局部变量。实际上，它没有任何效果，因此可以删除此语句。

如果需要在调用函数中使用，则应在调用destroy后将head设置为NULL。

- chqrlie

Answer 5

这是使用 DeleteRear() 销毁链表的示例函数：

void Destroy_Using_Rear(List *L)
{
    int y;
    Node *P,*Q,*Z;

    while(P!=NULL){
        y=DeleteRear(L,x);
        return y;
        Z=P;
        P=*L;
    }
}

- ahmad delea