C编程栈

Question

我现在正在做栈的工作。我应该使用以下结构和函数原型：

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还没有分配给它空间(因为您将其设置为NULL)，您仍然可以访问stack->data成员。实际上，您在之后设置了它，这很可能就是它崩溃的原因。

您可能想要这样做：

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++;
}

正如前面提到的，这只是一个单链表，它不是最适合堆栈的，因为它现在存在，你必须跟随节点指针到达最后一个元素，这使得推送和弹出操作为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)。

Answer 2

遵循您的代码....

stack *newStack = create_stack();   // in push()
    newStack = malloc(sizeof(stack)); // in create_stack()
    newStack->stack = NULL; // in create_stack()
newStack->stack->data = val; // in push()... this is where you crash.

Answer 3

因为newStack->stack是一个空指针。您的create_stack()函数将其设置为NULL，然后取消对它的引用。你必须在某个地方分配一个struct node。

这段代码也有一些可读性问题，这可能是导致问题的原因之一。您将变量命名为与其类型相同的名称，这非常令人困惑。考虑使用其他一些命名模式，比如类型使用stack_t，变量名使用stack。