Wie erstelle ich einen leeren Stapel?

Question

Ich versuche einen Stapel zu erstellen, wo ich ganze Zahlen hineinschieben kann. Bisher habe ich das:

#include <stdio.h> 
#define N 20 

typedef struct { 
    int data[N]; // array of at most size N 
    // N should be a constant declared globally 
    int top; 
} stack_t; 

void push(stack_t *stack, int element); 


int main(){ 

void push(stack_t *stack, int n) { 
    if (stack->top == N - 1) { 
     printf("Warning: Stack is full, You can't add'\n"); 
     return; 
    } else { 
     stack->data[++stack->top] = n; 
    } 
    } 


    stack_t * e_stack; // Empty stack created 
    push(e_stack, 2); 


} 

Allerdings gibt dieser Code einen Laufzeitfehler. Ich nehme an, es liegt daran, dass dieser Teil falsch ist: stack_t * e_stack; // Leere Stapel erstellt

(das wahrscheinlich nicht schaffen ein leerer Stack)

Aber ich weiß, wie es ist falsch

Answer 1

Du hast Recht, alles, was Sie haben, ist ein Zeiger erstellt getan, dass zeigt auf ... etwas, aber wahrscheinlich kein stack_t. Sie müssen etwas zuordnen, auf das Sie zeigen können. Siehe malloc. Dann müssen Sie stack_t::top auf -1 oder einen anderen Wert initialisieren. Null wird wahrscheinlich hier nicht funktionieren, da dieser Index wahrscheinlich das erste Element im Stapel sein würde.

Answer 2

Hier ist ein Beispiel, das ich vor einiger Zeit geschrieben habe. Im Grunde werden ganze Zahlen auf einen Stapel geschoben und das zuletzt hinzugefügte Element wird dem Stapel hinzugefügt. Beachten Sie, dass das Knallen von Gegenständen wahrscheinlich nicht der beste Weg ist, es zu tun, es gibt sicherlich bessere Möglichkeiten.

Beispielcode:

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

#define N 20 

typedef struct { 
    int data[N]; //better to use a dynamic array instead here 
    int top; 
} stack_t; 

stack_t *create_empty_stack(void); 
void push(stack_t *stack, int value); 
int pop(stack_t *stack); 

int 
main(void) { 
    stack_t *stack; 
    stack = create_empty_stack(); 

    push(stack, 10); 
    push(stack, 20); 
    push(stack, 30); 

    printf("Popped: %d\n", pop(stack)); 
    printf("Popped: %d\n", pop(stack)); 
    printf("Popped: %d\n", pop(stack)); 
    printf("Popped: %d\n", pop(stack)); 

    free(stack); 

    return 0; 
} 

void 
push(stack_t *stack, int value) { 
    if (stack->top == N - 1) { 
     printf("Warning: Stack is full, You can't add'\n"); 
     return; 
    } else { 
     stack->data[stack->top] = value; 
     (stack->top)++; 
    } 
} 

int 
pop(stack_t *stack) { 
    if (stack->top > 0) { 
     (stack->top)--; 
     return stack->data[stack->top]; 
    } else { 
     //definetly better way to do this. I will let you decided how you want to implement this. 
     printf("Tried to pop empty stack!\n"); 
     exit(EXIT_FAILURE); 
    } 
} 

// Since you are using a fixed sized array, creating an empty stack in this case is easy. 
stack_t 
*create_empty_stack(void) { 
    stack_t *stack = malloc(sizeof(*stack)); 
    if (stack == NULL) { 
     printf("Cannot allocate stack\n"); 
     exit(EXIT_FAILURE); 
    } 
    stack->top = 0; 
    return stack; 
} 

Answer 3

Entweder (wie andere Antworten vorschlagen) einen Speicherbereich zuweisen und einen Zeiger auf stack_t auf dem Heap bekommen und richtig initialisiert werden (vielleicht durch eine create_empty_stack-Funktion) oder deklarieren ein stack_tlocal variable (auf der call stack), initialisieren es explizit, und übergeben sie einen Zeiger auf sie:

stack_t locstack = {.data={}, .top=0}; 
push(&locstack, 2); 

BTW, wie Jonathan Leffler kommentierte Code ist nicht Standard C99 oder C11, weil nested functions in Standard C nicht erlaubt sind. Sie verwenden (wahrscheinlich falsch) einige GCC extension. Sie sollten die push-Funktion außerhalb von (und vor) main definieren. Wenn Sie Wert auf Effizienz legen, definieren Sie es als static inline void push(stack_t *stack, int n) .... um es zu bekommen inlined.

Beachten Sie, dass, wenn Sie beliebig große Stapel annehmen möchten, sollten Sie einige flexible array member verwenden und wachsen sie (hin und wieder) nach Bedarf (man denke an einige int newsize = 4*stack->size/3+2;, wenn der Stapel voll ist, dann
stack_t*newstack = malloc(sizeof(stack_t)+newsize*sizeof(int)); etc ....) und nur Verwenden Sie heap allocated Zeiger, könnten Sie sowohl top und size als Felder von stack_t halten und haben data[] als sein (last) flexible array member. In diesem Fall würde push wahrscheinlich einen (möglicherweise aktualisierten) Zeiger zurückgeben.

BTW, sobald Sie wie malloc einig Heapzuordnung verwenden, können Sie immer sollten Ausfall behandeln, zumindest als:

stack_t* pstack = malloc(sizeof(stack_t)); 
if (pstack==NULL) { perror("malloc"); exit(EXIT_FAILURE); }; 

(wenn Sie etwas haben GCC Wenn verwenden, lesen mehr über seine command options (ihre Reihenfolge ist wichtig). Ich empfehle kompilieren mit (auf Ihrem ursprünglichen Code, der einige nützliche Diagnose geben sollte), verbessern Sie Ihren Code, bis Sie keine Warnungen erhalten, dann verwenden Sie den gdb Debugger.