6.5 Coda con allocazione dinamica

La logica della gestione di una coda, fatte salve le specificità, è simile alla logica di gestione dello stack: si dovrà tenere conto solo del fatto che qui si devono gestire due puntatori.

/* 
   Funzioni per la gestione di un elenco di libri con
   una CODA dinamica
*/

#include <stdlib.h>

/* Implementazione della struttura */

typedef struct rec *lpointer;
typedef struct rec { 
  char titolo[50]; 
  char autore[20]; 
  char editore[20]; 
  float prezzo; 
  lpointer next; 
}libro;
lpointer testa=NULL;	/*1*/
lpointer fondo=NULL;

/* Funzioni per la gestione della Coda */

void aggiungi(lpointer lib){	/*2*/
  lib->next=NULL;	/*3*/
  if (fondo)	/*4*/
    fondo->next=lib; 
  fondo=lib; 
  if(!testa)	/*5*/ 
    testa=lib; 
}

lpointer elimina(){	/*6*/
  lpointer lib; 
  lib=testa;	/*7*/ 
  if (testa)	/*8*/ 
    testa=testa->next; 
  if (!testa)	/*9*/ 
    fondo=NULL; 
  return lib;
}

Le dichiarazioni presenti in 1 sono formalmente simili a quelle presenti nella gestione dello stack, eccezione fatta per la presenza, in questo caso, di due puntatori invece che uno solo: testa utilizzato per i prelievi, fondo per gli inserimenti.

La funzione aggiungi in 2, si occupa dell’inserimento di un nuovo elemento nella coda. La funzione riceve un puntatore all’elemento da inserire e, per prima cosa (per la 3) considera tale elemento ricevuto come ultimo e quindi registra nel suo puntatore il codice di fine coda. Si occupa poi di modificare il puntatore dell’ultimo elemento che era presente nella coda, ammesso che esista (condizione testata in 4) e quindi di aggiornare fondo al nuovo elemento. Il controllo presente in 5 si occupa di verificare se testa era NULL (non c’erano cioè elementi prima di questo inserito) e, in tal caso fa in modo che tale puntatore conservi l’indirizzo dell’elemento inserito.

La funzione elimina della 6 preleva un elemento dalla coda, restituendo un puntatore allo stesso. Poiché testa punta al primo elemento da prelevare, è il valore di tale puntatore che deve essere restituito (istruzione 7). Se, all’atto del prelievo, c’era almeno un elemento, testa dovrà puntare al prossimo: è di ciò che si occupa il controllo 8. Il controllo presente in 9 si occupa di verificare se l’elemento prelevato era l’ultimo e, in tal caso reinizializza il puntatore fondo.

Così come osservato per la gestione dello stack, il chiamante, finito l’utilizzo dell’elemento estratto dalla coda, dovrà liberare la memoria occupata.