Puntatori, struct e memoria dinamica in C

In questa pagina 7

In C non esistono classi né interfacce (vedi Liste, pile e code): un ADT si realizza con struct e funzioni, e la memoria si gestisce a mano. L'esame ha una parte di programmazione in C su liste, alberi e heap (vedi Liste concatenate in C e Alberi e heap in C). Questa nota riprende e approfondisce quanto visto in Fondamenti di Informatica: Puntatori in C, Strutture (struct) in C, Array e stringhe in C, Funzioni in C e Gestione della memoria in C; per chi viene da Python il confronto è in Dal Python al C.

Puntatori

Definizione (puntatore). Un puntatore è una variabile che contiene un indirizzo di memoria. &x è l'indirizzo di x, *p è il valore puntato da p (dereferenziazione), NULL è il puntatore che non punta a nulla.

Un indirizzo è il numero d'ordine di una cella della memoria dell'elaboratore (la memoria è una sequenza di byte numerati: vedi Struttura di un elaboratore). Un puntatore è quindi un intero che si interpreta come "posizione in memoria"; il tipo int * ricorda al compilatore che in quella posizione si trova un int.

Esempio. Con int x = 5; int *p = &x; *p = 7; si ottiene x == 7. Passo per passo, supponendo che x sia all'indirizzo $1000$ (valore indicativo):

istruzione	`x`	`p`	commento
`int x = 5;`	5	(non definito)	la cella $1000$ contiene $5$
`int *p = &x;`	5	1000	`&x` è l'indirizzo $1000$ , `p` lo memorizza
`*p = 7;`	7	1000	si scrive $7$ nella cella a cui `p` punta, cioè in `x`

Proprietà (passaggio dei parametri per valore). C passa i parametri per valore: la funzione riceve una copia. Per modificare una variabile del chiamante si passa il suo indirizzo.

Esempio. Con void incrementa(int *p) { (*p)++; } e int n = 5; incrementa(&n); si ha n == 6.

void scambia(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}
/* int x = 3, y = 7; scambia(&x, &y);  ->  x = 7, y = 3 */

Traccia di scambia(&x, &y): a contiene l'indirizzo di x, b quello di y. Si salva il valore di x in una variabile temporanea (t = *a dà $t=3$ ), si copia il valore di y in x (*a = *b dà $x=7$ ) e si scrive il vecchio valore di x in y (*b = t dà $y=3$ ). La variabile t serve: senza di essa *a = *b cancellerebbe il $3$ prima di averlo salvato. Se scambia ricevesse int a, int b per valore, scambierebbe due copie e x, y resterebbero $3$ e $7$ .

Una funzione che deve restituire più valori ne restituisce uno e scrive gli altri tramite puntatori:

int massimo(const int v[], int n, int *pos) {   /* const: la funzione non modifica v */
    int m = v[0];
    *pos = 0;
    for (int i = 1; i < n; i++)
        if (v[i] > m) { m = v[i]; *pos = i; }
    return m;
}

Array, aritmetica dei puntatori e stringhe

Proprietà (array e aritmetica dei puntatori). Un array è un blocco contiguo; il suo nome si comporta come puntatore al primo elemento, quindi v[i] equivale a *(v + i) (la somma avanza di i elementi, non di i byte). Un array passato a una funzione arriva come puntatore: la lunghezza non si conserva e va passata a parte (int n). Nessun controllo sui limiti: v[n] è un errore silenzioso.

Esempio. Con int v[3] = {10, 20, 30}; si ha *(v + 2) == v[2] == 30. Se v fosse all'indirizzo $1000$ e sizeof(int) fosse $4$ , gli elementi occuperebbero i byte $1000$ – $1003$ , $1004$ – $1007$ , $1008$ – $1011$ e v + 2 varrebbe $1000 + 2 \cdot 4 = 1008$ : il compilatore moltiplica i per la dimensione del tipo puntato. Per questo v[i] costa $\Theta(1)$ (un'addizione e una lettura), la stessa assunzione del modello RAM. Altri dettagli sugli array sono in Array e stringhe in C.

Definizione (stringa in C). Una stringa è un array di char terminato da '\0': char nome[64] contiene al più 63 caratteri più il terminatore. Si copia con strcpy, si confronta con strcmp, mai con = o ==.

Esempio. strlen("ciao") vale 4, ma la stringa occupa sizeof("ciao") == 5 byte per il terminatore '\0': in memoria ci sono i cinque char 'c', 'i', 'a', 'o', '\0'. I caratteri sono memorizzati come interi piccoli secondo una codifica (vedi Codifiche binarie e informazione non numerica) e '\0' è il valore $0$ . strlen conta i caratteri fino al primo '\0', quindi costa $\Theta(\text{lunghezza})$ e non $\Theta(1)$ . == tra due stringhe confronterebbe i due indirizzi, non il contenuto.

Struct e typedef

typedef struct {
    char nome[64];
    int voto;
} Studente;

Studente s;
strcpy(s.nome, "Anna");
s.voto = 28;
Studente *ps = &s;
ps->voto++;            /* equivale a (*ps).voto++ */

Definizione (operatori . e ->). . si usa su una struct, -> su un puntatore a struct. Una struct che contiene un puntatore a se stessa permette le strutture collegate:
typedef struct nodo {
    int val;
    struct nodo *next;   /* dentro la definizione serve il nome "struct nodo" */
} Nodo;

Esempio. Con Studente s; s.voto = 28; Studente *ps = &s; ps->voto++; si ottiene s.voto == 29.

Memoria dinamica

Definizione (memoria dinamica con malloc e free). Le variabili locali vivono nello stack e spariscono quando la funzione termina; malloc alloca nello heap un blocco che dura finché non lo si libera con free.

Esempio. int *a = malloc(4 * sizeof(int)); riserva 16 byte nello heap; dopo a[i] = i * i si ha a[3] == 9, e free(a); li libera.

int n = 4;
int *a = malloc(n * sizeof(int));     /* n interi; restituisce NULL se fallisce */
if (a == NULL) return 1;
for (int i = 0; i < n; i++) a[i] = i * i;
free(a);                              /* ogni malloc ha il suo free */
a = NULL;                             /* per non lasciare un puntatore pendente */

Su questa macchina sizeof(int) vale $4$ e sizeof(Studente) $68$ ( $64$ byte per nome più $4$ per voto): usare sempre sizeof invece di numeri fissi. Il compilatore può aggiungere byte di riempimento (padding) per allineare i campi agli indirizzi multipli della loro dimensione; qui non servono perché $64$ è già multiplo di $4$ , ma in generale sizeof di una struct può superare la somma dei campi.

La differenza tra stack e heap è la durata: una variabile locale nasce quando la funzione viene chiamata e muore al return (il suo record di attivazione viene tolto dallo stack, come in Algoritmi ricorsivi e Stack e chiamata di funzioni in ARM); un blocco di malloc resta valido finché non lo si libera. Per questo una funzione può restituire l'indirizzo di un blocco allocato con malloc ma non l'indirizzo di una sua variabile locale. Il funzionamento è approfondito in Gestione della memoria in C.

Puntatore a puntatore

Proprietà (puntatore a puntatore). Un puntatore passato per valore è una copia: assegnarlo dentro la funzione non cambia quello del chiamante. Per modificarlo (tipicamente la testa di una lista o la radice di un albero) si passa il suo indirizzo, cioè un Nodo **.

Esempio. Con void azzeraGiusto(int **p) { *p = NULL; }, la chiamata azzeraGiusto(&a) lascia a == NULL.

void azzeraSbagliato(int *p)  { p = NULL; }    /* a resta com'era */
void azzeraGiusto(int **p)    { *p = NULL; }   /* chiamata: azzeraGiusto(&a) */

Il test ha mostrato: dopo azzeraSbagliato(a), a != NULL; dopo azzeraGiusto(&a), a == NULL.

Perché. In azzeraSbagliato(a) il parametro p è una copia dell'indirizzo contenuto in a: la funzione assegna NULL alla copia e al return la copia sparisce, mentre a nel chiamante non è stata toccata. In azzeraGiusto(&a) il parametro p contiene l'indirizzo della variabile a stessa (un puntatore a puntatore, tipo int **); *p = NULL scrive NULL proprio in a. È la stessa regola di scambia: per cambiare una variabile se ne passa l'indirizzo; qui la variabile è a sua volta un puntatore, quindi serve un livello di * in più.

Compilare

gcc -std=c99 -Wall -Wextra -o programma programma.c (e -lm per la libreria matematica). Un Makefile automatizza il comando; man funzione mostra la documentazione, ammessa all'esame. Gli avvisi vanno letti: -Wall segnala variabili non inizializzate e formati di printf sbagliati. Le fasi dalla sorgente all'eseguibile (preprocessore, compilazione, assemblaggio, collegamento) sono in Dal programma C all'eseguibile ARM; per cercare gli errori sono utili le tecniche di Debugging e testing.

Errori comuni

Dereferenziare NULL o un puntatore non inizializzato (crash).
Puntatore pendente: usare un blocco dopo free, o restituire l'indirizzo di una variabile locale.
Perdita di memoria: perdere l'unico puntatore a un blocco allocato (p = NULL senza free) o dimenticare il free.
Passare Nodo * dove serve Nodo ** e vedere la testa invariata.
Errori di uno sugli array (i <= n invece di i < n) e stringhe senza spazio per '\0'.
Confrontare stringhe con ==.

Versione ripasso

Puntatore: contiene un indirizzo. &x è l'indirizzo, *p il valore puntato, NULL non punta a nulla. Esempio: int x = 5; int *p = &x; *p = 7; lascia x == 7.
Passaggio per valore: C copia i parametri. Per modificare una variabile del chiamante si passa &x: scambia(int *a, int *b) usa una variabile temporanea, t = *a; *a = *b; *b = t;. Con int per valore, x e y resterebbero invariati. Più risultati: uno col return, gli altri via puntatore (esempio massimo(v, n, &pos)).
Array: v[i] equivale a *(v+i), con avanzamento di i elementi (non di i byte). Negli argomenti l'array arriva come puntatore: la lunghezza va passata a parte. Nessun controllo sui limiti: v[n] è un errore silenzioso. Con int v[3]={10,20,30} si ha *(v+2) == 30.
Stringa: array di char terminato da '\0'; strlen("ciao") vale $4$ , mentre sizeof("ciao") è $5$ . Si confronta con strcmp, mai con == (che confronta indirizzi). strlen costa $\Theta(\text{lunghezza})$ .
Struct: typedef struct {...} T;, . su una struct, -> su un puntatore a struct: ps->voto++. Struct autoreferenziale: struct nodo *next (vedi Liste concatenate in C).
Memoria dinamica: malloc(n * sizeof(int)) restituisce NULL se fallisce, quindi va controllato; ogni malloc ha un free, seguito da a = NULL per non lasciare un puntatore pendente. Stack = variabili locali, che muoiono al return; heap = blocchi di malloc, validi finché non si libera. Una funzione non deve restituire l'indirizzo di una variabile locale.
Puntatore a puntatore: un puntatore passato per valore è una copia. azzeraSbagliato(int *p) { p = NULL; } non cambia a; azzeraGiusto(int **p) { *p = NULL; }, chiamato come azzeraGiusto(&a), lo azzera. Per la testa di una lista si usa Nodo **.
Dimensioni: su questa macchina sizeof(int) vale $4$ e sizeof(Studente) vale $68$ ( $64$ per nome più $4$ per voto); conviene usare sempre sizeof, perché il compilatore può aggiungere padding.
Compilare: gcc -std=c99 -Wall -Wextra -o programma programma.c, con -lm per la matematica; man è ammesso all'esame.
Errori tipici: dereferenziare NULL o un puntatore non inizializzato; usare memoria dopo free; perdere l'unico puntatore a un blocco (perdita di memoria); Nodo * invece di Nodo **; i <= n invece di i < n; == sulle stringhe.