c - 函数 && 链表

Question

我已经尽力使用这个程序，但我不知道错误在哪里？？我会解释这个程序。在这个程序中，我应该将整数堆栈实现为链表，使用全局变量指向堆栈的顶部，方法如下:

int push(int i);

将i入栈，成功则返回1，否则返回0。

int pop();

从栈中弹出数字。栈空则返回0；

我确实创建了新方法调用 int stackEmpty(); 和上面的两个方法。

每次我运行我的程序时，它都会将数字压入堆栈，但弹出不起作用。这是我的代码:::

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

typedef struct stack Stack;
struct stack
{
    int number;
    Stack *next;
};
Stack *top = NULL;

int push(int i);
int count();
int stackEmpty();
int pop();

int main()
{
    char op;
    int i, x;
    printf("Welcome to my stack\n");
    printf("p to pop, s to push, c to count, q to quit\n");

    while (op != 'q')
    {
        scanf("%c", &op);
        if (op == 'p')
        {
            x = pop();
            if (x == 0)
            {
                printf("Stack is empty\n");
            }
            else
            {
                printf("%d popped\n", pop());
            }
        }
        else if (op == 'c')
        {
            i = count();
            printf("%d  numbers on stack\n", i);
        }
        else if (op == 's')
        {
            printf("Enter number: ");
            scanf("%d", &i);
            x = push(i);
            if (x == 1 || x == 2)
            {
                printf("%d puched :: state%d\n", i, x);
            }
            else
            {
                printf("faill %d\n", x);
            }
        }
        else if (op == 'q')
        {
            return 0;
        }
    }
    return 0;
}

int stackEmpty()
{
    if (top == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int count()
{
    int counter = 0;
    if (top == NULL)
    {
        return counter;
    }
    else
    {
        while (top != NULL)
        {
            top = top->next;
            counter++;
        }
        return counter;
    }
}

int push(int i)
{
    Stack *head;
    Stack *next;
    Stack *new;
    int state;
    int m;
    head = top;

    new = (Stack *) malloc(sizeof(Stack));
    if (new == NULL)
    {
        state = 0;
    } new->number = i;
    m = stackEmpty();

    if (m == 1)
    {
        head = new;
        top = head;
        head->next = NULL;
        state = 1;
    }
    else
    {
        while (head != NULL)
        {
            if ((next = head->next) == NULL)
                next = new;
            next->next = NULL;
            state = 2;
            break;
            head = top->next;
            next = head->next;
        }
        top = head;
    }
    return state;
}

int pop()
{
    Stack *head;
    int state;
    int m;
    head = top;

    if (head == NULL)
    {
        state = 0;
    }
    m = stackEmpty();

    if (m == 1)
    {
        state = 0;
    }
    else
    {
        state = head->number;
        top = head->next;
        free(head);
    }
    return state;

}

Answer 1

几个问题:

1. top 是我假定的堆栈的头。在 count 中，您会提升 top 直到它为 NULL - 因此，一旦您调用 count，您就“丢失”了堆栈。
2. 堆栈是一个 LIFO 队列(后进先出)。您的推送将通过在末尾附加新元素来实现 FIFO(先进先出)。
3. 您的推送实际上并未向列表中添加任何内容。您只是将 new 分配给 next 但您并未从列表中的任何位置指向 next。
4. 当使用 pop 时，您调用了两次(一次用于删除元素，一次用于打印)。因此，每当您沿着该代码路径前进时，您都会删除两个元素。更好的实现是编写一个 peek 函数，它返回顶部元素而不删除它，而 pop 函数只是简单地删除它(用 1 表示成功，用 0 表示失败)

堆栈的推送是这样的:

• 创建一个新元素
• 指向你当前的头部作为下一个元素
• 让你的新元素成为堆栈的新头部

不需要循环。这是一个 O(1) 操作。