Stapel in C. Speichern Popant Top-Ergebnisse

Question

Betrachten Sie einen Stapel, mit einem Maximum von 100 Int. Wie folgt definiert:

#define MAX 100 

typedef struct stack { 
    int size; 
    int values[MAX];  
} STACK; 

ich dieses Pop-Funktion haben:

int pop(STACK *s, int *x){ 
    if (s->size == 0) return 1; 

    int *p = s->values + s->size--; 
    *x = *p; 

    return 0; 
} 

Welche soll Werte [MAX] letzte Element entfernen, speichern diesen Wert bei x-Adresse und dann 0 zurück, wenn der Erfolg;

Weitere Funktionen:

int top(STACK *s, int *x){ 
    if (s->size == 0) return 1; 

    int *p = s->values + s->size; 
    *x = *p; 

    return 0; 
} //like pop function, it should store top element at address x. 


void initStack(STACK *s){ 
    s->size = 0; 
} 

int push(STACK *s, int x){ 
    if (s->size >= MAX) return 1; 

    int *p = (s->values); 
    *(p + s->size++) = x; 

    return 0; 
} 

Das ist mein Haupt. Es schlägt fehl, nur auf dem ersten Pop-Aufruf:

int main(){ 
    struct stack s; 
    STACK *p = &s; 
    int i; 
    int x,y,z,w,t; 

    initStack(p); 

    for(i = 0; i < MAX; i++) 
     push(p,i); 

    int res = push(p,MAX); 

    for(i = 0; i < MAX; i++) 
     printf("%d|", p->values[i]); 

    printf("\nLast insertion: %d",res); 

    pop(p,&x); 
    pop(p,&y); 
    pop(p,&z); 
    pop(p,&w); 
    top(p,&t); 

    printf("\nThe elements %d|%d|%d|%d were removed. Current stack size: %d . Top element: %d.",x,y,z,w,p->size,t); 

    return 0; 
} 

Ergebnisse (nur letzte printf):

The elements 1|99|98|97 were removed.Current stack size: 96 .Top element: 96. 

Aus irgendeinem Grunde erster Pop-Aufruf fehlschlägt,, die nicht nur die Liste der entfernten Elemente verurteilt, aber auch das oberste Element Ergebnis. Irgendwelche Vorschläge warum?

Answer 1

Ich zweite diejenigen, die über die Klarheit des Codes kommentiert haben. Wenn Sie Arrays verwenden, ist es viel weniger wahrscheinlich, dass Sie Probleme haben, wenn Sie anstelle der Zeigerarithmetik [] Indizierung verwenden.

Das sagte, ich denke, das Problem ist, dass pop ein Out-of-Bounds-Problem hat. Nachdem Sie MAX Elemente in main, s->size==MAX drücken. Daher greift pop auf *(s->values + MAX) == s->values[MAX] zu, das ist tatsächlich das Element nach das Ende des Arrays. Das Array läuft von 0 bis MAX-1, nicht von 1 bis MAX. Zum Beispiel, wenn size==1, möchten Sie eigentlich s->values[0], das erste Element, anstatt nicht existent s->values[1].

Die minimale Änderung wäre int *p = s->values + --s->size;, aber ich stimme zu, das ist nicht der richtige Weg, um das Problem zu beheben. Verwenden Sie stattdessen so etwas wie *x = s->values[s->size-1]; --s->size;

Answer 2

1. Sie schieben MAX+1 Elemente auf den Stack, da die Schleife MAX Elemente schiebt und es gibt ein weiteres push Anruf nach der Schleife.

2. Ihre pop Implementierung ist falsch, da die Linie:

   int *p = s->values + s->size--; 
   

   Der Zeiger p-s->values[s->size] statt s->values[s->size-1] zeigen, weil die Abnahme von s->size nach der Auswertung und Zuordnung zu p auftreten.

3. Die Verwendung von Inkrementieren/Dekrementieren Operatoren innerhalb von Ausdrücken wird mit Recht als schlechte Praxis angesehen und von genau dieser Art von Fehlern dringend abgeraten.

4. möglich, wenn, ist es viel besser lesbar und weniger fehleranfällig wie so den Index-Operator [] statt Zeigerarithmetik zu verwenden:

   int 
   pop(STACK *s, int *x) { 
       if (s->size == 0) { 
       return 1; 
       } 
   
       s->size--; 
       *x = s->values[s->size]; 
   
       return 0; 
   }