Nella sezione precedente abbiamo descritto una lista come costituita da elementi, ciascuno avente una struttura formata da un campo dati e un campo che riferisse l'elemento ad esso successivo. Cominciamo allora a costruire un elemento; utilizzeremo, come è ovvio, una struttura7.4, avente un costruttore che forzi l'utilizzatore ad inizializzare ogni elemento creato:
struct elem { int info; elem* next; elem (int Info, elem* Next) { info = Info; next = Next; } }; |
elem
7.5: abbiamo un campo intero info
che contiene l'informazione della cella, che in questo caso è un intero; in tutto il capitolo supporremo sempre di lavorare con liste di interi, ma nulla vieta che le liste possano contenere un qualunque tipo di dato, primitivo o derivato. Oltre all'informazione un elemento contiene, come detto, un puntatore all'elemento a esso successivo next
; ovviamente nel caso di elemento terminale (ultimo nella lista) tale puntatore vale 0
. Infine un elemento ha un costruttore che inizializza entrambi i campi della struttura; in tale maniera non è possibile costruire un elemento avente i campi fluttuanti, il che sarebbe pericoloso perché è presente un campo puntatore. Un esempio grafico di una lista è i seguente:
elem*
, che nel nostro esempio è chiamato lista
; il valore di esso è l'indirizzo della prima cella. Essa d'altronde contiene, oltre al campo informazione, anche l'indirizzo della cella successiva, e così via fino all'ultima cella, che ha next
nullo; nel grafico l'ultima cella risulta messa a terra, per indicare la sua posizione terminale. Un esempio che ci permette di costruire la lista disegnata (ovviamente gli indirizzi non corrispondono) è il seguente:
// ex7_7_1 // esempio di lista // Si ricordi di copiare la definizione di elem // in questo punto del programma void main() { elem* lista; // puntatore al primo elemento // gli elementi vanno creati in ordine inverso lista = new elem (4, 0); // l'elemento e` messo a terra lista = new elem (3, lista); lista = new elem (7, lista); }
Vediamo ora alcuni gruppi di funzioni sulle liste.