Stack basato su array dinamici in C

Question

Ho scritto uno stack dinamico in C che utilizza un array come struttura. Ho provato a mantenere O (1) per push e pop e credo di averlo fatto. Voglio sapere cosa si può scrivere in modo più pulito e se ci sono bug non banali.

#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

La recensione di @G. Sliepen è sano e sono d'accordo con tutto ciò che è stato detto lì. Inoltre:

• Non nascondere mai i puntatori dietro a typedef! Questo rende il codice molto confuso da leggere per i programmatori C incluso te stesso. Potresti pensare di passare i dati per valore quando non lo sei e situazioni confuse simili.

• ... = malloc(sizeof(int));È inefficiente allocare solo 1 oggetto e poi doverlo quasi immediatamente realloc. Nota che tutta la posizione della memoria dinamica è lenta al momento della creazione e dovremmo ridurre al minimo la quantità di chiamate a malloc/ realloc. Chiamarli frequentemente porta anche alla frammentazione dell'heap , che può portare a uno spreco di memoria e ad altri problemi.

  Assegna invece una stima "abbastanza grande" la prima volta che chiami malloc. Forse 100 articoli invece. E ogni volta che esaurisci la memoria, non reallocsolo 1 elemento in più, alloca molto di più e tieni traccia di quanto spazio hai allocato e di quanta memoria stai utilizzando.

  Allo stesso modo, non è necessario ridurre la quantità di memoria allocata ogni volta che si apre qualcosa. Anche la deallocazione è lenta. Basta diminuire un contatore che tiene traccia della quantità di memoria allocata che stai utilizzando.

  Cose come queste sono ciò che conta davvero quando si tratta di prestazioni del programma. Teoria della "Big O", molto meno.

• stack[(*c)-1] = NULL;non è corretto, un bug. Non si dovrebbe mai assegnare NULL alle variabili comuni, solo ai puntatori. NULL potrebbe anche essere definito come un tipo di puntatore e quindi questo codice si interromperà.

  In effetti non è necessario cancellare affatto la memoria non utilizzata, è inutile.

• È un problema di stile, ma rendi l'abitudine di usarlo sempre { }anche quando c'è solo una singola riga all'interno dell'istruzione following if/elseo loop. Ed evita le battute sciatte comeif (!(*c)) return -1;

• Il nome della variabile ideve essere utilizzato solo per gli iteratori del ciclo. Il nome iin un ciclo sta effettivamente per iteratore . Non usarlo per altri scopi come prendere l'input dell'utente.

• Non utilizzare "numeri magici" nel codice, come else if(i == 3). Usa invece costanti testuali. Per esempio:

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

• Con l'enumerazione sopra, possiamo chiarire un po 'il ciclo for e le istruzioni if, rendendo il codice un po' più lungo ma molto più gestibile:

  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)
  

  (Nota che deliberatamente non ho user_choicecreato un tipo enum. L'ho fatto solo perché scanf("%d", &user_choice);su un enum non è sicuro. Altrimenti, a typedef enumsarebbe stato preferibile int.)

Answer 2

Crea un'immagine structche incapsuli tutti i dettagli di una pila

Il problema è che il tuo stack sembra solo un puntatore a un int, indistinguibile da altri puntatori a ints. E il primo elemento a cui punta viene trattato in modo diverso dagli altri elementi. In questo caso, è meglio creare una struttura che tenga traccia della memoria allocata e delle dimensioni di essa, in questo modo:

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

Lo si inizializza come segue:

struct Stack stack = {0, NULL};

Ora dovresti cambiare push()e pop()prendere un puntatore a 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;
}

E simile per pop(). Notare che è comune avere funzioni che operano su un oggetto che prendono il puntatore a quell'oggetto come primo parametro. Inoltre, ho fatto tornare la funzione void, non è necessario restituire la dimensione della dimensione dello stack che le informazioni sono già disponibili per il chiamante.

Evita di usare variabili globali

Se possibile, dovresti evitare di utilizzare variabili globali. Il mio codice di esempio sopra non richiede più che ci sia un global stack. Questa modifica consente al codice di gestire più stack senza conflitti.

Aggiungi funzioni per creare e distruggere pile

Invece di richiedere al chiamante di sapere come inizializzare correttamente un struct Stacke liberarlo dopo l'uso, crea funzioni che lo facciano per te. Ciò ti consente di modificare gli interni di un struct Stacksecondo momento, senza dover cambiare tutti i punti in cui viene utilizzato uno stack.

Utilizza un prefisso comune per evitare conflitti di nome

push()e pop()sono nomi molto generici. Ci sono molte altre cose che possono avere operazioni push e pop, come le code FIFO. Ti consiglio di utilizzare un prefisso comune per tutte le strutture dati e le funzioni per il tuo stack. Questo può essere semplicemente Stacko stackse pensi che sia improbabile che sia in conflitto con qualcos'altro.