Hasta la lista, amigos!

di Stefano Casini

A Roma c'è un posto, sul colle Gianicolo, chiamato la quercia del Tasso. Deriva il nome da un albero, una quercia per l'appunto, sotto la quale era facile trovare il famoso poeta Torquato Tasso, autore della "Gerusalemme liberata", nei giorni di bel tempo.
Quello che non tutti sanno è che il celebre poeta soleva frequentare, in alternativa alla quercia, anche un altro albero, un tasso, che veniva chiamato, per distinguerlo dagli altri tassi, il tasso del Tasso.
Tra le fronde del tasso viveva un simpatico roditore, guarda caso un tasso, molto benvoluto al Tasso poeta, e che pertanto veniva additato come il tasso del Tasso. Poichè c'era un altro tasso nella quercia del Tasso, bisognava specificare se si parlava del tasso della quercia del Tasso o del tasso del tasso del Tasso.
Se poi vogliamo aggiungere che il Tasso del tasso del tasso teneva i soldi in banca, dove per gli interessi aveva un buon tasso (erano in pochi ad avere il tasso del Tasso del tasso del tasso) ... se volete sapere come va a finire la storia leggetevi "Vite degli uomini illustri" di Achille Campanile.

Il tasso del tasso del tasso del tasso ...
L'introduzione vuole mettere in evidenza la nascita di una serie di elementi tutti uguali (tasso) collegati dalla preposizione articolata (del), e da un articolo iniziale (il); il contenuto concettuale di ciascun elemento è però diverso, di volta in volta è poeta, albero, animale, interesse. Eugenio, programmatore ingenuo, si sta chiedendo: "Ma questo che c'entra col C? Se mi serve mi dichiaro come variabile globale un bell'array di tassi da 1000 elementi, così ci posso mettere tutti i tassi di Campanile e mi avanza lo spazio anche per qualche scoiattolo!"
Abbiamo visto nell'articolo precedente "Nei dintorni di malloc" (vedi Beta 05/96) che l'allocazione dinamica della memoria è un potente strumento offerto dal linguaggio C per gestire dati sulla cui dimensione non si è in grado di esprimersi a priori. Se, in linea di principio, è sempre possibile, una volta allocato dinamicamente un certo numero di byte, eseguire un'operazione di riallocazione per aumentare o diminuire la dimensione del blocco di memoria allocato, in certe condizioni è possibile avvalersi di una particolare struttura dati molto potente e flessibile, che risponde al nome di lista.
La lista è un insieme di elementi tutti dello stesso tipo, creati in ordine sequenziale, ognuno dei quali contiene al suo interno l'indirizzo dell'elemento precedente e/o successivo. Operativamente un elemento della lista è una struttura che contiene come uno dei suoi membri un puntatore alla struttura. Vediamo un esempio:

typedef struct tag_ELEMENTO
{
	char membro1;
	int membro2;
	struct tag_ELEMENTO * pPrecedente;
	struct tag_ELEMENTO * pSuccessivo;
}
ELEMENTO;
typedef ELEMENTO * P_ELEMENTO;

Nell'esempio abbiamo definito un tipo di dato, precisamente una struttura, chiamato ELEMENTO, che contiene come membri un intero, un carattere e due puntatori alla struttura ELEMENTO: uno che punterà l'elemento precedente della lista, l'altro che punterà il successivo.
Normalmente uno dei due puntatori non è necessario; infatti le liste che si implementano generalmente sono di due specie: quelle del tipo LIFO (Last In First Out), anche detta pila o stack, e quelle del tipo FIFO (First In First Out), anche detta coda.
Nella pila ci interessa avere sotto mano solo l'ultimo elemento allocato, perchè da lui potremo risalire, scorrendo la lista all'indietro, fino all'elemento iniziale; viceversa, nella coda l'elemento chiave è il primo della lista, perchè a partire da esso potremo arrivare, scorrendo in avanti, fino all'ultimo. Nel caso della pila il puntatore contenuto all'interno dell'elemento punta all'elemento precedente, mentre nella coda il puntatore punta all'elemento successivo; se invece vogliamo fare una lista generica, l'elemento conterrà entrambi i puntatori. Infine abbiamo definito il tipo di dato P_ELEMENTO, che altro non è che il puntatore ad un elemento della lista, che ci serve per comodità di scrittura del codice: infatti i membri pPrecedente e pSuccessivo, che nella definizione della struttura sono necessariamente del tipo struct tag_ELEMENTO, saranno in seguito richiamati come P_ELEMENTO.
In questo esempio si vede l'utilità dell'etichetta (tag) nella dichiarazione delle strutture: senza il tag_ELEMENTO, non sarebbe stato possibile definire all'interno della struttura ELEMENTO i puntatori a se stessa.

Come gestire una lista
Per gestire una lista generica, le funzioni di cui abbiamo bisogno sono quelle che> permettono di creare, inserire, rimuovere un elemento, e quelle che permettono di scorrere e distruggere la lista. Facciamo un esempio applicato ad una pila.

void main(void)
{
	int numeroelementi = 5;
	int i;
	int posizioneElemento = 2;
	P_ELEMENTO pPila = NULL;

	for(i = 0; i < numeroelementi; i++)
		pPila = AggiungiElemento(pPila, 'A' + (i % 26), i);
	/* creiamo la lista aggiungendo i vari elementi */

	RimuoviElemento(&pPila, posizioneElemento);
	/* rimuoviamo uno degli elementi della pila, contando da zero partendo 		
	dall'ultimo */

	CancellaLista(&pPila);
	/* cancelliamo tutti gli elementi della pila */
}

P_ELEMENTO AggiungiElemento(P_ELEMENTO pPila, char membro1, int membro2)
{
	P_ELEMENTO pElem;

	pElem =  malloc(sizeof(ELEMENTO));
	/* allochiamo memoria per un elemento della lista */

	if(!pElem)
		return pPila;
	/* se l'allocazione fallisce, ritorniamo il puntatore alla pila */

	pElem->membro1 = membro1;
	pElem->membro2 = membro2;
	pElem->pPrecedente = pPila;
	/* riempiamo i membri della struttura*/

	return pElem;
}

void CancellaLista(P_ELEMENTO * ppPila)
{
	while(* pPila)
		* pPila = RimuoviUltimoElemento(* pPila);
	/* cancelliamo uno per uno tutti gli elementi della lista */
}

P_ELEMENTO RimuoviUltimoElemento(P_ELEMENTO pPila)
{
	P_ELEMENTO pElem;

	if(!pPila)
		return NULL;
	/* controlliamo che ci venga passato un puntatore valido */

	pElem = pPila->pPrecedente;
	/* salviamo nella variabile pElem il puntatore al penultimo elemento */

	free(pPila);
	/* cancelliamo dalla memoria l'ultimo elemento */
	
	return pElem;
	/* adesso pElem punta all'ultimo elemento */
}

void RimuoviElemento(P_ELEMENTO *ppPila, int posizioneElemento)
{
	P_ELEMENTO pElemCorrente;	
	P_ELEMENTO pAppoggio;
	
	if(! * ppPila)
		return;
	/* controlliamo che ci venga passato un puntatore valido */

	if(posizioneElemento == 0)
	{
		* ppPila = RimuoviUltimoElemento(* ppPila);
		return;
	}
	/* se l'elemento da rimuovere è l'ultimo, chiamiamo la funzione apposita */
	
	/* adesso possono presentarsi due possibilità: l'elemento da rimuovere è
	contenuto nella lista, oppure la lista è più corta del previsto, per cui l'elemento
	non esiste */
	
	pElemCorrente = * ppPila;
	/* pElemCorrente punta all'elemento su cui ci portiamo mano mano che
	scorriamo la lista a ritroso: iniziamo a scorrere la lista dall'ultimo elemento,
	naturalmente */
	while(--posizioneElemento)
	{
		pElemCorrente = pElemCorrente->pPrecedente;
		if(!pElemCorrente->pPrecedente)
			return;
	}
	/* se scorrendo la lista ci troviamo che l'elemento corrente non ne ha altri
	precedenti, vuol dire che la lista è più corta del previsto, per cui la funzione
	ritorna senza fare nulla */


	pAppoggio = pElemCorrente->pPrecedente;
	pElemCorrente->pPrecedente = pElemCorrente->pPrecedente->pPrecedente;
	free(pAppoggio);
	/* se invece l'elemento da togliere è contenuto nella lista dovremo usare una
	variabile di appoggio per il puntatore all'elemento da togliere.
	pElemCorrente->pPrecedente->pPrecedente è equivalente a scrivere
	pAppoggio->pPrecedente, ma fa più effetto su Eugenio */

	return;
}

typedef struct tag_PIATTO
{
	char * piatto;
	int costo;
	struct tag_PIATTO * pPrecedente;
	struct tag_PIATTO * pSuccessivo;
}
PIATTO;
typedef PIATTO * P_PIATTO;

typedef struct tag_COMMENSALE
{
	char * nome;
	P_PIATTO pPiattiOrdinati;
	struct tag_COMMENSALE * pPrecedente;
	struct tag_COMMENSALE * pSuccessivo;
}
COMMENSALE;
typedef COMMENSALE * P_COMMENSALE;

typedef struct tag_TAVOLO
{
	int numerotavolo;
	P_COMMENSALE pCliente;
	struct tag_TAVOLO * pPrecedente;
	struct tag_TAVOLO * pSuccessivo;
}
TAVOLO;
typedef TAVOLO * P_TAVOLO;

void main(void)
{
	P_TAVOLO pTavolo = NULL;
	P_TAVOLO pNostroTavolo = NULL;
	int numerotavolo = 3;
	int conto;

	pTavolo =  ............
	/* creiamo la lista dei tavoli aggiungendo i vari elementi */
	
	.......................
	/* aggiungiamo ai tavoli la lista delle persone e dei piatti ordinati */

	pNostroTavolo = CercaTavolo(pTavolo, numerotavolo);
	/* cerchiamo il nostro tavolo nella lista dei tavoli */

	conto = CalcolaConto(pNostroTavolo);
	/* calcoliamo il conto per il nostro tavolo */

	RimuoviTavolo(&pTavolo, pNostroTavolo);
	/* rimuoviamo il nostro tavolo dalla lista dei tavoli */

	.............
	/* quando tutti i tavoli sono stati rimossi, è ora di chiudere il ristorante */
}

P_TAVOLO CercaTavolo(P_TAVOLO pTavolo, int numerotavolo)
{
	P_TAVOLO pElemCorrente;

	pElemCorrente = pTavolo;	
	while(* pElemCorrente)
	{
		if(pElemCorrente->numerotavolo == numerotavolo)
			break;
		pElemCorrente = pElemCorrente->pSuccessivo;
	}
	/* scorriamo la lista dei tavoli finché non troviamo il nostro tavolo */
	
	return pElemCorrente;
}

int CalcolaConto(P_TAVOLO pTavolo)
{
	P_COMMENSALE pCommensale;
	int conto = 0;

	pCommensale = pTavolo->pCliente;
	/* questo è il primo dei clienti del tavolo */
	
	while(pCommensale)
	{
		P_PIATTO pPiatto;
	
		pPiatto = pCommensale->pPiatto;
		/* questo è il primo piatto ordinato dal cliente */

		while(pPiatto)
		{
			conto += pPiatto->costo;
			pPiatto = pPiatto->pSuccessivo;
			/* passo al piatto successivo */
		}
	
		pCommensale = pCommensale->pSuccessivo;
		/* passo al cliente successivo */
	}
	return conto;
}

void RimuoviTavolo(P_TAVOLO * ppTavolo, P_TAVOLO pNostroTavolo)
{
	if(* ppTavolo == pNostroTavolo)
		* ppTavolo = pNostroTavolo->pSuccessivo;
	/* se il nostro tavolo è il primo della lista, dopo averlo sganciato il puntatore
	all'inizio della lista dei tavoli dovrà essere spostato sul tavolo successivo */
	
	if(pNostroTavolo->pSuccessivo != NULL)
		pNostroTavolo->pSuccessivo->pPrecedente = pNostroTavolo->pPrecedente;
	if(pNostroTavolo->pPrecedente != NULL)
		pNostroTavolo->pPrecedente->pSuccessivo = pNostroTavolo->pSuccessivo;
	/* sganciamo il nostro tavolo dalla lista, riagganciando tra loro il tavolo
	precedente e quello successivo, controllando che le eccezioni quando il tavolo
	da sganciare è il primo o l'ultimo della lista */

	...........
	/* liberiamo la memoria allocata per la lista dei commensali e le liste dei piatti
	ordinati al nostro tavolo */
	
	free(pNostroTavolo);
	/* liberiamo la memoria allocata per il nostro tavolo */
}

• la lista permette di gestire in maniera dinamica un'enorme quantità di dati del medesimo tipo, portandosi appresso il solo puntatore all'elemento iniziale (o finale);
• le funzioni di gestione delle liste sono fondalmente quelle di aggiunta, rimozione e lettura/modifica di un elemento della lista;
• esistono due particolari tipi di lista, usati per implementare le situazioni in cui si ha un processo di tipo LIFO o di tipo FIFO: la pila, dove si mantiene il puntatore all'ultimo elemento aggiunto, e la coda, dove viceversa conta il puntatore al primo elemento;
• il puntatore ad un singolo elemento di una lista è, a sua volta, un puntatore ad una lista;
• tra i membri dell'elemento di una lista, può esserci uno o più puntatori a liste del medesimo tipo o di altro tipo;
• invitate Eugenio al ristorante, chiedetegli di scrivere un pò di codice di gestione di liste o di pagare il conto, ed avrete mangiato gratis!