Rappresentare sequenze in memoria

Supponiamo di voler rappresentare una specifica sequenza di interi in memoria, per esempio la sequenza (-2 12), che è composta da due soli interi. Possiamo usare per esempio un array statico di due soli elementi, mettendo -2 nella prima posizione e 12 nella seconda, oppure un array dinamico con la stessa disposizione. Se sappiamo che la sequenza da rappresentare sarà sempre composta da due elementi, possiamo anche usare una struttura:

struct SeqDue {
  int primo;
  int secondo;
};

Una rappresentazione alternativa, cha usa ancora le strutture, è la seguente:

struct SeqDue {
  int primo;
  int *secondo;
};

Questo metodo di rappresentazione può, a prima vista, sembrare illogico: perchè usare un puntatore a intero per il secondo elemento, invece che un intero? Vedremo poi che questa seconda rappresentazione si può estendere per rappresentare sequenze di lunghezza generica. Se la variabile x viene dichiarata di tipo struct SeqDue, allora la sua rappresentazione in memoria sarà la seguente:

Il punto fondamentale da tenere in considerazione è che vogliamo che la sequenza sia rappresentabile come una unica variabile. Nel caso di sopra, è vero che la variabile x non contiene il secondo intero, però è anche vero che da x siamo comunque in grado di risalire sia al primo che al secondo elemento della sequenza. Possiamo quindi, per esempio, passare x a una funzione, e questa funzione è in grado di capire quali sono gli elementi della sequenza. Ad esempio, possiamo scrivere una funzione che riceve la sola variabile x e stampa gli elementi della sequenza. In generale, la regola che dobbiamo rispettare nel definire un meccanismo di rappresentazione delle liste è:

ogni lista deve essere rappresentabile usando una sola variabile, ossia, dato il valore di questa variabile deve essere possibile capire quali sono tutti gli elementi della sequenza.

Possiamo pensare di estendere questo meccanismo su una sequenza di tre elementi. Vediamo un modo possibile di rappresentare in memoria una sequenza di tre elementi (non ci preoccupiamo, per ora, della definizione dei tipi). Possiamo organizzare i dati in questo modo: usiamo una struttura il cui primo campo è il primo elemento della sequenza, mentre il secondo campo è un puntatore, che contiene quindi un indirizzo. In particolare, questo indirizzo indica la posizione iniziale in cui è memorizzata una seconda struttura, il cui primo campo è il secondo elemento della sequenza, mentre il secondo campo è un puntatore al terzo elemento della sequenza. Si veda di seguito la rappresentazione grafica.

Per sequenze di quattro elementi possiamo usare la seguente diposizione.

Le figure di sopra danno una possibile rappresentazione in memoria di alcune liste. Per poter realizzare queste disposizioni in memoria, occorre dare delle definizioni di tipo. Diamo per esempio la definizione per la sequenza di quattro elementi:

struct Terza {
  int terzoelem;
  int *quartoelem;
};

struct Seconda {
  int secondoelem;
  struct Terza *terzoelem;
};

struct SeqQuattro {
  int primoelem;
  struct Seconda *secondoelem;
};

Quello che è importante capire è che

1. la definizione di tipo richiede una definizione per ogni elemento della sequenza;
2. le definizioni sono quasi tutte uguali: ogni struttura è composta da un intero e da un puntatore.

Consideriamo ora la seguente variante della rappresentazione di sopra: l'ultimo elemento della lista, invece di essere un intero, è una struttura composta da un intero e da un puntatore di valore NULL. Questa è una variante lecita:

Osserviamo ora che ogni struttura è composta da un intero e da un puntatore, e questo vale ora anche per l'ultima struttura, che differisce dalle altre solo per il fatto che il valore del puntatore è NULL. Quindi, ognuna delle strutture è composta da un intero e da un puntatore a qualcosa. In particolare, osserviamo che la zona di memoria che inizia dall'indirizzo scritto nel puntatore è ancora una struttura identica alla precedente. Possiamo quindi definire tutte le strutture nello stesso identico modo:

struct Sequenza {
  int valore;
  struct Sequenza *next;
};

In altre parole, sappiamo che tutte le strutture devono essere composte da un intero e da un puntatore, e questo giustifica il fatto che la definizione di tipo per la struttura è composta da due campi, il primo dei quali è un intero, e il secondo è un puntatore. Per capire di che tipo deve essere il puntatore, dobbiamo semplicemente vedere cosa contiene la zona di memoria che inizia dall'indirizzo che il puntatore contiene. In questo caso, la zona contiene ancora una struttura di tipo struct Sequenza, quindi dichiariamo che il puntatore è un puntatore a una struttura struct Sequenza.

Lista vuota

Questa definizione di tipo va bene per sequenze di un qualsiasi numero di elementi, ma c'è un caso su cui non funziona: la lista vuota. Infatti, una lista è una sequenza di interi, che può anche essere composta da nessun numero. Una sequenza che non contiene nessun elemento si denota con ( ). Un esempio del perchè questo caso è cosí importante: supponiamo di voler memorizzare dei numeri che vengono forniti dall'utente in una lista: all'inizio dell'esecuzione, quando l'utente non ha ancora inserito nessun numero, la lista deve risultare vuota.

Esiste un modo molto semplice per estendere la definizione di sopra in modo tale che comprende anche il caso di lista vuota: definiamo una lista non come una struttura a due campi, ma come un puntatore alla struttura. In altre parole, diamo un nome di comodo alla struttura, e poi definiamo la lista come un puntatore alla struttura:

struct NodoLista {
  int val;
  struct NodoLista *next;
};

typedef struct NodoLista *TipoLista;

Per prima cosa, verifichiamo facilmente che, in questo modo, possiamo rappresentare sia liste vuote che liste con elementi. Se dichiariamo l come una variabile di tipo TipoLista, allora questa variabile è di tipo puntatore, ossia contiene l'indirizzo di una zona di memoria che contiene una struttura. Rappresentiamo la lista vuota mettendo il valore NULL nella variabile l. Se la lista non è vuota, allora la rappresentiamo usando la sequenza di strutture collegate, la cui prima struttura è quella all'indirizzo contenuto in l.

Resterebbe ora da dire perchè usiamo questo particolare meccanismo, e non altri, per rappresentare la lista vuota. Il motivo è che, in questo modo, si ha una certa coerenza di rappresentazione. In particolare, la lista intera è rappresentata da l, mentre la lista composta da tutti gli elementi tranne il primo è (*l).next. Questa uniformità semplifica molto il lavoro di programmazione, e permette la creazione di funzioni ricorsive sulle liste.

Tutto questo discorso spiega la definizione di tipo della lista. È però anche possibile partire dalla definizione di tipo, e vedere a cosa corrisponde in memoria. Nella prossima pagina, facciamo finta di non sapere come si è arrivati a questa definizione di tipo, e facciamo vedere come sia possibile rappresentare liste di interi.

Riepilogo:

1. possiamo rappresentare liste usando strutture composte da due campi, uno dei queli è un puntatore a un'altra struttura dello stesso tipo;
2. usiamo una struttura anche per rappresentare l'ultimo elemento della sequenza, anche se questo non ha una struttura che segue (per cui il puntatore non sarebbe necessario): in questo modo, si riesce a dare una definizione di tipo abbastanza semplice;
3. per riuscire a rappresentare anche la lista vuota, usiamo un puntatore a struttura per rappresentare una lista (cioè non rappresentiamo una lista con una variabile struttura ma con una variabile puntatore a struttura).

Si vede chiaramente che questo meccanismo di rappresentazione soddisfa la regola che la lista deve essere rappresentata da un'unica variabile. Infatti, se passiamo il valore di l (il puntatore alla prima struttura) a una funzione, questa è per esempio in grado di capire quali sono tutti gli elementi della lista. Vedremo più avanti una funzione che stampa una lista a partire dal solo puntatore iniziale.