c - 释放整个链表，这个算法正确吗？

Question

这可能吗？还是会有丢失的清单？因为我无法检查它是否工作

void FreeRecurs(struct nodeTag *pFirst)
{
    if(pFirst != NULL)
    {   
            FreeRecurs(pFirst -> pNext);
            free(pFirst);
    }
}

Answer 1

这会起作用，但是在长列表中，您可能会遇到堆栈溢出，因为您递归了很多并且没有使用尾递归。我会转向迭代版本：

• 虽然当前节点不为 NULL：
  • 存储指向下一个节点的指针。
  • 释放当前节点。
  • 使用您在释放之前存储的指针开始处理下一个节点。

Answer 2

理论上这没问题，但你可以通过使其尾递归来很大程度上改进它：

void FreeRecurs(struct nodeTag *pFirst)
{
    if(pFirst != NULL)
    {   
            struct nodeTag* const next = pFirst->pNext;
            free(pFirst);
            FreeRecurs(next);
    }
}

请注意，这FreeRecurs(next)是您函数中的最后一条语句。编译器会识别这一点，您的代码将运行得更快，并且不会冒破坏堆栈的风险。

除此之外，当您不确定是否丢失了内存时，您可以在valgrind（特别是在massif）中运行程序，它会告诉您是否丢失了内存。

Answer 3

该算法将起作用。也就是说，你应该学习使用类似的工具，valgrind或者gdb准确地监控你的代码发生了什么，这样你就可以判断它是否在工作。

Answer 4

我不会使用递归，而是使用这样的东西：

void FreeRecurs(struct nodeTag *pFirst)
{
    struct nodeTag *aux = NULL;
    while (pFirst != NULL)
    {   
        aux = pFirst;
        pFirst = pFirst -> pNext;
        free(aux);
    }
}

递归会导致堆栈溢出，实际上最终会变慢，因为每个函数调用都有一个新的调用堆栈，实际上是什么都没有创建。