C语言链表实现栈：调用push/pop后display无限输出或无输出求助

我用C语言基于链表实现栈，通过create函数直接从数组初始化栈，而非逐个调用push。但调用pop或push后执行display时，会出现无限输出，部分编译器甚至无输出。已在DevC++和在线GDB测试，排除环境问题，求排查代码问题。

原代码如下：

#include <stdio.h>
#include <stdlib.h>

struct stackLinkedList
{
    int data;
    struct stackLinkedList *next;
} *top=NULL;

void create(int A[],int size)
{
    top=(struct stackLinkedList*)malloc(sizeof(struct stackLinkedList));
    top->data=A[0];
    top->next=NULL;
    struct stackLinkedList *temp=NULL;
    for(int i=1;i<size;i++)
    {
        temp=(struct stackLinkedList*)malloc(sizeof(stackLinkedList));
        temp->data=A[i];
        temp->next=top;
        top=temp;
    }
}

void display(struct stackLinkedList *iterator)
{
    while(iterator!=NULL)
    {
        printf("%d ",iterator->data);
        iterator=iterator->next;
    }
}

bool isEmpty(struct stackLinkedList *top)
{
    if(top==NULL) return true;
    else return false;
}

bool isFull()
{
    struct stackLinkedList *temp=(struct stackLinkedList*)malloc(sizeof(stackLinkedList));
    if(temp==NULL) return true;
    else return false;
}

void push(struct stackLinkedList *top,int data)
{
    if(isFull()) 
    {
        printf("cannot push more values, memory is full!");
    }
    else
    {
        struct stackLinkedList *temp=(struct stackLinkedList*)malloc(sizeof(stackLinkedList));
        temp->data=data;
        temp->next=top;
        top=temp;
    }
}

int pop(struct stackLinkedList *top)
{
    struct stackLinkedList *temp=(struct stackLinkedList*)malloc(sizeof(stackLinkedList));
    if(temp==NULL) return NULL;
    else
    {
        int temporary=top->data;
        struct stackLinkedList *temp=top;
        top=top->next;
        free(temp);
        temp=NULL;
        return temporary;
    }
}

int main()
{
    int A[]={1,3,5,7,9};
    create(A,5);
    display(top); printf("\n");
    printf("deleted value is: %d\n",pop(top));
    display(top); printf("\n");
    return (0);
}

问题根源及修复方案 #

1. push/pop函数无法修改全局top指针

全局变量top是栈的头节点指针，但push和pop的参数top是局部变量，函数内修改这个局部变量不会影响全局的top。执行pop后，全局top仍指向已被free的节点，display访问野指针，导致无限输出或无输出。

修复：将函数参数改为指针的指针（struct stackLinkedList **top），通过*top修改全局头节点：

void push(struct stackLinkedList **top, int data)
{
    if(isFull()) 
    {
        printf("cannot push more values, memory is full!\n");
        return;
    }
    struct stackLinkedList *temp=(struct stackLinkedList*)malloc(sizeof(struct stackLinkedList));
    temp->data=data;
    temp->next=*top;
    *top=temp;
}

int pop(struct stackLinkedList **top)
{
    if(isEmpty())
    {
        printf("Stack is empty, cannot pop!\n");
        return -1;
    }
    struct stackLinkedList *temp=*top;
    int temporary=temp->data;
    *top=(*top)->next;
    free(temp);
    return temporary;
}

调用时传入全局top的地址：pop(&top)、push(&top, 11)

2. pop函数逻辑错误与内存泄漏

pop开头的malloc完全多余，会造成内存泄漏；且用temp==NULL判断栈空是错误的，应该用isEmpty函数判断栈是否为空，避免访问空指针。

修复：删除多余的malloc，先判断栈空再执行弹出操作，返回-1作为栈空的标识（因为int类型不能返回NULL）。

3. create和isFull函数中的类型错误

malloc(sizeof(stackLinkedList))缺少struct关键字，C语言中结构体标签必须加struct才能作为类型使用（除非用typedef定义别名）。

修复：统一改为malloc(sizeof(struct stackLinkedList))，同时isFull中要释放临时分配的内存，避免泄漏：

bool isFull()
{
    struct stackLinkedList *temp=(struct stackLinkedList*)malloc(sizeof(struct stackLinkedList));
    if(temp==NULL)
    {
        return true;
    }
    free(temp);
    return false;
}

4. isEmpty函数参数冗余

全局top可以直接访问，无需传参，简化函数：

bool isEmpty()
{
    return top == NULL;
}

5. 缺少bool类型头文件

使用bool类型需要包含<stdbool.h>，否则部分编译器会报错。

修正后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct stackLinkedList
{
    int data;
    struct stackLinkedList *next;
} *top = NULL;

void create(int A[], int size)
{
    top = (struct stackLinkedList*)malloc(sizeof(struct stackLinkedList));
    top->data = A[0];
    top->next = NULL;
    struct stackLinkedList *temp = NULL;
    for(int i = 1; i < size; i++)
    {
        temp = (struct stackLinkedList*)malloc(sizeof(struct stackLinkedList));
        temp->data = A[i];
        temp->next = top;
        top = temp;
    }
}

void display(struct stackLinkedList *iterator)
{
    while(iterator != NULL)
    {
        printf("%d ", iterator->data);
        iterator = iterator->next;
    }
}

bool isEmpty()
{
    return top == NULL;
}

bool isFull()
{
    struct stackLinkedList *temp = (struct stackLinkedList*)malloc(sizeof(struct stackLinkedList));
    if(temp == NULL)
    {
        return true;
    }
    free(temp);
    return false;
}

void push(struct stackLinkedList **top, int data)
{
    if(isFull())
    {
        printf("cannot push more values, memory is full!\n");
        return;
    }
    struct stackLinkedList *temp = (struct stackLinkedList*)malloc(sizeof(struct stackLinkedList));
    temp->data = data;
    temp->next = *top;
    *top = temp;
}

int pop(struct stackLinkedList **top)
{
    if(isEmpty())
    {
        printf("Stack is empty, cannot pop!\n");
        return -1;
    }
    struct stackLinkedList *temp = *top;
    int temporary = temp->data;
    *top = (*top)->next;
    free(temp);
    return temporary;
}

int main()
{
    int A[] = {1,3,5,7,9};
    create(A,5);
    display(top); printf("\n");
    printf("deleted value is: %d\n", pop(&top));
    display(top); printf("\n");
    push(&top, 11);
    display(top); printf("\n");
    return 0;
}

内容的提问来源于stack exchange，提问作者Argav