Per scansione di una lista si intende la ripetizione di una stessa operazione su tutti gli elementi della lista, a partire dal primo e andando avanti in ordine. Vediamo ora un semplice caso di scansione: quello della stampa di una lista. Dal momento che vogliamo ripetere la stampa su tutti gli elementi della lista, in ordine, si tratta appunto di fare una scansione della lista.
Vediamo prima un modo che si ottiene facilmente dalla definizione. Supponiamo quindi che l sia una variabile di tipo TipoLista. Per definizione, si tratta di un puntatore a una struttura *l a due campi: il primo elemento della lista è il campo val di questa struttura, ossia (*l).val. Il secondo elemento della sequenza si ottiene considerando che la seconda struttura è *(*l).next, e quindi il secondo elemento è (*(*l).next).val. In modo simile, il terzo elemento è (*(*(*l).next).next).val. Possiamo quindi stampare i primi tre elementi della sequenza con il programma listano.c riportato qui sotto.
/*
Stampa dei primi tre elementi di una lista.
*/
#include<stdlib.h>
/* definizione di tipo */
struct NodoLista {
int val;
struct NodoLista *next;
};
typedef struct NodoLista *TipoLista;
/*
main
*/
int main () {
TipoLista l;
/* creazione lista (2 -9 1) */
l=malloc(sizeof(struct NodoLista));
(*l).val=2;
(*l).next=malloc(sizeof(struct NodoLista));
(*(*l).next).val=-9;
(*(*l).next).next=malloc(sizeof(struct NodoLista));
(*(*(*l).next).next).val=1;
(*(*(*l).next).next).next=NULL;
/* stampa della lista l */
printf("%d ", (*l).val);
printf("%d ", (*(*l).next).val);
printf("%d ", (*(*(*l).next).next).val);
printf("\n");
return 0;
}
Il programma di sopra va bene se la lista è composta da tre elementi. Per stampare una lista più lunga servirebbe un'altra chiamata alla funzione printf per stampare il quarto elemento, ecc. Da notare che le espressioni che danno l'elemento della lista a partire dal puntatore iniziale diventano sempre più complicate mano a mano che si avanza nella lista (si provi a scrivere la espressione che dà il decimo elemento).
Vediamo ora un meccanismo più semplice per stampare tutti gli elementi in ordine. L'idea di base è che, dato che tutte le strutture della lista sono analoghe, si può realizzare un ciclo. Per capire quando uscire da questo ciclo, sfruttiamo il fatto che l'ultima struttura ha NULL nel campo puntatore.
Cominciamo a modificare il codice del programma di sopra per evitare di ripetere le espressioni lunghe. Dato che la espressione (*l).next compare molto spesso, la memorizziamo in una variabile. Il tipo deve coincidere con il tipo di (*l).next, per cui questa nuova variabile deve essere di tipo puntatore a struttura struct NodoLista, oppure di tipo TipoLista, che è eqivalente. Abbiamo quindi una dichiarazione TipoLista s; e poi la istruzione:
printf("%d ", (*l).val);
s=(*l).next;
printf("%d ", (*s).val);
Questo codice si ottiene semplicemente inserendo l'istruzione di assegnazione su s, e sostituendo a (*l).next la variabile s nella seconda istruzione si stampa. In altre parole, dal momento che questa variabile s contiene una copia dell'indirizzo della seconda struttura della sequenza, il secondo elemento della lista è (*s).val.
La successiva struttura della sequenza (la terza) ha indirizzo (*s).next. Dato che la seconda struttura non ci serve più (è stata già stampata), possiamo direttamente memorizzare l'indirizzo della terza struttura nella variabile s, e da questa stampare il campo val della struttura:
s=(*s).next;
printf("%d ", (*s).val);
A questo punto, possiamo di nuovo stampare (*s).val, e passare alla successiva struttura con s=(*s).next;. Questo si conclude quando si arriva a una struttura il cui campo next vale NULL.
Il punto fondamentale è che possiamo usare una variabile puntatore s per memorizzare l'indirizzo della struttura che stiamo guardando, e ogni volta facciamo gli stessi passi:
Possiamo seguire questa strategia anche per la stampa del primo elemento della lista: basta che inizialmente copiamo l'indirizzo della prima struttura in s. Il ciclo di scansione della sequenza diventa quindi:
s=l;
while(s!=NULL) {
printf("%d ", (*s).val);
s=(*s).next;
}
printf("\n");
Riportiamo qui sotto il codice completo del programma listamain.c che crea un sequenza di tre elementi e li stampa. Da notare come la parte di stampa sia totalmente indipendente dalla lunghezza della sequenza. Inoltre, rimpiazzando la istruzione di stampa printf("%d ", (*s).val) con qualche altra istruzione, è possibile fare una qualsiasi operazione sugli elementi della sequenza.
/*
Definizione di lista, creazione, stampa.
*/
#include<stdlib.h>
struct NodoLista {
int val;
struct NodoLista *next;
};
typedef struct NodoLista *TipoLista;
/*
main
*/
int main() {
TipoLista l;
TipoLista s;
/* creazione della lista (2 -9 1) */
l=malloc(sizeof(struct NodoLista));
(*l).val=2;
(*l).next=malloc(sizeof(struct NodoLista));
(*(*l).next).val=-9;
(*(*l).next).next=malloc(sizeof(struct NodoLista));
(*(*(*l).next).next).val=1;
(*(*(*l).next).next).next=NULL;
/* stampa la lista */
s=l;
while(s!=NULL) {
printf("%d ", (*s).val);
s=(*s).next;
}
printf("\n");
return 0;
}
Il codice di stampa della sequenza, come abbiamo detto, funziona con liste di qualsiasi lunghezza. È quindi utile realizzare una funzione che stampa gli elementi di una lista. Il programma seguente lista.c definisce e usa una funzione di stampa di una sequenza di interi.
/*
Definizione di lista, creazione, stampa.
*/
#include<stdlib.h>
struct NodoLista {
int val;
struct NodoLista *next;
};
typedef struct NodoLista *TipoLista;
/*
stampa di una lista di lunghezza generica
*/
void StampaLista(TipoLista l) {
TipoLista s;
s=l;
while(s!=NULL) {
printf("%d ", (*s).val);
s=(*s).next;
}
printf("\n");
}
/*
main
*/
int main() {
TipoLista l;
/* creazione della lista (2 -9 1) */
l=malloc(sizeof(struct NodoLista));
(*l).val=2;
(*l).next=malloc(sizeof(struct NodoLista));
(*(*l).next).val=-9;
(*(*l).next).next=malloc(sizeof(struct NodoLista));
(*(*(*l).next).next).val=1;
(*(*(*l).next).next).next=NULL;
/* stampa la lista */
StampaLista(l);
return 0;
}
Una osservazione importante da fare è che la funzione riceve come parametro il puntatore alla prima struttura e basta. A partire dalla prima struttura è possibile capire quali sono i successivi elementi. Questo indica che è corretto dire che una variabile di tipo TipoLista rappresenta una lista di interi: la sequenza definita da una variabile di questo tipo è data dalla sequenza di interi che si incontrano seguendo i puntatori da una struttura all'altra.
Vediamo di seguito la evoluzione della memoria quando si esegue il programma di sopra. Quando si assegna a s il valore di l quello che succede è che queste il valore di l viene copiato in s. Quindi, l'indirizzo che è individuato da l ora è anche l'indirizzo di memoria individuato da s.
Nella rappresentazione con freccie, possiamo dire che la freccia di s, dopo l'assegnamento s=l, ha la punta nella stessa posizione delle punta della freccia di l. Se quindi eseguiamo la prima istruzione s=l, quello che otteniamo è che la freccia di s va alla locazione iniziale della prima struttura.
La stampa di (*s).val produce effettivamente la stampa del primo elemento della lista, che è 2. Quando si esegue l'istruzione s=(*s).next, quello che succede è che la freccia di s deve puntare alla stessa locazione della freccia di (*s).next, quindi, guardando il disegno di sopra, è chiaro che si arriva alla situazione qui sotto:
Si stampa (*s).val, che è -9, ossia effettivamente il secondo elemento della lista. Si ripete ancora la assegnazione s=(*s).next. Si noti che la struttura *s, e quindi la variabile (*s).next, è diversa da quello che era in precedenza. Quello che si ottiene è che le due freccie puntano allo stesso indirizzo.
Si stampa (*s).val, che vale -1, e che è il terzo elemento della lista. Si esegue nuovamente s=(*s).next, ma in questo momento (*s).next vale NULL. Quindi, nella variabile s si mette NULL.
A questo punto la condizione del ciclo while è falsa, dal momento che s non è più diverso da NULL. Quindi, si esce dal ciclo. Se si va a vedere le stampe che sono state fatte, si nota come in effetti siano stati stampati gli elementi della lista, in ordine. È chiaro che questa funzione va bene per liste di lunghezza generica.