C 编程堆栈 [英] C Programming Stack

问题描述

我目前正在研究堆栈.我应该使用以下结构和函数原型:

I am currently working on stacks right now. I am supposed to use the following structures and function prototypes:

typedef struct node_{
    char data;
    struct node_ *next;
}node;

typedef struct stack_{
    unsigned int size;
    node* stack;
}stack;

stack* create_stack();
void   push(stack* s, char val);

这是我的 create_stack() 和 push() 实际代码:

Here is my actual code for create_stack() and push():

stack* create_stack()
{
    stack *stack;
    stack = malloc(sizeof(stack));
    stack->size = 0;
    stack->stack = NULL;
    return stack;
}

void push(stack* s, char val)
{
    stack *newStack;
    newStack = create_stack();
    newStack->stack->data = val;
    newStack->stack = s->stack;
    s = newStack;
}

当我尝试将 char val 存储到 newStack->stack->data 时出现分段错误.这怎么行不通?我需要做什么才能使这个堆栈在顶部???

I am getting a segmentation fault when I try to store char val into newStack->stack->data. How does this not work? What do I need to do to make this stack on top???

推荐答案

推送功能有误.

void push(stack* s, char val)
{
    stack *newStack;
    newStack = create_stack(); /* new stack created, why not work on the existing one ? */
    newStack->stack->data = val; /* you're writing to a NULL pointer */
    newStack->stack = s->stack;
    s = newStack; /* this will not be visible from outside the function */
}

首先，您试图为该函数的每次调用重新创建一个新堆栈，这当然不是预期的.

First of all, you are trying to recreate a new stack for each call of this function, which is certainly not what is intended.

如果你尝试修改s的值，它在函数外部是不可见的，你仍然拥有你原来的堆栈.

If you try to modify the value of s, it will not be visible from outside the function, and you will still have your original stack.

然后，您正在访问 stack->data 成员，即使 stack 尚未为其分配空间(因为您将其设置为 NULL).您实际上是在之后立即设置的，这就是它崩溃的原因，很可能.

Then, you are accessing the stack->data member even though stack has no space allocated to it yet (because you set it to NULL). You actually set it right after, which is why it crashes, most probably.

你可能想做这样的事情:

You probably want to do something like this:

void push(stack* s, char val)
{
    node * n;

    /* go to the end of the "stack" */
    n = s->stack;
    while (n != NULL) {
        n = n->next;
    }

    /* allocate memory for a new node */
    n = malloc(sizeof(node));

    /* initialize node */
    n->data = val;
    n->next = NULL;

    /* increment stack size */
    s->size++;
}

而且如前所述，这只是一个单向链表，不是最适合堆栈的，因为它现在存在，你必须跟随节点指针到达最后一个元素，这使得 push 和 pop操作 O(N).

And as mentionned before, this is merely a singly-linked list which is not the best fit for a stack, because as it exists now, you have to follow the node pointers to reach the last element, which makes push and pop operations O(N).

更快的实现如下所示:

void push(stack* s, char val)
{
    node * first_node, * new_node;
    first_node = s->stack;

    /* allocate memory for a new node */
    new_node = malloc(sizeof(node));

    /* initialize node */
    new_node->data = val;
    new_node->next = first_node;

    /* increment stack size */
    s->stack = new_node;
    s->size++;
}

栈顶总是第一个节点，性能O(1).

The top of the stack is always the first node, and the performance is O(1).

这篇关于C 编程堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！