In questa pagina vediamo come si possano rappresentare delle sequenze di elementi usando la definizione di struttura data nella pagina precedente, ossia:
struct NodoLista {
int val;
struct NodoLista *next;
};
typedef struct NodoLista *TipoLista;
Quale è il significato di questa definizione? In C, le definizioni (come tutto il resto) vanno interpretate in senso letterale. Quando si dichiara una variabile di tipo TipoLista, per esempio
TipoLista l;
questo equivale a dichiarare una variabile che contiene un puntatore, ossia un indirizzo di memoria. In particolare, la zona puntata (ossia quella che comincia a questo indirizzo) deve contenere una struttura di tipo struct NodoLista. Questa struttura è identificata, come al solito, da *l.
In base alla definizione di tipo, ogni struttura di tipo struct NodoLista è composta da due campi. Nel nostro caso, i due campi sono (*l).val e (*l).next. La prima è semplicemente una variabile intera, e quindi non ha nulla di complicato. La seconda variabile è un puntatore. In memoria, quello che succede è che la struttura occupa 4+4=8 byte, nell'ipotesi che sia interi che puntatori occupino quattro byte ciascuno.
Questa figura si ottiene semplicemente interpretando in modo letterale le definizioni di tipo. Il campo puntatore della struttura è semplicemente un numero, per cui sappiamo quanti byte occupa in memoria (anche senza sapere cosa c'è a partire dall'indirizzo scritto dentro). D'altra parte, la definizione di tipo ci dice anche che questo puntatore (*l).next è di tipo struct NodoLista *, e quindi la zona di memoria che inizia dall'indirizzo in (*l).next contiene una struttura di tipo struct NodoLista. In altre parole, (*l).next individua una zona di memoria in cui si trova una struttura analoga a *l.
Si noti che è compito del programmatore allocare le zone di memoria, ossia riservarle per contenere delle strutture. In altre parole, quando si definisce una variabile di tipo lista con TipoLista l, l'unica zona di memoria che viene allocata è quella per la variabile l. È poi compito del programmatore allocare anche la memoria per la struttura. Quello che il linguaggio garantisce è solo che questa zona verrà interpretata come una struttura di tipo struct NodoLista.
Lo stesso discorso vale per la zona di memoria puntata da (*l).next. Se questa zona di memoria è stata allocata correttamente, allora è una struttura di tipo struct NodoLista. Quindi, abbiamo in memoria:
La struttura è fatta nello stesso modo della precedente, per cui è composta da un intero e da un puntatore. Questo puntatore indica una zona di memoria in cui inizia una struttura dello stesso tipo. D'altra parte, il puntatore può anche valere NULL.
Questo meccanismo consente di rappresentare sequenze di interi di lunghezza generica. Infatti, mettiamo il primo intero nella prima struttura, il secondo nella seconda struttura, ecc. Ogni struttura contiene anche un puntatore, che dà l'indirizzo della successiva struttura. Quando arriviamo all'ultimo elemento, lo mettiamo nell'ultima struttura, e mettiamo NULL come puntatore.
Supponiamo di voler per esempio rappresentare la sequenza (2 -9 1). Per prima cosa, allochiamo la prima struttura, e ci mettiamo il primo elemento. Per allocare una struttura, usiamo come al solito la funzione malloc. Per poter poi accedere alla struttura (per esempio, per scriverci dentro il primo elemento della lista) ci serve sapere il suo indirizzo. QUesto è dato dal valore di ritorno della funzione malloc. Dato che l deve contenere questo indirizzo, facciamo l=malloc(...) che alloca la prima struttura e mette il suo indirizzo in l.
| Codice | Memoria | |
TipoLista l; l=malloc(sizeof(struct NodoLista)); (*l).val=2; |
|
Nella rappresentazione con frecciae, dato che ho messo in l l'indirizzo della struttura allocata, ho una freccia da l alla struttura. Le parentesi di (*l).val sono necessarie perchè, secondo le regole di precedenza degli operatori del C, la espressione *l.next viene interpretata come *(l.next). Questo produce un errore perchè l non è una struttura, per cui l.next non è una espressione valida.
Dal momento che dobbiamo ancora memorizzare degli elementi, ci serve una seconda struttura, il cui indirizzo va messo in (*l).next. La funzione malloc alloca una struttura e restituisce il suo indirizzo, che va messo in (*l).next.
| Codice | Memoria | |
(*l).next=malloc(sizeof(struct Sequenza)); |
|
A questo punto, abbiamo due strutture in memorie, e in particolare (*l).next contiene l'indirizzo della seconda. Da questo segue che *(*l).next è esattamente la seconda struttura. Quindi, per mettere il secondo intero nella seconda struttura, facciamo:
| Codice | Memoria | |
(*(*l).next).val=-9; |
|
Questo significa: dato che (*l).next è un puntatore a struttura, allora *(*l).next è una struttura, quindi è composta da due variabili, la prima della quali è l'intero (*(*l).next).val (le parentesi sono necessarie per una questione di precedenza degli operatori); la seconda variabile di questo struttura, ossia (*(*l).next).next è un puntatore. In particolare, è l'indirizzo iniziale di una struttura di tipo struct NodoLista. Per essere più precisi, è l'indirizzo della terza struttura, quella che contiene il terzo elemento della sequenza. Dal momento che la lista ha tre elementi, questa terza struttura deve esistere, e deve contenere il valore 1 nel campo intero. Per prima cosa, questa struttura va allocata:
| Codice | Memoria | |
(*(*l).next).next=malloc(sizeof(struct Sequenza)); |
|
Ora possiamo dire che *(*(*l).next).next è una struttura, e in particolare è la terza struttura. Quindi, il numero intero che contiene deve valere -1; dal momento che non ci sono altri elementi nella lista, mettiamo a NULL il valore puntatore di questa struttura per indicare che la sequenza finisce qui.
| Codice | Memoria | |
(*(*(*l).next).next).val=-1; (*(*(*l).next).next).next=NULL; |
|
Nota: nelle figure di sopra le strutture sono state disegnate l'una sopra l'altra. In realtà non esiste nessuna garanzia che la allocazione di memoria faccia una cosa del genere. Quello che si potrebbe avere allla fine della costruzione è anche una cosa del genere:
