Dynamic Array Based Stack in C.

Question

Ich habe einen dynamischen Stapel in C geschrieben, der ein Array als Struktur verwendet. Ich habe versucht, O (1) für Push und Pop beizubehalten und glaube, dass ich das getan habe. Ich möchte wissen, was sauberer geschrieben werden kann und ob es nicht triviale Fehler gibt.

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

int push(int val, int *c);
int pop(int *c);

int *stack;

int main(){
    int *c = malloc(sizeof(int));
    stack = malloc(sizeof(int));
    *c = 0;
    int i;
    for(;;){
       printf("1. Push\n2. Pop\n3. Stack\n4. Quit\n>>> ");
       scanf("%d", &i);
       if(i == 1){
           printf("Value: ");
           scanf("%d", &i);
           push(i, c);
       }
       else if(i == 2)
           printf("Value popped: %d\n", pop(c));
       else if(i == 3)
           for(int i = 0; i < *c; i++)
               printf("%d\n", stack[i]);
       else
           break;
    }
    free(stack);
    return 0;
}

int push(int val, int *c){
    int *r;
    r = realloc(stack, ((*c)+1)*sizeof(int));
    if (r == NULL){
        free(stack);
        exit(0);
    }
    stack = r;
    stack[*c] = val;
    ++(*c);
    return *c;
}

int pop(int *c){
    if (!(*c)) return -1;
    int x = stack[(*c)-1];
    stack[(*c)-1] = NULL;
    int *r;
    printf("%d\n", *c);
    r = realloc(stack, ((*c)-1)*sizeof(int));
    if(r == NULL){
        free(stack);
        exit(0);
    }
    --(*c);
    stack = r;
    return x;
}

```

Answer 1

Die Bewertung von @G. Sliepen ist gesund und ich stimme mit allem überein, was dort gesagt wurde. Und dazu:

• Verstecke niemals Zeiger hinter einem typedef! Dies macht das Lesen des Codes für C-Programmierer, einschließlich Sie selbst, sehr verwirrend. Sie könnten denken, Sie übergeben Daten nach Wert, wenn Sie es nicht sind, und ähnliche verwirrende Situationen.

• ... = malloc(sizeof(int));Es ist ineffizient, nur 1 Element zuzuweisen und muss es dann fast sofort tun realloc. Beachten Sie, dass der gesamte dynamische Speicherort bei der Erstellung langsam ist und wir versuchen sollten, die Anzahl der Aufrufe von malloc/ zu minimieren realloc. Ein häufiger Aufruf führt auch zu einer Fragmentierung des Heapspeichers , was zu einer Verschwendung von Speicher und anderen Problemen führen kann.

  Weisen Sie stattdessen beim ersten Anruf eine Schätzung zu, die groß genug ist malloc. Vielleicht 100 Artikel stattdessen. Und jedes Mal, wenn Ihnen der Speicher ausgeht, geben Sie nicht reallocnur 1 Element mehr zu, weisen Sie viel mehr zu und verfolgen Sie, wie viel Speicherplatz Sie zugewiesen haben und wie viel Speicher Sie verwenden.

  Ebenso ist es nicht erforderlich, die Menge des zugewiesenen Speichers jedes Mal zu verkleinern, wenn Sie etwas einfügen. Die Freigabe ist ebenfalls langsam. Verringern Sie einfach einen Zähler, der festhält, wie viel des zugewiesenen Speichers Sie verwenden.

  Solche Dinge sind tatsächlich wichtig, wenn es um die Programmleistung geht. "Big O" -Theorie, weit weniger.

• stack[(*c)-1] = NULL;ist falsch, ein Fehler. Sie sollten allgemeinen Variablen niemals NULL zuweisen, sondern nur Zeigern. NULL könnte genauso gut als Zeigertyp definiert werden, und dann würde dieser Code brechen.

  Tatsächlich müssen Sie nicht verwendeten Speicher überhaupt nicht löschen, das ist sinnlos.

• Ein Stilproblem, aber machen Sie es sich zur Gewohnheit, es immer zu verwenden, { }auch wenn nur eine einzige Zeile in den folgenden Anweisungen if/elseoder Schleifenanweisungen enthalten ist. Und vermeiden Sie schlampige Einzeiler wieif (!(*c)) return -1;

• Der Variablenname isollte nur für Schleifeniteratoren verwendet werden. Der Name iin einer Schleife steht eigentlich für Iterator . Verwenden Sie es nicht für andere Zwecke, z. B. für Benutzereingaben.

• Verwenden Sie keine "magischen Zahlen" im Code, wie z else if(i == 3). Verwenden Sie stattdessen Textkonstanten. Zum Beispiel:

    enum
    {
      PUSH  = 1,
      POP   = 2,
      PRINT = 3,
      QUIT  = 4,
    };
  

• Mit der obigen Aufzählung können wir die for-Schleife und die if-Anweisungen ein wenig aufräumen, wodurch der Code etwas länger, aber weitaus wartbarer wird:

  int user_choice = 0;
  while(user_choice != QUIT)
  {
    printf("1. Push\n2. Pop\n3. Stack\n4. Quit\n>>> ");
    scanf("%d", &user_choice);
  
    switch(user_choice) 
    {
      case PUSH: 
      {
        printf("Value: ");
        scanf("%d", &i);
        push(i, c);
        break;
      }
  
      case POP:
      {
        printf("Value popped: %d\n", pop(c));
        break;
      }
  
      case PRINT:
      {
        for(int i = 0; i < *c; i++)
        {
          printf("%d\n", stack[i]);
        }
        break;
      }
  
      default:
        user_choice = QUIT; // defensive programming, quit upon all invalid choises
    } // switch(user_choice) 
  } // while(user_choice != QUIT)
  

  (Beachten Sie, dass ich absichtlich keinen user_choiceAufzählungstyp erstellt habe. Ich habe dies nur getan, weil scanf("%d", &user_choice);eine Aufzählung nicht sicher ist. Andernfalls typedef enumwäre eine vorzuziehen gewesen int.)

Answer 2

Erstellen Sie eine struct, die alle Details eines Stapels enthält

Das Problem ist, dass Ihr Stapel nur wie ein Zeiger auf einen aussieht int, der nicht von anderen Zeigern auf ints zu unterscheiden ist. Und das erste Element, auf das es zeigt, wird anders behandelt als die anderen Elemente. In diesem Fall ist es besser, eine Struktur zu erstellen, die den zugewiesenen Speicher und dessen Größe wie folgt verfolgt:

struct Stack {
    size_t size;
    int *data;
};

Sie initialisieren es wie folgt:

struct Stack stack = {0, NULL};

Jetzt sollten Sie ändern push()und pop()einen Zeiger auf a nehmen struct stack:

void push(struct Stack *stack, int val) {
    stack->size++;
    int *new_data = realloc(stack->data, stack->size * sizeof *stack->data);

    if (!new_data) {
        // error handling here, or just
        abort();
    }
    
    stack->data = stack->new_data;
    stack->data[stack->size - 1] = val;
}

Und ähnlich für pop(). Beachten Sie, dass Funktionen, die mit einem Objekt arbeiten, häufig den Zeiger auf dieses Objekt als ersten Parameter verwenden. Außerdem habe ich die Funktion zurückgegeben void. Es ist nicht erforderlich, die Größe der Stapelgröße zurückzugeben, die dem Aufrufer bereits zur Verfügung steht.

Vermeiden Sie die Verwendung globaler Variablen

Sie sollten nach Möglichkeit die Verwendung globaler Variablen vermeiden. In meinem obigen Beispielcode muss kein globaler Code mehr vorhanden sein stack. Diese Änderung ermöglicht es dem Code, mehrere Stapel ohne Konflikte zu verwalten.

Fügen Sie Funktionen zum Erstellen und Zerstören von Stapeln hinzu

struct StackErstellen Sie Funktionen, die dies für Sie tun, anstatt vom Anrufer zu verlangen, dass er weiß, wie ein ordnungsgemäß initialisiert und nach der Verwendung freigegeben wird. Auf diese Weise können Sie die Interna von struct Stackspäter ändern , ohne alle Stellen ändern zu müssen, an denen ein Stapel verwendet wird.

Verwenden Sie ein allgemeines Präfix, um Namenskonflikte zu vermeiden

push()und pop()sind sehr generische Namen. Es gibt noch viele weitere Dinge, die Push- und Pop-Vorgänge haben können, z. B. FIFO-Warteschlangen. Ich empfehle Ihnen, ein gemeinsames Präfix für alle Datenstrukturen und Funktionen für Ihren Stapel zu verwenden. Dies kann einfach sein Stackoder stackwenn Sie der Meinung sind, dass dies wahrscheinlich nicht mit irgendetwas anderem in Konflikt steht.