6.7 Gestione di una lista concatenata

La lista concatenata è la struttura ideale da utilizzare quando si debbano rappresentare insiemi di dati in cui le operazioni di inserimento e cancellazione siano prioritarie. Tali operazioni, come si vedrà, vengono permesse in maniera estremamente agevole dalla struttura.

• Implementazione. Nel caso di una lista non c’è una allocazione preventiva della struttura: si definiscono le strutture di cui si ha bisogno, la memoria verrà allocata quando serve, quando cioè si tratterà di conservare gli elementi.

/* Gestione di una LISTA con un elenco di libri */

#include <stdlib.h> 

/* Implementazione della Lista */

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

Le dichiarazioni presenti sono simili a quelle utilizzate nell’implementazione di uno stack: anche in questo caso si deve collegare ogni elemento con il suo successivo.

La dichiarazione presente in 1 è l’unica che alloca effettivamente spazio in memoria. Viene dichiarata la variabile entryp che è di tipo lpointer e che viene inizializzata al valore NULL. Questa rappresenta il puntatore al primo elemento della lista (entry point); i successivi elementi della lista saranno raggiungibili attraverso i puntatori contenuti in ogni nodo.

• Attraversamento. Definita la struttura concatenata, ci si occuperà delle operazioni fondamentali sulle liste. La prima operazione esaminata riguarda l’attraversamento di una lista: l’esame cioè di tutti i nodi presenti nella lista. Nel programma scritto di seguito vengono riportate solo le istruzioni riguardanti l’elaborazione richiesta; per la definizione della struttura si fa riferimento a quanto scritto in precedenza.

...
/* Funzioni per la gestione della Lista */

void esamina(lpointer p1);	/*1*/
...
esamina(entryp);	/*2*/
...

/* Funzioni per la gestione di una lista */

void esamina(lpointer p1){
  if(p1){	/*3*/

    /* elaborazione nodo */	/*4*/

    puts(p1->titolo);
    puts(p1->autore);
    puts(p1->editore);
    printf("%4.2f\n",p1->prezzo);
    while(!getchar()=='\n');	/*5*/	

    /* fine elaborazione nodo */

    esamina(p1->next);	/*6*/
  } 
}

Nella 1 viene dichiarato il prototipo della funzione che si occuperà di esaminare un nodo della lista: tale funzione riceverà il puntatore al nodo da esaminare.

La funzione verrà chiamata, come in 2, passandogli inizialmente l’entry point in modo da puntare al primo elemento.

L’esame degli elementi della lista è effettuato con una funzione ricorsiva: se il puntatore passato (3) è un puntatore valido, elabora l’elemento e richiama la funzione passando il puntatore contenuto nel nodo esaminato (il puntatore al prossimo nodo). A cominciare da 4 si elabora l’elemento (quello raggiungibile per mezzo del puntatore p1); nel caso specificato in questa sede, l’elaborazione è una visualizzazione delle informazioni contenute nel nodo stesso.

Il ciclo della 5 serve soltanto a fermare la visualizzazione per permettere un esame più comodo. Viene visualizzato un nodo e, finché non si preme il tasto invio, il programma non passa alla prossima visualizzazione.

Nella 6 viene chiamata ricorsivamente esamina passandogli come parametro il puntatore al prossimo nodo della lista.

• Inserimento di un nodo. La lista concatenata è un insieme ordinato di elementi: la successione logica degli elementi è quella data dai puntatori. Nel frammento di programma successivo ci si occuperà dell’inserimento di un nuovo libro nella lista in modo che i libri siano ordinati per titolo.

  L’inserimento di un nuovo elemento, così come la cancellazione di un elemento esistente, sono operazioni che avvengono in modo agevole perché vengono effettuate mediante l’uso dei puntatori. Sono operazioni molto veloci sia perché per mantenere l’ordine non è necessario inserire fisicamente l’elemento nel posto che gli compete (si sottolinea che, a differenza del vettore, l’ordine logico non coincide con l’ordine fisico), sia perché si opera mediante i puntatori con le locazioni di memoria interessate alle operazioni.

  Prima di passare ad esaminare le funzioni che effettuano l’inserimento di un nodo in una lista, è bene chiarire l’algoritmo utilizzato al fine di una più agevole comprensione delle funzioni stesse e dei parametri utilizzati.

• 

  Il programma si occuperà per prima cosa di trovare il posto giusto dove inserire il nodo (si ricorda che i libri devono essere registrati in ordine alfabetico per titolo).

  Tenendo conto che ogni elemento della lista contiene oltre ai dati del libro registrato, il puntatore al prossimo elemento, e che è proprio questo che occorre modificare affinché punti all’elemento da inserire, occorre conoscere l’indirizzo di memoria del puntatore da modificare (posins nella figura) affinché possa avvenire tale modifica. Non si tratta infatti, in questo caso, di accedere all’elemento successivo per cui basta solo la conoscenza del valore del puntatore, bensì di modificare tale valore affinché punti ad un nuovo elemento.

  Trovato il puntatore da modificare l’inserimento dell’elemento viene effettuato in maniera agevole.

/* Funzioni per la gestione della Lista */

void inserisci(lpointer* pins,lpointer pnodo);	/*1*/

/* Altre funzioni del programma */
    
void nuovolib();	/*1*/
void aggiungi(lpointer pn);	/*1*/
lpointer* cerca(lpointer* inizio,char tit);	/*1*/
...
/*
  Inserimento di un libro nella lista
  i libri sono inseriti alfabeticamente per titolo
*/

void nuovolib(){
  lpointer nuovo; 
  nuovo=(lpointer) malloc(sizeof(libro));	/*2*/
  if(nuovo==NULL){ 
    printf("\nMemoria esaurita: inserimento impossibile"); 
  }else{ 
    printf("\nInserimento di un libro"); 
    printf("\nTitolo : "); 
    gets(nuovo->titolo); 
    printf("Autore : "); 
    gets(nuovo->autore); 
    printf("Editore : "); 
    gets(nuovo->editore); 
    printf("Prezzo : "); 
    scanf("%f",&nuovo->prezzo); 
    aggiungi(nuovo);	/*3*/
  } 
}

/* 
  Aggiunge il nuovo elemento 
  nella posizione che gli compete 
*/

void aggiungi(lpointer pn){
  lpointer *posins;	/*4*/
  
  posins=cerca(&entryp,pn->titolo);  	/*5*/
  inserisci(posins,pn);	/*6*/
}

/* Cerca la posizione dell'inserimento */

lpointer* cerca(lpointer* inizio,char *tit){
  if(*inizio==NULL) 	/*7*/
    return inizio;

  if((strcmp((*inizio)->titolo,tit)>0)) 	/*8*/
    return inizio; 
  
  inizio=cerca(&((*inizio)->next),tit);	/*9*/
  return inizio;	/*10*/

};

/* Funzioni per la gestione di una lista */

void inserisci(lpointer* pins,lpointer pnodo){	/*11*/	
  
 pnodo->next=*pins;	/*12*/
  *pins=pnodo;	/*13*/

}

Nelle 1, al solito, sono riportati i prototipi delle funzioni utilizzate: la inserisci si occupa dell’inserimento effettivo mentre le altre funzioni si occupano di predisporre le condizioni affinché tale inserimento possa aver luogo.

In 2 viene allocato, tramite la funzione malloc, lo spazio necessario per contenere un elemento di tipo libro. La funzione restituisce un puntatore alla memoria allocata, è necessario quindi verificare se tale puntatore punta effettivamente ad una zona di memoria valida (il puntatore deve cioè contenere un valore diverso da NULL). Se tale condizione è verificata vengono acquisiste le informazioni da conservare e si passa, nella 3, il valore contenuto nel puntatore alla funzione aggiungi che si occuperà dell’inserimento.

La funzione aggiungi dichiara nella 4 la variabile posins come puntatore a lpointer, praticamente un puntatore a puntatore. È in questi casi che la typedef fornisce i suoi maggiori vantaggi: senza il suo uso si sarebbe dovuto scrivere struct rec **ppos; con un notevole sforzo mentale per cercare di fissare le idee sul senso di puntatori e puntatori di puntatori. Con la definizione di tipo la 4 si può leggere: si dichiara posins come un puntatore al tipo lpointer. Come osservato prima si tratta di cercare il puntatore il cui valore dovrà essere modificato; è necessario passare alle funzioni un puntatore alla variabile il cui contenuto dovrà essere modificato.

La funzione cerca si occupa di ritornare, così come evidenziato in 1, un puntatore al dato da modificare (che è un puntatore). A tale funzione viene passato, come specificato in 5, l’entry point e il titolo da confrontare per trovare la giusta posizione di inserimento. Alla funzione inserisci, chiamata successivamente in 6, si passa il puntatore al dato da modificare ritornato da cerca e il puntatore all’elemento da inserire.

La funzione cerca verifica, in 8, se il titolo del libro puntato è alfabeticamente successivo al titolo del libro che si sta inserendo, o, in 7, se la lista è terminata. Laddove una di queste condizioni è verificata la funzione ritorna l’indirizzo del puntatore poiché è questo il dato da modificare e quindi occorre conoscere il suo indirizzo. Se nessuna delle condizioni descritte prima è verificata, la funzione chiama ricorsivamente sé stessa (9) passando ad esaminare il prossimo elemento della lista.

La 10 si occupa di ritornare il giusto puntatore in uscita dallo stack delle chiamate ricorsive.

La funzione inserisci si occupa dell’inserimento effettivo dell’elemento nella struttura concatenata. La funzione riceve, come evidenziato in 11, il puntatore all’indirizzo da modificare e il puntatore all’elemento da inserire. Il puntatore al punto di inserimento dovrà contenere l’indirizzo del nuovo elemento (13), ma prima il vecchio contenuto del punto di inserimento dovrà essere assegnato al puntatore del nuovo elemento (12). È opportuno fare notare che un errore nell’assegnazione dei valori ai puntatori, per esempio scambiare di posto la 12 e la 13, comporta la perdita di fatto degli elementi successivi della lista: ogni elemento contiene informazioni per rintracciare il prossimo, basta modificare in maniera erronea un puntatore perché tutti gli elementi da quel punto in poi, scompaiano, anzi non sono mai esistiti (non è possibile rintracciarli in alcun modo).

• Eliminazione di un nodo. L’algoritmo per l’eliminazione di un nodo dalla lista è simile a quello dell’inserimento.

• 

  Si cerca l’indirizzo dell’elemento da cancellare, si modifica tale indirizzo con il contenuto del puntatore dell’elemento da cancellare (in modo che tale indirizzo non punti più all’elemento che si deve eliminare, ma al prossimo della lista) e si rende libera, per eventuali altri usi, l’area di memoria prima occupata dall’elemento cancellato.

...
/* Elimina un elemento dalla lista */

void elimina();

/* Altre funzioni del programma */

lpointer* cerca(lpointer *inizio,char *tit);
void canclib();
...
/* Cancella un titolo dalla lista */

void canclib(){
  char titcanc[50]; 
  lpointer* poscanc;

  printf("\nTitolo da cancellare :"); 
  gets(titcanc);	/*1*/	
  
  poscanc=cerca(&entryp,titcanc,'=');	/*2*/
  
  if(*poscanc==NULL)	/*3*/	
    printf("\nTitolo inesistente: cancellazione impossibile"); 
  else 
    elimina(poscanc);	/*4*/
}

lpointer* cerca(lpointer *inizio,char *tit){
  ... 
  if(!strcmp((*inizio)->titolo,tit))	/*5*/ 
    return inizio;
  } 
  ... 
}

/* Funzioni per la gestione di una lista */

void elimina(lpointer* pcanc){
  lpointer temp; 	

  temp=*pcanc;	/*6*/
  *pcanc=(*pcanc)->next;	/*7*/	
  free(temp);	/*8*/
}

In 1 viene acquisito il titolo del libro da eliminare e passato, in 2, come parametro alla funzione che si occuperà di cercare il puntatore all’elemento da cancellare. Se tale puntatore contiene un valore valido (test effettuato a cominciare da 3), si passa come parametro (in 4) alla funzione elimina che procederà alla cancellazione dell’elemento dalla lista.

La funzione cerca è la stessa funzione esaminata nell’inserimento: cambia solo il confronto da effettuare (espresso in questo caso dalla 5). In questo caso si tratta di trovare la coincidenza del titolo conservato nel nodo con il titolo da cancellare.

L’eliminazione dell’elemento prevede in 6 la conservazione temporanea del puntatore al fine di recuperare l’area di memoria con la chiamata alla free della 8. La cancellazione dell’elemento è effettuata in 7: nella sequenza dei puntatori si salta l’elemento da non considerare aggiornando in tal modo la sequenza logica degli elementi.