Связанный стек в C. Pop вызывает ошибку сегментации, а Push - нет! - PullRequest
2 голосов
/ 08 июля 2010

Я делаю несколько простых вещей, так что, надеюсь, на этот вопрос легко ответить легко.Я использую GCC для компиляции.Толчок работает отлично.Проблема в популярности.Я получаю ошибку сегментации при компиляции и запуске.

Вот функции pop и push:

int push(stack *stk, int data)
{
    stk->head = makeNode(data, stk->head);
    stk->length += 1;
    return data;
}

int pop(stack *stk)
{
    //Returns popped item
    //Returns -1 if stack length is zero
    if (stk->length < 1)
    {
        printf("No items to pop.");
        return -1;
    }
    int data = stk->head->value;
    struct node *toBeFreed = stk->head;
    stk->head = stk->head->ptr;
    free(toBeFreed);
    stk->length -= 1;
    return data;
}

Честно говоря, я не знаю в чем проблема, потому что код похожЯ переназначаю переменную head в стеке в функции push, но это вызывает ошибки в функции pop.Присвоение данных также вызывает ошибку сегмента.Практически все, кроме операторов присваивания возвращаемого значения и длины стека, дает мне ошибки сегментации.Кто-нибудь из вас может помочь мне понять это?Что вызывает эти ошибки сегмента?

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

#include <stdio.h>
#include <stdlib.h>
struct node 
{
    int value;
    struct node *ptr;
};

struct node *makeNode(int value, struct node *ptr)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->value = value;
    newNode->ptr = ptr;
    return ptr;
}

typedef struct stack
{
    struct node *head;
    int length;
} stack;

stack makeStack()
{
    stack stk;
    stk.head=NULL;
    stk.length = 0;
    return stk;
}

int push(stack *stk, int data)
{
    stk->head = makeNode(data, stk->head);
    stk->length += 1;
    return data;
}

int pop(stack *stk)
{
    if (stk->length < 1)
    {
        printf("No items to pop.");
        return -1;
    }
    int data = stk->head->value;
    struct node *toBeFreed = stk->head;
    stk->head = stk->head->ptr;
    free(toBeFreed);
    stk->length -= 1;
    return data;
}

int main()
{
    stack s = makeStack();
    printf("Pushing ints one through five. Should display ints one through five on separate lines: \n");
    int i;
    for (i = 1; i <= 5; i++)
            printf("%d\n",push(&s, i));
    printf("Popping ten values. Should display ints one through five in reverse order on separate lines along with 5 error statements.\n");
    for (i = 0; i <= 10; i++)
            printf("%d\n",pop(&s));
    return 0;
}

Ответы [ 6 ]

8 голосов
/ 08 июля 2010
struct node *makeNode(int value, struct node *ptr)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->value = value;
    newNode->ptr = ptr;
    return ptr;
}

Вы хотите вернуть newNode, а не ptr.

Причина, по которой вы получаете ошибку segf, заключается в том, что из-за ошибки в makeNode стек останется пустым, однако sizeбудет увеличен до 5, поэтому, когда вы pop стек не знаете, что он пуст, и он пытается разыменовать нулевой указатель.

2 голосов
/ 08 июля 2010

sepp2k уже дал правильный ответ.Поэтому я просто добавляю несколько полезных советов.

Одним из способов, который может помочь вам найти подобные проблемы в более крупных программах, является инструмент под названием valgrind.Например, если вы скомпилируете:

$ gcc -Wall -Wextra -g linked_stack.c -o linked_stack

и затем выполните:

$ valgrind ./linked_stack

Вы получите следующий вывод:

==1503== Invalid read of size 4
==1503==    at 0x80484C6: pop (linked_stack.c:62)
==1503==    by 0x8048584: main (linked_stack.c:79)
==1503==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==1503== 
==1503== Process terminating with default action of signal 11 (SIGSEGV)
==1503==  Access not within mapped region at address 0x0
==1503==    at 0x80484C6: pop (linked_stack.c:62)
==1503==    by 0x8048584: main (linked_stack.c:79)

Это эффективно говорит вамчто оператор в строке 62:

int data = stk->head->value;

пытается использовать недопустимый указатель со значением 0x0.В этот момент вам просто нужно отследить и выяснить, почему этот указатель недействителен.

Дополнительная информация, предоставляемая компиляцией с -g для символов отладки и последующим запуском в valgrind, действительно может помочь вам отследить этивиды проблем в больших программах.

2 голосов
/ 08 июля 2010

Я предлагаю вам добавить проверку на пустые указатели в pop и push. Функция makeStack вызывает у меня дрожь, так как она возвращает локальную переменную.

Также советую внести следующие изменения:

struct stack * makeStack()
{
    struct stack * p_stk = 0;
    p_stk = (struct stack *) malloc(sizeof(struct stack);
    if (p_stk)
    {
      p_stk->head=NULL;
      p_stk->length = 0;
    }
    return p_stk;
}

Или

void makeStack(stuct stack * p_stack)
{
 // Initialize the stack ...
}
0 голосов
/ 08 июля 2010

Я не думаю, что вы возвращаете правильный узел в вашей функции makeode. Попробуйте

ptr = newNode;

прежде чем вернуться.

0 голосов
/ 08 июля 2010

Указатель вашей головы не изменяется при вызове функции makeNode.Вы должны указать на только что созданный узел.

0 голосов
/ 08 июля 2010

В makeNode вы создаете новый узел, указывая этому узлу переданное значение, а затем возвращая переданное значение вместо нового узла.Так как вы передаете stk->head, который начинается как NULL, каждый толчок всегда будет создавать новый узел, указывающий на NULL, а затем возвращать NULL, поэтому stk->head не меняется, как вы ожидаете.Когда вы всплываете, вы пытаетесь получить доступ к NULL->ptr и NULL->value, что, очевидно, не работает.

Если вы измените makeNode на:

struct node *makeNode(int value, struct node *ptr)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->value = value;
    newNode->ptr = ptr;
    return newNode; // pass back the new node
}

, он будет работать.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...