c - 销毁(免费)链表式堆栈中的所有内容？

Question

//目前还不是一个非常成熟的LINK-Stack，我稍后会更新它。 当我遇到此错误时，我试图释放 linklist-style 堆栈中的每个节点:

根据方案一，这是一个可编译但不可执行的脚本。也许当我想为 (*S) 分配地址，但 (*S) 已经被释放时，我的问题发生了？

关于销毁函数，我想释放之前分配给(S)的RAM中的每个节点，使RAM可重用。

那为什么第一个功能不可用？？？

PS:我不知道如何在C中删除变量，我的意思是删除它的地址。也许通常的变量不能被FREE()释放？

PPS:当我使用free()时，我认为这只是释放RAM，但保留可能指向NULL或某个地方的变量的名称或标识符，这是危险的，但在解决方案1中，似乎我必须这样做。

//IDE:Dev C++ 5.11 
#include<stdio.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct Stack
{
    struct Stack *next;
    ElemType data;
} Stack,*LinkStack;

int InitStack(LinkStack *S) {
    *S = (LinkStack)malloc(sizeof(struct Stack));
    if(!*S) return -1;
    (*S)->next=NULL;
    (*S)->data =0;
    printf("Maybe successfully initialized.\n");
    return 0;
}

int Push(LinkStack *S, ElemType e)
{
    LinkStack pt = (LinkStack)malloc(sizeof(struct Stack));
    LinkStack newpt = (LinkStack)malloc(sizeof(struct Stack));
    newpt->data = e;
    pt = (*S)->next;
    int number = 0;

    if (!pt)
    {
        printf("#a one time \n");
        (*S)->next = newpt;
        (*S)->data++;
        return 1;
    }
    else
    {
        while (number < (*S)->data)
        {
            pt = pt->next;
            number++;
        }
        pt->next = newpt;
        newpt->next = NULL;
        (*S)->data++;
        return 0;
    }
}

int StackTraverse(LinkStack S)
{
    LinkStack pt = (LinkStack)malloc(sizeof(struct Stack));
    pt = (S)->next;
    while (pt)
    {
        printf("%d__", pt->data);
        pt = pt->next;
    }
    return 0;
}

Solution1:  //unavailable
void DestroyStack(LinkStack *S)
{
    while (*S)
    {
        LinkList pt = (*S)->next;
        free(*S);
        (*S) = pt;
    }
    printf("Node destroyed!\n");
}

int main()
{
    LinkStack Sb;
    InitStack(&Sb);
    ElemType *e = (ElemType *)malloc(sizeof(ElemType));
    while (scanf("%d", e))
    {
        Push(&Sb, *e);
        printf("you have entered : %d.\n", *e);
    }
    free(e);
    printf("%d\n", Sb->next->next->data);
    StackTraverse(Sb);
    DestroyStack(&Sb);
    if (!Sb)
    {
        printf("succeed\n");
    }
    return 0;
}

所以我想出了另一个函数!使用递归，但是当我向 linklist-style 堆栈中插入 3 个节点时，似乎“LinkStack 被破坏了”打印了6次。当我插入 4 个节点时，它会打印 7 次。

solution2:  //available ,but not work well
void DestroyStack(LinkStack *S) {
    while(*S){
        LinkStack pt=(*S);
        (*S)=(*S)->next;
        printf("#a\n");
        DestroyStack(S);
    }
    printf("LinkStack Destroyed!");
}

感谢您的帮助!

Answer 1

您的整个代码都有问题，也许是因为您不了解 malloc 和 free 的真正作用。

• malloc 分配一定大小的 block 并为您提供该内存的句柄。该句柄是一个指针。这意味着您仅在创建对象时调用malloc。在您的代码中，唯一应该调用它的地方是 Push，因为您创建了一个新节点。

• 您不需要为仅遍历堆栈的指针分配内存。特别是这样的:

  LinkStack pt = malloc(sizeof(struct Stack));
  pt = (S)->next;
  

  是错误的:您分配内存并通过分配给pt立即失去它的句柄。扔掉 malloc 并仅保留第二行。

• free 将先前分配的内存返回给系统。每个malloc都需要其相应的free。如果不这样做就称为内存泄漏。
• 一旦对指针调用了free，您就无法再访问其背后的数据。系统函数free不会将指针设置为NULL，所以这是你必须注意的事情。

• 空堆栈是没有节点的堆栈。因此分配虚拟节点是没有意义的。您的堆栈由指向其头节点的指针定义。您可以将此节点初始化为NULL:

  Stack *Sb = NULL;
  

  同样，您可以检查堆栈上是否还有项目:

  if (Sb) ...
  

• 这更多的是一个风格问题:typedef 消除指针性质被认为是不好的做法。您可以typedef该结构，但改为LinkStack，只需使用Stack *，这样乍一看就很明显您正在处理一个指针指向此处。

• 在 main 中，您执行以下操作:

  printf("%d\n", Sb->next->next->data);
  

  这很危险，因为你不知道用户是否至少输入了三个项目。在取消引用之前，您必须检查指针是否为 NULL。

我们来实践一下:推送的意思是创建一个新节点，并将其插入到头部，这样新的头部就是新节点:

typedef int ElemType;

typedef struct Stack Stack;

struct Stack {
    Stack *next;
    ElemType data;
};

void Push(Stack **S, ElemType e)
{
    Stack *newpt= malloc(sizeof(*newpt));

    newpt->data = e;
    newpt->next = (*S);
    *S = newpt;
}

您的代码实现了堆栈的破坏，但更常见的是，堆栈因弹出其中的项目而耗尽。那么让我们实现一下:

ElemType Pop(Stack **S)
{
    ElemType res;
    Stack *rem = *S;

    if (*S == NULL) {
        fprintf(stderr, "Stack underflow\n");
        exit(1);
    }

    res = (*S)->data;
    *S = (*S)->next;
    free(rem);

    return res;
}

请注意我们必须如何保留数据和旧指针的副本，因为释放数据会使其无法访问。

现在我们可以重写销毁函数:我们从堆栈中弹出项目，直到耗尽为止。

void DestroyStack(Stack **S)
{
    while (*S) Pop(S);
}

最后，一个不分配任何东西的遍历函数:

void StackTraverse(const Stack *S)
{
    while (S) {
        printf("%d ", S->data);
        S = S->next;
    }

    puts("");
}

该函数仅检查堆栈；它不会 mdofy，所以通过常量头指针就足够了。最后是主要功能:

int main(){
    Stack *Sb = NULL;        
    ElemType e;

    while (scanf("%d", &e) == 1){
        Push(&Sb, e);
    }

    StackTraverse(Sb);
    DestroyStack(&Sb);

    return 0;
}

元素类型只是一个int，因此为其动态分配内存有点大材小用。使用自动变量更容易。

该程序完成后，所有分配的 block 都将被释放。