Consideriamo ancora una volta il problema di specificare l'insieme dei figli di ogni nodo. Per ogni nodo c'è una struttura. Abbiamo quindi bisogno di specificare, per ogni struttura, quali sono le strutture che contengono i figli. Quindi, per ogni struttura dobbiamo rappresentare l'insieme degli indirizzi delle strutture che rappresentano i figli.
I vettori dinamici sono uno dei metodi che abbiamo visto per rappresentare insieme di cui non conosciamo a priori il numero o il numero massimo di elementi. Un secondo metodo è quello delle liste collegate. In questa pagina vediamo questo secondo metodo.
Con una lista possiamo rappresentare un insieme di interi. Per esempio, per l'insieme di tre elemento -32, 40 e 51 avremmo una rappresentazione del genere:
È chiaro che al posto degli interi si può mettere un qualsiasi altro tipo di dati, e al posto di un insieme di tre interi avremmo rappresentato un insieme di tre dati. Nel nostro caso, abbiamo bisogno di rappresentare un insieme di indirizzi. Ma questo non crea problemi: al posto del tipo int, avremo che il primo campo delle strutture sarà un indirizzo:
La dichiarazione di dati per le lista sarà poi modificata in modo tale che le strutture contengano un puntatore al posto di un intero, come si vedrà più avanti.
Per rappresentare i figli della radice abbiamo bisogno di una lista con tre elementi, dato che la radice ha tre figli.
La struttura che rappresenta il nodo 3 deve indicare quali sono i suoi successori, quindi il puntatore iniziale della lista lo mettiamo in un campo di questa struttura.
La lista deve contenere gli indirizzi delle strutture che rappresentano i successori della radice. Quindi, nelle posizioni della lista che abbiamo lasciato bianche, mettiamo questi indirizzi.
L'idea è che il secondo campo della struttura struct NodoLista è il puntatore iniziale a una lista, i cui elementi sono, invece che interi, gli indirizzi delle strutture che rappresentano i figli della struttura. La stessa cosa va fatta per tutti gli altri nodi: il nodo -2 ha un solo figlio, quindi avremo una lista con un solo nodo. Per il nodo 4, che non ha figli, si usa la lista vuota, ossia NULL.
Anche se tutte le strutture della figura hanno due elementi, non sono tutte uguali. Infatti, la struttura che rappresenta un nodo ha come campi un intero (il valore del nodo) e un puntatore a una struttura dell'altro tipo (questo è il puntatore iniziale della lista che contiene i figli del nodo).
struct NodoAlbero {
int info;
struct NodoLista *figli;
};
typedef struct NodoAlbero *TipoAlbero;
Le strutture delle lista sono invece composte di due puntatori. Il primo è un puntatore a uno dei figli, ossia è l'indirizzo di una struttura di quelle di sopra. Il secondo campo è invece il solito campo next, ossia un puntatore al prossimo elemento della lista (ossia contiene l'indirizzo della prossima struttura).
struct NodoLista {
struct NodoAlbero *figlio;
struct NodoLista *next;
};
Si può anche vedere questa dichiarazione come una variante della definizione di struttura standard delle liste, in cui al posto del campo info si è messo un puntatore.