C 编程堆栈

Question

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

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() 的实际代码:

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 时出现段错误。这怎么行不通？我需要做什么才能使这个堆栈位于顶部？？？

Answer 1

推送功能错误。

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 */
}

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

如果您尝试修改 s 的值，它在函数外部是不可见的，并且您仍然拥有原始堆栈。

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

你可能想做这样的事情:

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)。

更快的实现看起来像这样:

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)。