Почему я получаю ошибку сегмента с этим кодом? Должно быть просто?

Question

Я в полной растерянности.Я чувствую, что здесь должна быть какая-то явная, глупо легкая ошибка, и мои глаза слишком устали, чтобы это увидеть.Буду очень признателен за любую помощь.

Когда я запускаю testProb2, программа печатает «Pushing:», а затем на следующей строке «Ошибка сегментации».Я нахожу это действительно странным, потому что следующая вещь после printf ("Pushing: \ n");это еще один вызов printf с передачей только статического аргумента, ничего динамического, что могло бы делать странные сумасшедшие вещи в каком-то другом методе, и все же «1» не печатается.

Я положил вызов printf для1 и 2 там просто как тест, потому что я изначально думал, что проблема может быть в моем первом цикле for, который закомментирован прямо сейчас, но это не так.Как я уже сказал, я считаю, что проблема в testProb2.c, но на всякий случай я включил stackli.h и stackli.c под ним.Я компилирую это с помощью "gcc -ansi stackli.c testProb2.c -o testProb2".

/* testProb2
 * 
 * Demonstrates a stack implementation that allocates a number of nodes at creation of the stack
 * rather than on each call to Push. All methods are O(1) except for GrowFreeList, which is O(n),
 * and CreateStack, which is O(n) because it calls GrowFreeList, and possibly Push, which will be
 * O(1) when called while there are empty nodes, but O(n) when called if there are not empty nodes.
 */

#include "stackli.h"
#include <stdio.h>

int main(void) {
    Stack S;
    int i;

    S = CreateStack(8);

    printf("Pushing:\n");
    printf("1 ");
    Push(1, S);
    printf("2\n");
    Push(2, S);
                /*
                for (i = 0; i < 10; i++) {
                    printf("%d...", i);
                    Push(i, S);
                }
                printf("]\n");
                */

    printf("Popping:\n");
    while (!IsEmpty(S)) {
        printf("%d...", Top(S));
        Pop(S);
    }
    printf("]");
    DisposeStack(S);
}
/* stackli.h */

    typedef int ElementType;

    #ifndef _Stack_h
    #define _Stack_h

    struct Node;
    struct StackRecord;
    typedef struct Node *PtrToNode;
    typedef struct StackRecord *Stack;

    Stack CreateStack( int initialSize );
    void GrowFreeList( Stack S );
    int IsEmpty( Stack S );
    int IsFull( Stack S ) ;
    void MakeEmpty( Stack S );
    void DisposeStack( Stack S );
    void Push( ElementType X, Stack S );
    ElementType Top( Stack S );
    void Pop( Stack S );


    #endif  /* _Stack_h */
/* stackli.c */

#include "stackli.h"
#include "fatal.h"
#include <stdlib.h>

struct StackRecord {
    PtrToNode ThisStack;
    PtrToNode FreeNodes;
    int Size;
};

struct Node {
    ElementType Element;
    PtrToNode   Next;
};

/* O(n) instead of O(1) because it calls GrowFreeList which is O(n) */
Stack CreateStack(int initialSize) {
    Stack S;
    S = malloc( sizeof( struct StackRecord ) );
    S->ThisStack = NULL;
    S->FreeNodes = NULL;
    S->Size = initialSize;            
    GrowFreeList(S);
    return S;
}

/* O(n) function */
void GrowFreeList(Stack S) {
    int i;
    PtrToNode temp;

    for (i = 0; i < S->Size; i++) {
        temp = malloc( sizeof( struct Node) );
        if (temp == NULL)
            FatalError("Out of space!!");
        temp->Next = S->FreeNodes;
        S->FreeNodes = temp;
    }
    S->Size = S->Size * 2;
}

Answer 1

Проблема в последних двух строках Push:

void Push( ElementType X, Stack S ) {
    PtrToNode temp;
    ...
    temp->Next = S->ThisStack->Next;
    S->ThisStack = temp;
}

При первом вызове Push поле ThisStack пусто.Когда вы пытаетесь разыменовать его для доступа к его полю Next, вы получаете ошибку сегмента.Однако, поскольку вершина стека находится в ThisStack, а не ThisStack->next, исправление этой проблемы избавит от segfault.

void Push( ElementType X, Stack S ) {
    PtrToNode temp;
    ...
    temp->Next = S->ThisStack;
    S->ThisStack = temp;
}

Вы делаете ту же ошибку в Pop, чтозаставить вас полностью пропустить первый элемент.Назначение на temp должно быть таким:

temp = S->ThisStack;

Наконец, ваше поле Size всегда будет неправильным.Похоже, что GrowFreeList должен удваивать размер стека при его вызове, но когда вы вызываете его из CreateStack, реальный размер вашего стека равен 0, хотя поле Size равно 8 (в вашем примере).В результате в стеке есть 8 свободных узлов, но его поле Size равно 16. Фактически, поле Size всегда будет больше, чем фактический размер на начальный размер.Теперь это не вызывает никаких проблем, так как используется только для определения количества добавляемых объектов, но исправить это просто: сбросьте поле Size после вызова GrowFreeList из CreateStack:

Stack CreateStack(int initialSize) {
    Stack S;
    ...
    S->Size = initialSize;
    GrowFreeList(S);
    S->Size = initialSize; // Reset size, since GrowFreeList changed it
    return S;
}

Answer 2

Как говорят другие, вы должны использовать fprintf(stderr,...) для печати отладочных сообщений.

Вы можете использовать gdb, чтобы увидеть, в чем проблема, и посмотреть, что происходит в памяти. Добавьте флаг -g при компиляции, чтобы помочь с отладкой в ​​gdb.

Это вывод, который GDB дал мне:

(gdb) r
Starting program: .../test 
Pushing:
1 2
2

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400873 in Push (X=1, S=0x601010) at stackli.c:81
81      temp->Next = S->ThisStack->Next;
(gdb) bt
#0  0x0000000000400873 in Push (X=1, S=0x601010) at stackli.c:81
#1  0x0000000000400627 in main () at testprob2.c:20
(gdb) print temp
$1 = (PtrToNode) 0x601110
(gdb) print S->ThisStack
$2 = (PtrToNode) 0x0

Ошибка возникает в void Push( ElementType X, Stack S ).

Как вы можете видеть, когда мы распечатываем S->ThisStack, мы получаем 0x0, т.е. S->ThisStack указывает на NULL. Когда вы разыменовываете S->ThisStack, чтобы добраться до S->ThisStack->Next, вы получаете ошибку сегментации.

Вы можете добавить чек на if (S->ThisStack == NULL). Я не совсем уверен в том, как вы собираетесь создавать структуру стека.

Также обратите внимание, что это только одна проблема с вашим кодом, потенциально (и скорее всего) гораздо больше проблем, однако вы должны иметь возможность сузить их с помощью gdb с помощью команды backtrace (bt) и печать в stderr вместо stdout, чтобы ваш вывод не буферизовался. Я не хочу делать твою домашнюю работу за тебя.

Answer 3

Да ладно ... вот и мы:

Вы инициализируете свой Stack S с CreateStack(8).Это устанавливает ThisStack в NULL внутри структуры.Тогда первое, что вы так называете Push(1,S), в котором вы делаете ...

temp->Next = S->ThisStack->Next;

Kaboom.Вы просто разыменовали указатель NULL.

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

Answer 4

Комментарии о промывке верны.Проблема во второй-последней строке Push.Вы никогда не инициализировали ThisStack, поэтому при попытке получить доступ к его элементу next вы получаете segfault.Кстати, ваш размер отключен, потому что вы удваиваете его после заполнения в первый раз.Наконец, вы должны постараться не указывать typedef указатели.Слишком легко забыть, что указатель, а что нет.Сделать стек полной структурой и объявить указатели на нее.