Lezione 14: La Fuga dallo Stack (Memoria Dinamica e la nascita del Nodo)

Slide e Risorse della Lezione

• 📄 Scarica le Slide (PDF)
• 📘 Scarica la Dispensa della Lezione (PDF)

Nelle lezioni precedenti abbiamo visto come aggregare dati eterogenei usando le struct e come gestirli in blocchi fissi. Tuttavia, siamo sempre rimasti vincolati alla memoria automatica dello Stack, in cui le variabili nascono e muoiono rigidamente entro lo scope della funzione corrente.

In questa lezione compiremo un salto fondamentale: impareremo ad evadere dallo Stack allocando manualmente la memoria in un’area persistente controllata direttamente dal programmatore, lo Heap. Utilizzeremo le funzioni standard malloc, calloc e free per richiedere e rilasciare RAM, analizzeremo il funzionamento e i costi della riallocazione (realloc), e infine getteremo le basi per le strutture dati dinamiche definendo il Nodo autoreferenziale, l’unità fondamentale che ci consentirà di slegare i dati dalla contiguità fisica degli array.

---

1. Il Muro dello Stack e l’Ingresso nello Heap

1.1 Il problema irrisolvibile: Variabili Locali e Dangling Pointer

Si consideri il tentativo di scrivere una funzione che generi un array contenente i primi $n$ numeri della successione di Fibonacci e lo restituisca al chiamante:

int* genera_fibonacci_sbagliato(int n) {
    // Array locale nello Stack (Variable Length Array - VLA)
    int seq[n];

    seq[0] = 0;
    if (n > 1) seq[1] = 1;

    for (int i = 2; i < n; i++) {
        seq[i] = seq[i-1] + seq[i-2];
    }

    return seq; // Ritorno dell'indirizzo del primo elemento
}

Compilando questo codice, il compilatore emette un avviso critico: warning: function returns address of local variable [-Wreturn-local-addr]

All’esecuzione, il programma subirà un crash immediato (Segmentation fault) o produrrà valori spazzatura.

La ragione fisica: L’array seq risiede nello Stack Frame di genera_fibonacci_sbagliato. Al termine dell’esecuzione della funzione (return), il suo intero frame viene rimosso dallo Stack e invalidato dal sistema operativo. L’indirizzo restituito punta ad un’area non più riservata (un Dangling Pointer), pronta ad essere sovrascritta da altre chiamate a funzione.

Tutte le variabili create nello Stack nascono e muoiono con lo scope della funzione in cui sono dichiarate. Non è possibile restituire puntatori a variabili locali o array locali dallo stack.

1.2 La Fuga: La Memoria HEAP

Per superare la logica LIFO (Last-In, First-Out) dello Stack, i sistemi operativi offrono l’area di memoria Heap (Mucchio):

• Ampiezza: È limitata solo dalla RAM fisica complessiva del sistema.
• Persistenza: La memoria allocata nello Heap sopravvive alla chiusura delle funzioni e rimane attiva fino a quando il programmatore non ne richiede esplicitamente la distruzione, o fino al termine dell’intero processo.
• Manuale: La gestione è interamente affidata allo sviluppatore.

1.3 Le Chiavi dello Heap: malloc e free

La libreria standard <stdlib.h> fornisce gli strumenti per dialogare con lo Heap.

Allocazione con malloc

La funzione malloc (Memory Allocation) richiede al sistema operativo un blocco continuo di byte:

void* malloc(size_t size);

• Riceve come parametro il numero esatto di byte da allocare.
• Restituisce un puntatore a tipo generico (void*) che punta all’inizio del blocco allocato nello Heap.
• Se l’allocazione fallisce (ad es. per mancanza di RAM), restituisce NULL.

Riscriviamo la generazione di Fibonacci in sicurezza:

#include <stdlib.h>
#include <stdio.h>

int* genera_fibonacci(int n) {
    // Chiediamo spazio nell'Heap per n interi
    int *seq = (int*) malloc(n * sizeof(int));

    if (seq == NULL) {
        fprintf(stderr, "Errore: Memoria insufficiente!\n");
        return NULL;
    }

    seq[0] = 0;
    if (n > 1) seq[1] = 1;

    for (int i = 2; i < n; i++) {
        seq[i] = seq[i-1] + seq[i-2];
    }

    return seq; // Perfettamente sicuro: l'Heap non collassa al return!
}

L’immagine che segue mostra come si può usare lo heap per costruire un nuovo array dentro una funzione e restituire un puntatore al chiamante:

Rilascio della memoria con free

Poiché la memoria Heap non viene pulita automaticamente, dimenticare di liberarla genera un Memory Leak (perdita di memoria). La memoria occupata rimane bloccata e indisponibile. Per liberare un blocco di memoria si usa free:

void free(void* ptr);

Dopo aver liberato un puntatore, è ottima norma impostarlo a NULL per evitare di riutilizzarlo accidentalmente (Dangling Pointer).

int main(void) {
    int n = 8;
    int *fib = genera_fibonacci(n);

    if (fib != NULL) {
        for (int i = 0; i < n; i++) {
            printf("%d ", fib[i]);
        }
        printf("\n");

        free(fib);   // Riconsegniamo i byte allo Heap
        fib = NULL;  // Annulliamo il puntatore per sicurezza
    }
    return 0;
}

L’immagine che segue mostra un esempio di memory leak:

---

2. Array Dinamici e Ridimensionamento

2.1 Sintassi di Accesso negli Array Dinamici

Una volta allocato un array dinamico e assegnato l’indirizzo a un puntatore, l’accesso avviene con la medesima sintassi degli array statici:

int *arr = (int*) malloc(5 * sizeof(int));
arr[0] = 10;
*(arr + 1) = 20; // Equivalente a arr[1] = 20;

L’operatore parentesi quadre [] compie implicitamente l’aritmetica dei puntatori ed esegue la dereferenziazione.

2.2 calloc: Allocazione con Inizializzazione a Zero

A differenza di malloc, che lascia intatto il contenuto preesistente della memoria (spazzatura), la funzione calloc pulisce a zero tutti i bit allocati:

void* calloc(size_t nmemb, size_t size);

// Alloca 10 interi e li inizializza tutti a 0
int *vettore = (int*) calloc(10, sizeof(int));

Il diagramma seguente mostra le differenze fisiche nell’inizializzazione della memoria tra malloc e calloc:

2.3 Ridimensionare la memoria: realloc

Se la dimensione originaria di un array dinamico si rivela insufficiente, possiamo modificarne l’estensione tramite realloc:

void* realloc(void* ptr, size_t size);

Meccanismo di funzionamento:

1. Espansione in situ: Se lo spazio contiguo immediatamente successivo nello Heap è libero, la realloc estende semplicemente il blocco originale senza spostarlo.
2. Trasloco: Se lo spazio adiacente è occupato, la realloc cerca una nuova area capiente altrove nello Heap, copia l’intero contenuto, dealloca il vecchio spazio in automatico e restituisce il nuovo indirizzo.
3. Fallimento: Se non c’è RAM sufficiente, restituisce NULL lasciando il puntatore originario valido e intatto.

Nota

Per evitare perdite di memoria in caso di fallimento della realloc, non bisogna mai sovrascrivere direttamente il puntatore originale con il risultato della funzione senza prima controllare se è valido (NULL).

// Corretto schema d'uso di realloc
int *nuovo = (int*) realloc(fib, (n + 1) * sizeof(int));
if (nuovo != NULL) {
    fib = nuovo;
} else {
    // Gestione errore: fib contiene ancora i dati precedenti!
}

Il diagramma seguente illustra i tre diversi scenari che si possono verificare durante una chiamata a realloc:

---

3. Verso le Strutture Dinamiche: Il Nodo

3.1 Superare il vincolo della contiguità

Gli array in C devono essere allineati in celle di memoria contigue. Ciò rende costoso l’inserimento o la riallocazione in mezzo ai dati. L’alternativa consiste nel disporre i dati sparsi in zone distinte dello Heap, legandoli tra loro tramite puntatori, in una caccia al tesoro logica.

3.2 Il Nodo Autoreferenziale

L’elemento base di questa catena è la struct autoreferenziale, detta Nodo:

typedef struct Nodo {
    int dato;               // Il valore utile (Payload)
    struct Nodo *prossimo;  // Il puntatore al prossimo nodo
} Nodo;

Dentro la definizione della struct non è possibile usare l’alias Nodo in quanto non è ancora stato registrato dal compilatore. Bisogna usare obbligatoriamente la nomenclatura formale completa struct Nodo *prossimo.

3.3 Collegamento manuale di nodi

Il seguente codice mostra come allocare e collegare manualmente tre nodi nello Heap:

#include <stdio.h>
#include <stdlib.h>

typedef struct Nodo {
    int dato;
    struct Nodo *prossimo;
} Nodo;

int main(void) {
    // 1. Allocazione dei nodi sparsi nello Heap
    Nodo *testa = (Nodo*) malloc(sizeof(Nodo));
    Nodo *secondo = (Nodo*) malloc(sizeof(Nodo));
    Nodo *terzo = (Nodo*) malloc(sizeof(Nodo));

    // 2. Assegnamento dei dati
    testa->dato = 10;
    secondo->dato = 20;
    terzo->dato = 30;

    // 3. Collegamento
    testa->prossimo = secondo;
    secondo->prossimo = terzo;
    terzo->prossimo = NULL; // Fine della catena

    // Navigazione
    printf("Secondo dato: %d\n", testa->prossimo->dato); // 20

    // Liberazione manuale
    free(testa);
    free(secondo);
    free(terzo);

    return 0;
}

Il diagramma seguente illustra la disposizione in memoria dei nodi nello Heap e il relativo collegamento tramite puntatori:

---

4. Autovalutazione ed Esercizi

4.1 Test a Risposta Multipla (10 Quiz)

1. Cosa succede se una funzione restituisce l’indirizzo di una variabile locale allocata nello Stack?

   • a) La variabile viene promossa automaticamente nello Heap.
   • b) Si ottiene un dangling pointer che punta a una zona di memoria invalidata dal return.
   • c) Il compilatore rifiuta di compilare bloccando l’esecuzione con errore bloccante.
   • d) La variabile sopravvive fino al termine del main.
   Risposta corretta

   Risposta: b. Le variabili locali nello Stack cessano di esistere al return; il puntatore diventa dangling.

2. Quale delle seguenti affermazioni descrive correttamente la memoria Heap?

   • a) È ordinata secondo la logica LIFO.
   • b) Viene gestita automaticamente dal compilatore senza intervento umano.
   • c) Consente allocazioni persistenti a vita manuale, fino alla chiamata di free.
   • d) Ha dimensioni inferiori a quelle dello Stack di sistema.
   Risposta corretta

   Risposta: c. Lo Heap è governato interamente in modo manuale dal programmatore.

3. Cosa restituisce malloc in caso di fallimento dell’allocazione?

   • a) Un puntatore a 0x0001.
   • b) Un valore casuale.
   • c) NULL.
   • d) Genera un’eccezione di runtime interrompendo il programma.
   Risposta corretta

   Risposta: c. Restituisce NULL, motivo per cui va sempre controllata.

4. Qual è la principale differenza tra malloc e calloc?

   • a) calloc alloca solo memoria nello Stack.
   • b) calloc alloca la memoria e azzera il valore di tutti i bit.
   • c) malloc accetta due parametri anziché uno.
   • d) calloc non può fallire.
   Risposta corretta

   Risposta: b. calloc inizializza a zero, malloc lascia spazzatura.

5. Cosa si intende per “Memory Leak”?

   • a) La perdita fisica del computer contenente i file sorgente.
   • b) Una fuga di dati sensibili a causa di un puntatore non protetto.
   • c) Memoria Heap allocata che non viene liberata con free, rimanendo inutilizzabile.
   • d) Il collasso dello Stack Frame per ricorsione infinita.
   Risposta corretta

   Risposta: c. È l’accumulo di memoria allocata e mai rilasciata.

6. Come si comporta realloc se non trova spazio adiacente per allargare il blocco?

   • a) Restituisce NULL e distrugge i vecchi dati.
   • b) Sposta l’intero blocco in una nuova posizione nello Heap e copia i dati.
   • c) Converte l’array in una lista concatenata in modo trasparente.
   • d) Sospende l’esecuzione del programma fino a quando non si libera spazio.
   Risposta corretta

   Risposta: b. Esegue un “trasloco” dei dati in una nuova area Heap.

7. Perché nello schema realloc non si deve riassegnare direttamente il puntatore originale?

   • a) Perché l’assegnamento diretto causerebbe un errore sintattico.
   • b) Perché se la realloc fallisce e restituisce NULL, perderemmo l’indirizzo originale creando un memory leak.
   • c) Perché il puntatore originale verrebbe invalidato in automatico dal compilatore.
   • d) Perché la realloc richiede un cast esplicito a void**.
   Risposta corretta

   Risposta: b. Sovrascrivere con NULL rende inaccessibile il vecchio blocco.

8. Qual è la sintassi corretta per un puntatore autoreferenziale in una struct chiamata Nodo?

   • a) Nodo *prossimo; all’interno della struct senza alias definito.
   • b) struct Nodo *prossimo;
   • c) void *prossimo; castato sempre a struct Nodo.
   • d) struct prossimo *Nodo;
   Risposta corretta

   Risposta: b. Poiché l’alias Nodo non è ancora registrato, è necessario usare struct Nodo *.

9. Che valore si assegna tipicamente al campo prossimo dell’ultimo nodo di una lista?

   • a) 0x0001.
   • b) EOF.
   • c) NULL.
   • d) L’indirizzo del nodo di testa (sempre).
   Risposta corretta

   Risposta: c. NULL funge da terminatore.

10. A quale delle seguenti operazioni equivale sintatticamente *(ptr + i)?

    • a) ptr->i
    • b) ptr[i]
    • c) &ptr[i]
    • d) ptr.i

Risposta corretta

Risposta: b. L’accesso con parentesi quadre è pura aritmetica e dereferenziazione di puntatori.

---

4.2 Esercizi di Programmazione Progressivi

Esercizio 1: Allocazione di un Intero Singolo

Scrivere un programma che allochi dinamicamente memoria per un singolo intero nello Heap, vi assegni il valore 42, lo stampi, liberi la memoria e azzeri il puntatore.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int *p = (int*) malloc(sizeof(int));
    if (p == NULL) {
        return 1;
    }
    *p = 42;
    printf("Valore nello Heap: %d\n", *p);
    free(p);
    p = NULL;
    return 0;
}

Esercizio 2: Vettore Dinamico Semplice

Scrivere una funzione double* crea_vettore(int n) che allochi un array di n double tramite calloc, inserisca in ciascuna cella il proprio indice e restituisca il puntatore. Testare la funzione nel main e liberare la memoria.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>

double* crea_vettore(int n) {
    double *arr = (double*) calloc(n, sizeof(double));
    if (arr == NULL) return NULL;
    for (int i = 0; i < n; i++) {
        arr[i] = (double) i;
    }
    return arr;
}

int main(void) {
    int n = 5;
    double *v = crea_vettore(n);
    if (v != NULL) {
        for (int i = 0; i < n; i++) {
            printf("%.1f ", v[i]);
        }
        printf("\n");
        free(v);
        v = NULL;
    }
    return 0;
}

Esercizio 3: Stringa Dinamica da Input

Scrivere un programma che legga da tastiera un intero lunghezza e allochi dinamicamente una stringa (char*) della dimensione esatta (incluso il terminatore \0). Leggere la stringa con scanf e stamparla al contrario.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    int len;
    printf("Inserisci la lunghezza massima: ");
    if (scanf("%d", &len) != 1) return 1;

    char *s = (char*) malloc((len + 1) * sizeof(char));
    if (s == NULL) return 1;

    printf("Inserisci la stringa: ");
    scanf("%s", s);

    int reale = strlen(s);
    for (int i = reale - 1; i >= 0; i--) {
        putchar(s[i]);
    }
    putchar('\n');

    free(s);
    s = NULL;
    return 0;
}

Esercizio 4: Prevenzione di Perdite con Malloc

Creare una funzione che allochi un array di 1000 interi. Simulare un fallimento inserendo intenzionalmente un ciclo che non libera la memoria. Aggiungere le istruzioni di rilascio necessarie per mantenere la stabilità del sistema ed evitare il leak.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>

void alloca_e_rilascia(void) {
    int *temp = (int*) malloc(1000 * sizeof(int));
    if (temp != NULL) {
        // Operazioni fittizie sui dati
        temp[0] = 99;

        // Rilascio corretto
        free(temp);
    }
}

int main(void) {
    for (int i = 0; i < 10000; i++) {
        alloca_e_rilascia(); // Senza free provocherebbe leak continui
    }
    printf("Esecuzione completata senza leak.\n");
    return 0;
}

Esercizio 5: Espansione di un Buffer con Realloc

Creare un array dinamico di 3 interi, popolarlo con i valori 10, 20, 30. Ridimensionarlo a 5 elementi usando realloc e inserire nelle nuove posizioni 40, 50. Stampare l’array finale.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int *arr = (int*) malloc(3 * sizeof(int));
    if (arr == NULL) return 1;

    arr[0] = 10; arr[1] = 20; arr[2] = 30;

    int *nuovo = (int*) realloc(arr, 5 * sizeof(int));
    if (nuovo == NULL) {
        free(arr);
        return 1;
    }
    arr = nuovo;
    arr[3] = 40; arr[4] = 50;

    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    free(arr);
    return 0;
}

Esercizio 6: Stringa Dinamica Concatenata

Scrivere una funzione char* concatena(const char *s1, const char *s2) che allochi dinamicamente lo spazio strettamente necessario a ospitare la concatenazione di due stringhe, la esegua e restituisca il puntatore al main.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* concatena(const char *s1, const char *s2) {
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    char *res = (char*) malloc((l1 + l2 + 1) * sizeof(char));
    if (res == NULL) return NULL;
    strcpy(res, s1);
    strcat(res, s2);
    return res;
}

int main(void) {
    char *c = concatena("Hello, ", "World!");
    if (c != NULL) {
        printf("%s\n", c);
        free(c);
        c = NULL;
    }
    return 0;
}

Esercizio 7: Copia Dinamica di una Struct

Data una struct typedef struct { char modello[20]; float prezzo; } Auto;, scrivere una funzione Auto* duplica_auto(const Auto *originale) che allochi nello Heap una copia identica della struct passata per riferimento e ne restituisca l’indirizzo.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char modello[20];
    float prezzo;
} Auto;

Auto* duplica_auto(const Auto *originale) {
    Auto *copia = (Auto*) malloc(sizeof(Auto));
    if (copia == NULL) return NULL;
    *copia = *originale; // Copia per assegnamento diretto delle struct!
    return copia;
}

int main(void) {
    Auto mia = {"Fiat Panda", 14500.0f};
    Auto *d = duplica_auto(&mia);
    if (d != NULL) {
        printf("Copia: %s - %.2f\n", d->modello, d->prezzo);
        free(d);
    }
    return 0;
}

Esercizio 8: Creazione di una Lista Dinamica di 3 Nodi

Scrivere un programma che definisca il tipo Nodo e popoli dinamicamente una catena di 3 nodi con valori inseriti dall’utente a runtime. Stampare la lista scorrendola tramite un puntatore temporaneo.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>

typedef struct Nodo {
    int valore;
    struct Nodo *prossimo;
} Nodo;

int main(void) {
    Nodo *testa = (Nodo*) malloc(sizeof(Nodo));
    Nodo *secondo = (Nodo*) malloc(sizeof(Nodo));
    Nodo *terzo = (Nodo*) malloc(sizeof(Nodo));

    if (testa == NULL || secondo == NULL || terzo == NULL) return 1;

    printf("Inserisci tre interi:\n");
    scanf("%d %d %d", &testa->valore, &secondo->valore, &terzo->valore);

    testa->prossimo = secondo;
    secondo->prossimo = terzo;
    terzo->prossimo = NULL;

    // Scorrimento pulito con puntatore temporaneo
    Nodo *curr = testa;
    while (curr != NULL) {
        printf("%d -> ", curr->valore);
        curr = curr->prossimo;
    }
    printf("NULL\n");

    free(testa);
    free(secondo);
    free(terzo);
    return 0;
}

Esercizio 9: Matrice Lineare Dinamica (Row-Major Order)

Scrivere un programma che allochi un array monodimensionale nello Heap per simulare una griglia di righe e colonne (matrice linearizzata). Leggere righe R e colonne C, popolare la matrice con il prodotto degli indici i * j e stamparla in forma tabellare.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int R = 3, C = 4;
    // Linearizzazione: allocazione di R * C celle contigue
    int *mat = (int*) malloc(R * C * sizeof(int));
    if (mat == NULL) return 1;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            mat[i * C + j] = i * j; // Formula Row-Major Order
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            printf("%3d ", mat[i * C + j]);
        }
        printf("\n");
    }

    free(mat);
    return 0;
}

Esercizio 10: Inserimento in Testa (Manuale)

Dato il puntatore iniziale Nodo *testa che punta a una catena esistente di 2 nodi (10 -> 20 -> NULL), implementare manualmente l’inserimento di un nuovo nodo di valore 5 in testa, aggiornando correttamente i puntatori. Stampare la nuova lista partendo da testa.

Soluzione proposta

#include <stdio.h>
#include <stdlib.h>

typedef struct Nodo {
    int valore;
    struct Nodo *prossimo;
} Nodo;

int main(void) {
    // Lista di partenza: 10 -> 20 -> NULL
    Nodo *n1 = (Nodo*) malloc(sizeof(Nodo));
    Nodo *n2 = (Nodo*) malloc(sizeof(Nodo));
    if (n1 == NULL || n2 == NULL) return 1;
    n1->valore = 10;
    n2->valore = 20;
    n1->prossimo = n2;
    n2->prossimo = NULL;

    Nodo *testa = n1;

    // NUOVO NODO DA INSERIRE IN TESTA
    Nodo *nuovo = (Nodo*) malloc(sizeof(Nodo));
    if (nuovo == NULL) return 1;
    nuovo->valore = 5;

    // INSERIMENTO: Il nuovo nodo punta alla vecchia testa
    nuovo->prossimo = testa;
    // La testa si sposta sul nuovo nodo
    testa = nuovo;

    // Stampa finale per validazione
    Nodo *temp = testa;
    while (temp != NULL) {
        printf("%d -> ", temp->valore);
        temp = temp->prossimo;
    }
    printf("NULL\n");

    // Liberazione di tutta la memoria
    free(n2);
    free(n1);
    free(nuovo);

    return 0;
}