Ошибка сегментации при чтении из стека

Question

Я впервые создаю стеки. Мне совершенно ясно, что я должен делать, но я совершенно обескуражен тем, что код не работает.

Он работает нормально, пока я не пытаюсь извлечь какие-либо данные из корня, что немедленно приводит к segfault.

Вот моя программа:

#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, вызывая сбой программы.

Правильный класс стека не должен использовать глобальные данные. Он должен заключать в себе все необходимое состояние в структурах. Это делает его многоразовым, позволяя создавать несколько стеков (свойство, которое я хотел бы использовать в большинстве классов, которые я использую).

Несколько других предложений:

• Избегать побочные эффекты , где это возможно. Отпечатки в порядке для целей временной отладки, но в противном случае их следует полностью отделить от логики программы.
• Если вы планируете писать обработчики ошибок, печатайте в stderr и избегайте магических значений, таких как return '\0';, которые могут быть ошибочно приняты зафактические данные узла.
• Не приводите результат 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;
}

Answer 2

Это действительно запутанный код (т. Е. Глобальные переменные с тем же именем, что и переменные в локальной области видимости). Я просто собираюсь переписать это, не проверено и на мобильном телефоне, но должно быть в порядке. Вы можете посмотреть разницу, чтобы увидеть проблемы. Во-первых, хотя вы устанавливаете локальную переменную root на самое новое размещение, а не на глобальный root.

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

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

stackNode* kTailStack = NULL;

void push(char data)
{
    stackNode* p=(stackNode *)malloc(sizeof(stackNode));
    p->letter=data;
    p->prev=kTailStack;
    kTailStack = p;
}

char pop()
{
    stackNode* prev_tail = kTailStack;
    char n = 0;

    if (prev_tail != NULL)
    {
        n = prev_tail->letter;
        kTailStack = prev_tail->prev;
        free(prev_tail);
    }

    return n;
}

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

    printf("%c %c %c", pop(kTailStack), pop(kTailStack), pop(kTailStack));
}