c - 从堆栈读取时出现段错误

Question

这是我第一次创建堆栈。我很清楚我必须做什么，但是代码不起作用让我很沮丧。

它运行良好，直到我尝试从根检索任何数据，这立即导致段错误。

这是我的程序:

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

struct stackNode
{
    char letter;
    struct stackNode * next;    
};

int size=0;
int capacity=10;

struct stackNode * root=NULL;

void push(char data, struct stackNode * root)
{
    if(size==capacity)
    {
        printf("Error: Stack Overflow\n");
        return;
    }

    struct stackNode * new=(struct stackNode *)malloc(sizeof(struct stackNode *));
    new->letter=data;
    new->next=root;
    printf("%c,%u", new->letter, new->next);
    root=new;
    printf("%c,%u", new->letter, new->next);
    size++;
}

char pop(struct stackNode ** root)
{
    if(size==0)
    {
        printf("Error: Stack is Empty\n");
        return '\0';
    }

    printf("\npop*\n");

    char temp;
    printf("\n*\n");
    struct stackNode * tempad;
    printf("\n*\n");
    temp=(*root)->letter;
    printf("\n*\n");
    tempad=*root;
    printf("\n*\n");
    *root=(*root)->next;
    printf("\n*\n");
    free(tempad);
    printf("\n*\n");
    size--;
    return temp;
}

int main()
{
    push('c', root);
    push('v', root);
    push('n', root);

    printf("%c %c %c", pop(&root), pop(&root), pop(&root));
}

这是输出:

pop*

*

*
Segmentation fault

谁能指出错误？

Answer 1

主要问题是使用不必要的全局变量，这似乎会造成困惑。在 push , 参数类型为 struct stackNode *然而它被操纵就好像它指的是全局 root .但是root = new纯本地，对全局没有影响root .然而，size++ 确实影响全局范围。这会破坏堆栈的逻辑状态，以及您在 pop 开头的错误处理程序认为size == 3并且不提示。该函数然后尽职地取消引用 root , 使程序崩溃。

正确的栈类不应该使用全局数据。它应该将所有必要的状态封装在结构中。这使得它可重用，允许创建多个堆栈(这是我在使用的大多数类中想要的属性)。

其他一些建议:

• 避免side effects在可能的情况。打印可用于临时调试目的，但应与程序逻辑完全分开。
• 如果您打算编写错误处理程序，请打印到 stderr并避免像 return '\0'; 这样的魔法值这可能会被误认为是实际的节点数据。
• Don't cast the result of malloc .这可以抑制错误并且在视觉上很嘈杂。
• 硬编码 capacity感觉很随意。我不确定这样做有什么意义(但如果有，请将其添加到结构中)。如果每个节点内关于堆栈的元数据太多(理想情况下，应该没有)，创建一个 Stack结构以包含此元数据并将其指向实际的 stackNode链。
• 另一个堆栈设计点:malloc/free很慢。对于字符数据，一个带有 top 的简单数组指针将更快更容易实现。当 top >= capacity 时，您可以通过定期将数组加倍来摊销分配调用。并在top < capacity / 2时签约.

这里是一个快速重写(没有关于 Stack 包装器结构或数组的建议):

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

struct stackNode {
    char letter;
    struct stackNode *next;
    int size;
};

void push(char data, struct stackNode **root) {
    struct stackNode *new = malloc(sizeof(*new));
    new->size = *root ? (*root)->size + 1 : 1;
    new->letter = data;
    new->next = *root;
    *root = new;
}

char pop(struct stackNode **root) {
    if (!*root || !(*root)->size) {
        fprintf(stderr, "pop from empty stack\n");
        exit(1);
    }

    char popped = (*root)->letter;
    struct stackNode *cull = *root;
    *root = (*root)->next;
    free(cull);
    return popped;
}

int main() {  
    struct stackNode *root = NULL;
    push('c', &root);
    push('v', &root);
    push('n', &root);

    while (root) {
        printf("%c ", pop(&root));
    }

    puts("");
    return 0;
}