9 Livello 7

9.1 I puntatori

In C, i puntatori sono onnipresenti e vengono impiegati in quasi ogni ambito della programmazione.

Definizione: Un puntatore è una variabile destinata a memorizzare l’indirizzo di memoria (la coordinata fisica nella RAM) di un’altra variabile.

Come verrà analizzato dettagliatamente, i puntatori sono indispensabili per manipolare gli array, modificare il contenuto delle variabili passate alle funzioni, gestire i file, governare l’allocazione dinamica della memoria e strutturare collezioni di dati complesse come le liste concatenate.

La sintassi per la dichiarazione di un puntatore richiede l’uso dell’operatore * anteposto al nome della variabile:

int *mio_puntatore;

La dichiarazione definisce l’identificatore del puntatore e, mediante il tipo specificato (in questo caso int), stabilisce il tipo di dato della variabile puntata. È possibile dichiarare puntatori a qualunque tipo di dato.

Si analizzi un primo esempio essenziale per comprendere il funzionamento di base dei puntatori:

#include <stdio.h>
int main(void) {
    int n = 10;
    int *p;
    p = &n; // Inizializzazione: p memorizza l'indirizzo di n
    printf("%d %d\n", n, *p);    
    return 0;
}

In questo frammento, alla dichiarazione int *p; segue l’inizializzazione p = &n;. Quest’ultima istruzione mappa il puntatore p sulla variabile n, trasferendo l’indirizzo di quest’ultima all’interno del puntatore. Da questo momento, p contiene l’indirizzo in RAM di n, e diventa possibile modificare il valore di n per via indiretta tramite l’espressione *p (operatore di dereferenziazione).

9.1.1 Accesso alle strutture tramite puntatori

I puntatori possono indirizzare variabili composte come le struct. Per accedere ai campi di una struttura attraverso un puntatore dedicato, il C introduce l’operatore freccia (->), che sostituisce la combinazione dell’operatore di dereferenziazione e dell’operatore punto ((*p).campo).

#include <stdio.h>
#define DIM_NOME 20
struct studente {
    int matricola;
    char nome[DIM_NOME];
    char cognome[DIM_NOME];
};
int main(void) {
    struct studente stud;
    struct studente *mio_p;
    mio_p = &stud; // Il puntatore referenzia la struttura    
    printf("\nNome: ");
    fgets(mio_p->nome, DIM_NOME, stdin);    
    printf("\nCognome: ");
    fgets(mio_p->cognome, DIM_NOME, stdin);    
    printf("\nMatricola: ");
    scanf("%d", &mio_p->matricola);
    printf("\n\nDati studente: ");
    printf("%s %s, Matricola: %d\n", stud.nome, 
      stud.cognome, stud.matricola);    
    return 0;
}

L’istruzione mio_p = &stud; vincola formalmente il puntatore all’istanza della struttura. Di conseguenza, le funzioni di input agiscono direttamente sui membri della struct originaria operando per via indiretta tramite il puntatore.

9.1.2 Il ruolo dei puntatori nelle liste concatenate

Come vedremo più avanti, i puntatori costituiscono il componente fondamentale per l’implementazione delle liste concatenate (linked lists). Anche nella loro forma più elementare, ovvero in regime di allocazione statica della memoria, le liste sono strutturate attraverso i puntatori. Sussistono tre ragioni fondamentali che rendono l’uso dei puntatori vincolante nelle liste:

A differenza degli array, gli elementi (nodi) di una lista concatenata non sono necessariamente allocati in blocchi di memoria fisicamente adiacenti. L’unico meccanismo per determinare la posizione del nodo successivo resta quello di memorizzarne l’indirizzo all’interno del nodo precedente. Ogni nodo deve pertanto integrare un campo puntatore.
La lista è identificata dal puntatore che indirizza il suo primo elemento (la “testa” della lista). Lo smarrimento di questo puntatore comporta l’impossibilità di scorrere la lista. Nell’esempio che segue i nodi sono variabili locali dotate di un proprio nome e restano comunque raggiungibili, quando però i nodi verranno allocati dinamicamente (come accade nelle liste reali), la perdita della testa renderà la loro memoria irraggiungibile e non più rilasciabile (memory leak, ci torneremo nel capitolo sugli oggetti dinamici).
La scansione della lista richiede l’individuazione del nodo terminale. È obbligatorio imporre che il campo puntatore dell’ultimo nodo sia impostato sulla costante NULL, un valore convenzionale che attesta la fine della lista.

Si consideri un esempio di lista concatenata statica, in cui tutti i nodi sono preventivamente allocati sullo stack:

#include <stdio.h>
struct lista {
    int num;
    struct lista *next; // Puntatore al nodo successivo
};
int main(void) {
    struct lista val1, val2, val3;
    struct lista *punt_list;
    // Configurazione dei dati e concatenazione dei nodi
    val1.num = 10;
    val1.next = &val2;    
    val2.num = 20;
    val2.next = &val3;    
    val3.num = 30;
    val3.next = NULL; // Nodo terminale    
    punt_list = &val1; // Il puntatore individua l'inizio della lista    
    // Ciclo di scansione sequenziale
    while(punt_list != NULL) {
        printf("%d ", punt_list->num);
        punt_list = punt_list->next; // Traslazione al nodo successivo
    }
    printf("\n");    
    return 0;
}

Le liste concatenate offrono un’elevata flessibilità. Le operazioni di inserimento o rimozione di un nodo intermedio non richiedono lo spostamento fisico dei dati in memoria, ma si risolvono mediante il semplice aggiornamento dei puntatori dei nodi coinvolti. Negli array questa medesima operazione presenta una complessità superiore, poiché richiede lo shift (scorrimento) di tutti gli elementi successivi alla posizione d’esame per preservare la contiguità degli elementi.

Una precisazione terminologica

In questo esempio i nodi sono dichiarati come variabili locali e risiedono quindi sullo stack. Nel gergo comune si parla spesso di “allocazione statica” per indicare tutto ciò che non viene allocato dinamicamente, ma è bene sapere che lo standard C distingue tre tipologie di memorizzazione: automatica (le variabili locali, sullo stack), statica in senso proprio (le variabili globali e quelle dichiarate con la parola chiave static) e dinamica (la memoria richiesta a runtime con malloc, che vedremo nel capitolo sugli oggetti dinamici).

9.1.3 Relazione tra array e puntatori

Esiste una stretta relazione tra array e puntatori. È possibile associare un puntatore esterno ad un array e scorrere gli elementi dell’array applicando le regole dell’aritmetica dei puntatori.

Data la seguente dichiarazione:

int v[N];
int *v_ptr;

v_ptr = &v[0]; // Il puntatore indirizza l'elemento iniziale

Il puntatore v_ptr memorizza l’indirizzo del primo elemento dell’array v, consentendo di interagire con l’intera struttura lineare.

#include <stdio.h>
int main(void) {
    int i, v[3] = {1, 2, 3};
    int *v_ptr;
    for(i = 0; i < 3; i++) printf("%d ", v[i]); // Output: 1 2 3
    printf("\n");
    v_ptr = v; // Equivalente a: v_ptr = &v[0];    
    *(v_ptr + 1) = 10; // Modifica del secondo elemento
    for(i = 0; i < 3; i++) printf("%d ", v[i]); // Output: 1 10 3
    printf("\n");    
    return 0;
}

In Figura 9.1, vediamo l’organizzazione dell’array v e del puntatore v_ptr (successivamente all’istruzione v_ptr = v;) in memoria RAM.

Figura 9.1: Schema dell’organizzazione in RAM di un array. L’array `v` occupa 12 byte, in quanto è costituito da tre interi da 4 byte l’uno. Gli elementi dell’array sono adiacenti in RAM. Si noti che la differenza tra gli indirizzi di ogni elemento è pari a 4 byte (nella figura gli indirizzi sono espressi in esadecimale). A seguito dell’istruzione `v_ptr = v;`, il puntatore `v_ptr` contiene al suo interno l’indirizzo del primo elemento dell’array `v`. Tramite l’aritmetica dei puntatori è possibile accedere all’array `v` tramite il puntatore `v_ptr`.

L’espressione *(v_ptr + 1) = 10; dimostra come modificare il contenuto del secondo elemento dell’array. La notazione v_ptr + 1 non incrementa l’indirizzo di un singolo byte, lo spostamento (offset) viene automaticamente scalato sulla dimensione del tipo puntato. Se l’array memorizza interi, lo scostamento fisico sarà tipicamente di 4 byte, se l’array fosse composto da caratteri (char), lo scostamento sarebbe di 1 byte. In generale, l’espressione v_ptr + i corrisponde all’indirizzo base aumentato di \(i \times \texttt{sizeof(tipo)}\) byte. L’operatore * garantisce poi l’accesso diretto al valore memorizzato a quell’indirizzo.

In virtù di queste proprietà, all’interno del codice le notazioni vettoriali e le espressioni basate sui puntatori risultano del tutto equivalenti dal punto di vista computazionale:

\[v[i] \iff *(v\_ptr + i)\]

Infine, è possibile impiegare gli operatori di incremento e decremento (v_ptr++, v_ptr--) per spostare dinamicamente il puntatore tra gli elementi dell’array. Si raccomanda di considerare che tali operazioni modificano il valore memorizzato nella variabile puntatore stessa e quindi al termine delle elaborazioni, v_ptr non farà più riferimento all’elemento iniziale dell’array, a meno di non procedere a un esplicito riallineamento (v_ptr = v;).

Il decadimento

Come già visto nel capitolo sugli array, in quasi tutti i contesti il nome di un array decade automaticamente nell’indirizzo del suo primo elemento (\(v = \&v[0]\)), per questo v_ptr = v è del tutto equivalente a v_ptr = &v[0], e quando si passa un array a una funzione la funzione riceve un indirizzo, non una copia dell’array. Il nome dell’array non è però riassegnabile né incrementabile, operazioni come v = v + 1 o v++ non sono ammesse dal compilatore.

Il decadimento non si verifica soltanto in pochissimi contesti eccezionali: sizeof(v), che restituisce la dimensione dell’intero array e non quella di un puntatore e &v produce un puntatore di tipo int (*)[N]. Al di fuori di queste eccezioni, il nome dell’array e un puntatore al suo primo elemento si comportano in modo equivalente nelle espressioni.