Puntatori, struct e memoria dinamica in C

In C non esistono classi né interfacce (vedi Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.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 CLista singolarmente concatenata in C con nodo struct e testa passata per riferimento (Nodo **); addHead, addTail ricorsiva e iterativa, pop, inversione in loco, liberazione; coda con puntatori a testa e coda; ricorsione sulle liste; costi.Liste concatenate in C → e Alberi e heap in CAlbero binario in C con nodo struct e figli left/right; funzioni ricorsive (conteggio, altezza, visita inorder, liberazione in postorder); inserimento in un albero binario di ricerca con Nodo **; min-heap su array con indici da 1 (insert, removeMin, bottomUp).Alberi e heap in C →).

Puntatori

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.

C passa i parametri per valore: la funzione riceve una copia. Per modificare una variabile del chiamante si passa il suo indirizzo.

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 */

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

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.

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 ==.

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++ */

. 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;

Memoria dinamica

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.

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 + 4): usare sempre sizeof invece di numeri fissi.

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 **.

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.

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.

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 ==.