6.4 Stack con allocazione dinamica

Si riportano di seguito le funzioni per la gestione di uno stack solo che, stavolta, gli elementi nello stack sono allocati dinamicamente.

/* 
   Funzioni per la gestione di un elenco di libri con
   uno STACK dinamico
*/

#include <stdlib.h>	/*1*/

/* Implementazione della struttura */

typedef struct rec *lpointer;	/*2*/
typedef struct rec { 
  char titolo[50];
  char autore[20]; 
  char editore[20]; 
  float prezzo; 
  lpointer next;	/*3*/ 
}libro;
lpointer cima=NULL;	/*4*/
...

/* Funzioni per la gestione dello Stack */

void push(lpointer lib){	/*5*/
  lib->next=cima;	/*6*/
  cima=lib;	/*7*/
}

lpointer pop(){	/*8*/
  lpointer lib;  
  lib=cima;	/*9*/
  if (cima)	/*10*/
    cima=cima->next;
  return lib;
}

L’inclusione specificata in 1 permette, all’interno del programma, di utilizzare le funzioni per l’allocazione dinamica della memoria.

Nella 2 la dichiarazione di un puntatore alla struttura rec è preceduta dalla dichiarazione di definizione di tipo typedef. Tale dichiarazione permette di utilizzare lpointer allo stesso modo dei tipi definiti dal C, come per esempio il tipo int. lpointer diventa, con questa dichiarazione, un sinonimo di struct rec *, così come libro diventa sinonimo di struct rec. Ciò permette di incrementare la leggibilità delle dichiarazioni, la quale cosa sarà di utilità specie nelle dichiarazioni complesse.

Così come messo in evidenza nelle righe precedenti, nella struttura libro oltre agli attributi visti negli altri esempi, viene dichiarato in 3 un puntatore al prossimo elemento della lista: next è una variabile di tipo lpointer cioè, come evidenziato in 2, un puntatore a libro. Come è possibile notare, la praticità di tale dichiarazione permette di abbreviare e rendere più chiara la natura della variabile next. Tale variabile viene utilizzata per collegare ogni elemento al suo successivo.

La dichiarazione presente in 4 è l’unica che alloca effettivamente spazio in memoria. Viene dichiarata la variabile cima che è di tipo lpointer e che viene inizializzata al valore NULL. Ciò indica che, in questo momento, la struttura è vuota.

Alla funzione push nella 5 viene passato un puntatore alla zona di memoria dove è conservato l’elemento da inserire nella struttura. L’attuale contenuto di cima viene copiato, nella 6, nel puntatore next. Se c’era NULL vorrà dire che questo elemento inserito sarà considerato l’ultimo, se invece puntava ad un elemento E_i, con tale assegnazione E_i diventa il successivo dell’elemento che si sta inserendo. Il puntatore cima, per la 7, da questo momento punterà all’ultimo elemento inserito.

La funzione pop, come definito in 8, ritorna un puntatore all’elemento estratto. Nella 9 viene definita una variabile di tipo lpointer alla quale viene assegnato il valore di cima. Come osservato, nei commenti riguardanti la push, cima punta all’ultimo elemento inserito. Nel caso in cui lo stack fosse vuoto, il valore assegnato sarebbe NULL per l’inizializzazione della 4. Il programma chiamante deve controllare tale eventualità.

La funzione pop, come specificato in 8, ritorna un puntatore all’elemento estratto dallo stack. Il puntatore ritornato, come osservato precedentemente, assume, come messo in evidenza da 9, il valore di cima: è questo infatti il puntatore all’ultimo elemento inserito. Se lo stack è vuoto il puntatore, per la 4, varrà NULL. L’istruzione presente in 10 testa quest’ultimo caso: se c’era almeno un elemento, cima dovrà puntare al successivo.

Il chiamante dovrà verificare se la pop ritorna un puntatore valido e, finito l’utilizzo dell’elemento estratto, dovrà occuparsi di liberare, con una chiamata alla funzione free, la memoria occupata dall’elemento.

Le funzioni di inserimento ed estrazione di un libro dalla pila saranno, rispettivamente:

/* Inserimento di un libro nella pila */
    
void inserisci(){
  lpointer buflib;	/*1*/

  buflib=(libro*) malloc(sizeof(libro));	/*2*/

  printf("\nInserimento di un libro");
  printf("\nTitolo : "); 
  gets(buflib->titolo); 	/*3*/
  printf("Autore : "); 
  gets(buflib->autore); 	/*3*/
  printf("Editore : "); 
  gets(buflib->editore); 	/*3*/
  printf("Prezzo : "); 
  scanf("%f",&(buflib->prezzo)); 	/*3*/
  while(!getchar()=='\n');

  push(buflib);	/*4*/

}

/* Estrazione di un libro */

void estrai(){
  lpointer buflib; 	/*5*/	

  buflib=pop();	/*6*/
    
  if(buflib){  	/*7*/
    puts(buflib->titolo); 	/*8*/
    puts(buflib->autore); 	/*8*/
    puts(buflib->editore); 	/*8*/
    printf("%4.2f\n",buflib->prezzo); 	/*8*/
  }else
    printf("Non ci sono elementi nella pila\n");	/*9*/

}

Nella funzione di inserimento viene dichiarato un puntatore alla struttura libro (1), viene allocato lo spazio per contenere i dati (2), si acquisiscono i dati nei vari membri (3). Si noti l'uso dell'operatore -> per l'accesso ai membri in una allocazione dinamica. Infine (4) si richiama la funzione push di inserimento nella pila passando, come parametro, il puntatore alla zona di memoria che contiene i dati da conservare.

Nella funzione di estrazione si dichiara (5) un puntatore, alla solita struttura, che accoglierà i dati prelevati dallo stack (6). Se la funzione ritorna un puntatore valido (7), vengono visualizzati i dati (8), altrimenti viene visualizzato un messaggio (9).