Il metodo che abbiamo usato nelle pagine precedenti per costruire una lista è basato sull'uso di sequenze di tipo *(*(*l).next).next).next. Questo chiaramente si può fare solo se il numero di elementi di cui è fatta una lista è fissato a priori, e soprattutto se è un numero piccolo.
La costruzione della lista fatta in questo modo avviene in modo sequenziale, ossia allocando prima la prima struttura, poi la seconda, ecc. In questa pagina vediamo come sia molto più facile costruire una lista partendo dal fondo, ossia iniziando ad allocare l'ultima struttura, poi la penultima, ecc. Questo ci consente di realizzare dei cicli per costruire delle liste (si possono fare cicli anche per la costruzione in avanti, ma è più complicato).
Vediamo ora quali sono i passi da compiere per costruire una lista a partire dall'ultimo elemento. Consideriamo la lista (2 -9 1). La situazione finale, a cui vogliamo arrivare, è qualcosa del genere:
Come al solito, non esiste nessuna garanzia che le strutture siano messe in questo ordine nella memoria.
Abbiamo detto che vogliamo iniziare dall'ultima struttura della lista, ossia quella che contiene 1. Quello che dobbiamo fare è allocare la struttura e metterci dentro 1 e NULL. La allocazione di fa con malloc. Per usare la struttura allocata, occorre sapere il suo indirizzo, che il valore di ritorno della malloc. Mettiamo questo indirizzo in una variabile:
s=malloc(sizeof(struct NodoLista)); (*s).val=1; (*s).next=NULL; |
|
Questa struttura deve essere l'ultima struttura della lista, con i campi riempiti con i valori che deve avere (l'ultimo elemento della lista e NULL). Occorre ora allocare la penultima struttura della lista. Questo si può ancora fare con una istruzione malloc. Occorre però fare attenzione a dove si memorizza il valore di ritorno, ossia l'indirizzo della nuova struttura.
Supponiamo infatti di fare la stessa cosa di prima, ossia s=malloc(sizeof(struct NodoLista)); e poi (*s).val=-9;. A questo punto, abbiamo il problema di cosa mettere nel campo next della nuova struttura. Questo è il campo next della penultima struttura, e quindi deve contenere l'indirizzo dell'ultima struttura. D'altra parte, l'indirizzo dell'ultima struttura stava in s, ma ora non c'è più: il suo valore è stato sovrascritto dall'indirizzo della penultima struttura quando abbiamo fatto l'ultima chiamata a malloc.
/* codice che NON FUNZIONA */ s=malloc(sizeof(struct NodoLista)); (*s).val=-9; (*s).next=...?; |
|
Tutto questo dice che, prima di fare s=malloc(sizeof(struct NodoLista)); dobbiamo salvare il valore che stava prima in s, ossia l'indirizzo dell'ultima struttura, perchè questo valore poi ci occorre. Quindi facciamo:
t=s; s=malloc(sizeof(struct NodoLista)); (*s).val=-9; (*s).next=t; |
|
In altre parole, in t (non disegnato) mettiamo il valore che aveva prima s, ossia l'indirizzo dell'ultima struttura. Poi facciamo la allocazione, mettendo in s l'indirizzo della struttura allocata, che deve diventare la penultima della lista. Possiamo ora riempire questa struttura: nel campo val ci mettiamo il valore del penultimo elemento della lista, ossia -9, e nel campo next ci mettiamo l'indirizzo dell'ultima struttura della lista. Questo indirizzo lo conosciamo, perchè lo abbiamo memorizzato in t.
Dobbiamo ora fare l'allocazione della terz'ultima struttura della lista (nel nostro caso è anche la prima, dato che la lista ha solo tre elementi). Facciamo l'allocazione mettendo l'indirizzo della struttura creata in s, ma prima occorre salvare da qualche parte il valore di s, dal momento che l'indirizzo della penultima struttura ci serve per poter collegare ad essa la terz'ultima. Quindi, prima salviamo il valore di s in una variabile, poi facciamo la allocazione e riempiamo i campi.
t=s; s=malloc(sizeof(struct NodoLista)); (*s).val=2; (*s).next=t; |
|
Si tratta di fare esattamente come prima: si salva il valore di s, che è l'indirizzo della struttura che è l'ultima a essere stata costruita, e in s ci si mette l'indirizzo ritornato dalla funzione malloc, ossia quello di una nuova struttura. Si mette nel campo val di questa struttura il valore opportuno, mentre nel campo puntatore ci si mette il valore di t, ossia l'indirizzo della struttura che era stata creata prima di questa.
L'ultima cosa che manca da fare è mettere in l l'indirizzo della prima struttura della sequenza, ossia di quella che contiene il primo elemento della lista. Questo indirizzo si trova già in s, quindi possiamo semplicemente fare:
l=s; |
|
Il codice completo è:
s=malloc(sizeof(struct NodoLista)); (*s).val=1; (*s).next=NULL; t=s; s=malloc(sizeof(struct NodoLista)); (*s).val=-9; (*s).next=t; t=s; s=malloc(sizeof(struct NodoLista)); (*s).val=2; (*s).next=t;
Si tratta di ripetere sempre lo stesso blocco di istruzioni. In particolare, possiamo fare una modifica a questo codice per semplificarlo ulteriormente: mettiamo inizialmente in s il valore NULL
s=NULL; t=s; s=malloc(sizeof(struct NodoLista)); (*s).val=1; (*s).next=t; t=s; s=malloc(sizeof(struct NodoLista)); (*s).val=-9; (*s).next=t; t=s; s=malloc(sizeof(struct NodoLista)); (*s).val=2; (*s).next=t;
Questo codice è esattamente uguale al precedente: s inizialmente contiene NULL, valore che viene poi copiato in t. La prima istruzione (*s).next=t è quindi equivalente a (*s).next=NULL, che è l'istruzione che stava nel codice precedente.
A questo punto è chiaro che si tratta di ripetere lo stesso blocco di quattro istruzioni per ogni struttura da creare. Ogni blocco crea una struttura, e la prima struttura creata è quella che contiene l'ultimo elemento della lista.
Vediamo ora un esempio in cui si può effettivamente realizzare una lista usando un ciclo. Supponiamo di volere la seguente lista:
(1 2 3 4 5 6 7 8 9 10 11 12 ... 1200)
Crearla scrivendo espressioni del tipo (*(*(*(*l).next).next).next).next è chiaramente impensabile. Possiamo però sfruttare il fatto che sappiamo perfettamente quanto vale l'ultimo elemento della lista, il penultimo, ecc. Possiamo quindi costruire prima la struttura che contiene 1200, poi quella che contiene 1199, ecc fino a quella che contiene il primo elemento della lista, ossia 1.
Si tratta quindi di fare un ciclo. Si noti che il ciclo non va da 1 a 1200. Infatti, fino a questo momento sappiamo solo come costruire la lista a partire dall'ultimo elemento. In altre parole, visto che dobbiamo prima creare la struttura che contiene 1200, poi quella che contiene 1199, poi 1198, ecc, è chiaro che dobbiamo partire dal 1200 e arrivare a 1. Questo è dovuto al fatto che costruiamo la lista nell'ordine opposto, dall'ultimo elemento al primo.
Possiamo quindi realizzare un ciclo che parte dall'ultimo elemento e arriva al primo. Ad ogni passo creaiamo una struttura e la colleghiamo al pezzo di lista che abbiamo costruito.
s=NULL;
for(i=1200; i>=1; i--) {
t=s;
s=malloc(sizeof(struct NodoLista));
(*s).val=i;
(*s).next=t;
}
l=s;
Nel caso ci fossero ancora dubbi, si provi a simulare su carta l'evoluzione della memoria nel caso in cui la lista da costruire abbia quattro elementi invece che milleduecento. Alla fine si vedrà che l contiene l'indirizzo di una struttura il cui campo val è 1, e seguendo i puntatori si leggono gli altri valori 2, 3 e 4.
Il programma completo indietro.c che costruisce questa lista e la stampa, è qui sotto.
/*
Crea una lista composta dai
numeri (1 2 3 4 5 ... 1200)
*/
#include<stdlib.h>
#include<stdio.h>
struct NodoLista {
int val;
struct NodoLista *next;
};
typedef struct NodoLista *TipoLista;
int main() {
TipoLista l;
struct NodoLista *s, *t;
int i;
struct NodoLista *q;
/* costruzione dal fondo: si parte allocando
l'ultima struttura, e poi si risale fino alla
prima, collegando ogni struttura con la successiva */
s=NULL;
for(i=1200; i>=1; i--) {
t=s;
s=malloc(sizeof(struct NodoLista));
(*s).val=i;
(*s).next=t;
}
l=s;
/* stampa la lista */
q=l;
while(q!=NULL) {
printf("%d ", (*q).val);
q=(*q).next;
}
return 0;
}