C语言中的简单栈程序

Question

我正在上一门操作系统课程，需要编写一个简单的栈程序（主要函数只是确定用户要求做什么）。如果不需要用C语言编写，我早就完成了，但由于我不太擅长C编程，它有一个“bug”...到目前为止，这个bug是它继续从中“弹出”相同的值。（实际上没有弹出任何东西）。我认为这是因为我不理解结构和指针如何工作。或者这是一个不太明显的编码错误？

#include <stdio.h>

struct node {
    int data;
    struct node *next;
    struct node *prev;
} first;

void push(int);
void pop();

int main(void)
{
    int command = 0;

    while (command != 3)
    {
        printf("Enter your choice:\n1) Push integer\n2) Pop Integer\n3) Quit.\n");
        scanf("%d",&command);
        if (command == 1)
        {
            // push
            int num;
            scanf("%d",&num);
            push(num);
        }
        else
        {
            if (command == 2)
            {
                pop();
            }
            else
            {
                if (command != 3)
                {
                    printf("Command not understood.\n");
                }
            }
        }
    }

    return 0;
}

void push (int x)
{
    struct node newNode;
    newNode.data = x;
    newNode.prev = NULL;
    newNode.next = &first;
    first = newNode;
    printf("%d was pushed onto the stack.\n", first.data);
}

void pop()
{
    if (first.data == '\0')
    {
        printf("Error: Stack Empty.\n");
        return; 
    }
    printf("%d was popped off the stack.\n", first.data);
    first = *(first.next);
    first.prev = NULL;
}

- Gary Ridgway

Answer 1

首先应该是一个指针。将其更改为struct node *first;

在main函数中初始化first=NULL;

将推入/弹出操作更改为以下内容：

void push (int x)
{
    struct node *newNode;// It should be a pointer
newNode = (struct node *)malloc(sizeof(struct node));
    newNode->data = x;
    //newNode.prev = NULL; // You don't need this
    newNode->next = first;
    first = newNode;
    printf("%d was pushed onto the stack.\n", first->data);
}

void pop()
{
struct node *prevPtr;
    //if (first.data == '\0')
    if (first == NULL) // check if stack is empty
    {
        printf("Error: Stack Empty.\n");
        return; 
    }

    printf("%d was popped off the stack.\n", first->data);
prevPtr = first;
    first = first->next;

free(prevPtr);
}

- surender8388

Answer 2

问题在于first是一个全局的单一node，并且它是你唯一拥有的node（除了在调用push时创建的临时本地node）。这行代码：

    first = newNode;

这段代码只是将newNode的内容复制到first中；由于newNode.next指向了first，这意味着现在first.next指向了first，因此你得到了一个只有一个元素的循环链表。

同样地，这行代码：

    first = *(first.next);

只是将*(first.next)的内容复制到first中; 这是一个无操作，因为（由于上面所述），*(first.next) 就是 first。

要解决这个问题，您实际上需要使用malloc（和free）动态创建节点。您的全局变量first应该是一个指针 - 一个node * - 它始终指向堆栈的顶部元素。（最好，您的push和pop函数应该将first作为参数，而不是作为全局变量。这些函数没有必要仅允许存在单个堆栈。）

- ruakh

Answer 3

&first 的值是多少？提示：由于 first 是静态分配的，因此始终相同。即使更改结构的内容，地址也不会改变。这可能告诉您为什么 push 中存在错误。如果要拥有大小可变的结构，则需要使用 malloc 和 free。

- Steve Howard

Answer 4

void pop()
{
struct node *prevPtr;
//if (first.data == '\0')
if (first == NULL)
{
    printf("Error: Stack Empty.\n");
    return; 
}

printf("%d was popped off the stack.\n", first->data);
prevPtr = first;
first = first->next;

free(prevPtr);
}

- Staunton Allen

Answer 5

当你需要自己管理内存时，就像C语言所要求的那样，你需要知道内存中被称为堆栈和堆的区别。(这个"堆栈"与你在程序中创建的数据结构略有不同。)

你的push()函数正在堆栈上创建一个新节点；当函数退出时，堆栈被弹出，你的新节点占用的内存就可以被使用了。你看到输入值的事实是由于你的程序非常简单。如果它调用其他执行其他任务的函数，它们几乎肯定会覆盖堆栈的那一部分，并且在调用pop()时，你会看到垃圾。

正如其他人所指出的，你需要使用malloc()和free()函数，它们从堆中提供内存，而不是从堆栈中提供。

- benzado

Answer 6

如果你想用链表来创建一个栈，需要将first变量作为指针。然后，当你将一个新节点推入栈中时，通过malloc()在堆内存上分配一个新的节点。我知道你打算使用它来指向栈顶，对吧？

在你的代码中，first变量被一个新节点覆盖了，因为它不是一个指针变量而是一个值变量。这导致栈顶的节点丢失。

- Kyokook Hwang

Answer 7

#include<stdio.h>

# define max 10

int stack[max],top=-1,size=0;

void push()

{

     if(top==(max-1))

     {

         printf("stack full\n");

     }

     else

     {

    top++;

    printf("enter the value which you want to insert\n");

    scanf("%d",&stack[top]);

     }

}

void pop()

{

int str;

if(top==-1)

        {

         printf("stack empty\n");

     }

     else

        {


    str=stack[top];

     top--;

    printf("the removed element is %d\n",str);

        }

}

void display()

{

 int i;

    for(i=0;i<top;i++)

    {

        printf("%d\n",stack[i]);

    }

}

void main()

{ 

int enter,x;

    do

    {

        printf("enter 1 for push the element in the array\n");

        printf("enter 2 for pop the element in the array\n");

        printf("enter 3 for display the element in the array\n");

        scanf("%d",&enter);

        switch(enter)

        {

        case 1:push();

        break;

        case 2:pop();

        break;

        case 3:display();

        break;

    default:

        printf("invalid syntax");

        }


         printf("for continue press 0\n");

        scanf("%d",&x);

    }

while(x==0);

}

- abhishek agrawal