Risolvere il seguente esercizio: si scriva una funzione che riceve come parametri una lista (ossia una variabile di tipo TipoLista) di interi e un intero; questa funzione modifica la lista aggiungendo l'intero come ultimo elemento.
Per risolvere questo esercizio, consideriamo la rappresentazione grafica della memoria prima e dopo l'aggiunta. Usiamo la lista (65 22 -90) come esempio di lista, e il valore 32 come valore da aggiungere in coda.
Dal momento che la lista è rappresentata usando delle strutture, e la lista va modificata, alcune di queste strutture devono essere modificate. Per modificare una struttura occorre sapere il suo indirizzo. Cerchiamo quindi di capire quali indirizzi ci servono. Dato che dobbiamo modificare l'ultima struttura della lista, ci serve il suo indirizzo. Facciamo quindi una scansione della lista, fino ad arrivare ad avere l'indirizzo dell'ultima struttura. Come al solito, se usiamo un puntatore t per scandire la lista, questo punta all'ultimo elemento quando t->next vale NULL.
Facciamo quindi una scansione della lista, portando avanti il puntatore t fino a che t->next vale NULL. A questo punto, t è l'indirizzo dell'ultima struttura della lista. Possiamo quindi aggiungere il nuovo elemento: t->next deve diventare l'indirizzo della prossima struttura della lista, ossia di una struttura nuova che abbiamo creato appositamente. Quindi, allochiamo una struttura con la funzione malloc, e mettiamo in t->next il valore di ritorno della funzione, che è l'indirizzo della nuova struttura.
A questo punto, possiamo mettere i valori nella struttura. Si può fare in due modi:
/* primo modo */ t->next->val=32; t->next->next=NULL; /* secondo modo */ t=t->next; t->val=32; t->next=NULL;
È abbastanza evidente che sono due modi equivalenti.
La funzione ora è quasi completa. Mancano solo alcune cose:
In effetti, si tratta dello stesso problema: nel caso in cui la lista è vuota, allora il puntatore al primo elemento della lista va modificato. Infatti, quando la lista è vuota vale NULL, quando si aggiunge un elemento in coda alla lista vuota deve puntare al primo (ed unico) elemento della lista, quindi non vale più NULL. Dato che questa variabile va modificata, occorre passarla per riferimento.
Si ricorda che la regola sul passaggio di liste a una funzione non è: "se la lista viene modificata, allora occorre passarla per riferimento". Questa regola non è esatta: vedere la pagina sul passaggio di liste per valore nel caso ci siano dei dubbi. La regola, al contrario, è: se il puntatore iniziale della lista viene modificato (ossia viene fatto puntare a un altro indirizzo) allora va passato per indirizzo. Quando si aggiunge un elemento a una lista non vuota, allora il puntatore iniziale contiene sempre l'indirizzo della prima struttura della lista, per cui non viene modificato. Quindi, se si sa con certezza che la lista non è vuota, si può anche passare per valore.
D'altra parte, se la lista è inizialmente vuota, il puntatore l contiene NULL prima della chiamata, mentre dopo la chiamata contiene l'indirizzo della prima struttura della lista. Quindi, è stato modificato. Dato che la modifica deve essere visibile dal programma principale, occorre passare la lista per indirizzo.
Se poi controlliamo il comportamento della funzione nel caso di lista vuota, ci aggorgiamo che non possiamo semplicemente fare una scansione. Infatti, una volta fatto t=*pl per iniziare la scansione, il valore di *pl non viene più modificato. Mettiamo quindi una istruzione condizionale per verificare se *pl vale NULL. In questo caso, la aggiunta di un elemento consiste nella allocazione di una struttura, il cui indirizzo iniziale va in *pl.
Si può facilmente verificare che, togliendo questo controllo alla funzione riportata qui sotto (contenuta nel programma incoda.c), si verifica un errore quando si tenta di aggiungere un elemento in coda a una lista vuota.
void InserisciCodaLista(TipoLista *pl, int e) {
TipoLista t;
/* caso lista inizialmente vuota */
if(*pl==NULL) {
*pl=malloc(sizeof(struct NodoLista));
(*pl)->val=e;
(*pl)->next=NULL;
return;
}
/* caso lista con almeno un elemento */
t=*pl;
/* vado avanti fino alla fine della lista */
while(t->next!=NULL)
t=t->next;
/* qui t punta all'ultima struttura della lista: ne
creo una nuova e sposto il puntatore in avanti */
t->next=malloc(sizeof(struct NodoLista));
t=t->next;
/* metto i valori nell'ultima struttura */
t->val=e;
t->next=NULL;
}