11  Livello 9

11.1 Introduzione all’allocazione dinamica

Fino a questo punto, la gestione della memoria è stata delegata interamente al compilatore attraverso l’allocazione statica. In questo scenario, le variabili locali vengono allocate nell’area di memoria denominata Stack all’atto della chiamata di una funzione, vengono distrutte (deallocate) in modo automatico al termine della stessa e la quantità di memoria necessaria deve essere nota a tempo di compilazione (compile-time).

Per superare quest’ultimo vincolo, il C offre gli strumenti per l’allocazione dinamica della memoria. Questo paradigma trasferisce il controllo dal compilatore al programmatore, consentendo di richiedere spazio durante l’esecuzione (run-time) all’interno di un’ampia area di memoria denominata Heap.

11.1.1 malloc e free

La gestione manuale dell’Heap si basa sulle funzioni messe a disposizione dalla libreria di sistema <stdlib.h>. L’operazione di allocazione si esegue (tipicamente) tramite la funzione malloc() (memory allocation) che richiede in ingresso la dimensione esatta in byte dello spazio desiderato e restituisce l’indirizzo del blocco allocato.

Si consideri la seguente istruzione fondamentale:

p = malloc(sizeof(int));

In questa riga si concentrano diverse operazioni cruciali:

  1. L’operatore sizeof(int) calcola la dimensione necessaria per ospitare un numero intero.
  2. La funzione malloc riserva quello spazio nell’Heap.
  3. L’indirizzo di memoria viene infine assegnato al puntatore p (il quale risiede invece nello Stack).

Da questo momento, l’intero allocato nell’Heap è accessibile esclusivamente per via indiretta dereferenziando il puntatore (es. *p = 10;).

A differenza dello Stack, l’Heap non è soggetto a pulizia automatica, una volta che la variabile dinamica non è più necessaria, lo spazio deve essere liberato tramite la funzione free(p);.

11.2 Le liste concatenate

Una lista concatenata è una struttura dati composta da un insieme di elementi omogenei (tutti del medesimo tipo: una struct definita dall’utente), la cui implementazione si basa sull’utilizzo dei puntatori. In questa sezione verrà illustrato come creare e gestire una lista concatenata in cui gli elementi non sono dichiarati staticamente a priori, bensì generati dinamicamente durante l’esecuzione del programma.

Vi sono alcuni principi fondamentali e imprescindibili da tenere a mente quando si opera con le liste concatenate:

  • Allocazione dinamica: ogni qualvolta sia necessario creare un nuovo nodo (elemento), occorre allocare esplicitamente lo spazio in memoria. Questa operazione si esegue avvalendosi della funzione malloc (inclusa nella libreria <stdlib.h>). La malloc restituisce un puntatore all’area allocata e richiede come parametro la dimensione in byte dell’elemento. Un esempio di chiamata per una struttura definita dall’utente denominata mia_lista è: malloc(sizeof(struct mia_lista)). Si osservi il seguente frammento utilizzato per allocare la memoria nell’heap necessaria a un singolo elemento:
struct mia_lista *p;
p = malloc(sizeof(struct mia_lista));

A questo punto, è possibile utilizzare il puntatore p per accedere alla nuova locazione di memoria appena allocata.

  • Puntatore interno (concatenazione): ogni singolo elemento della lista sarà collegato al nodo successivo tramite un puntatore interno. Di conseguenza, in fase di definizione della struct, è tassativo includere un puntatore (come campo membro) al medesimo tipo di struttura (creando una struttura autoreferenziale):
struct mia_lista {
    int num;
    struct mia_lista *next;
};

L’omissione di questo puntatore (denominato next nell’esempio) renderà impossibile la concatenazione dei nodi.

  • Terminazione della lista: per utilizzare e scansionare correttamente la lista, è indispensabile garantire che il puntatore interno dell’ultimo elemento della lista sia esplicitamente impostato a NULL. Questo costituisce il criterio di arresto che permette di iterare sui nodi fermandosi nel momento esatto in cui la lista è terminata.
  • Puntatore di testa (Head): dove si trova fisicamente la lista? L’intera lista è identificata da un singolo puntatore rivolto al suo primo elemento. Se i nodi sono concatenati correttamente e l’ultimo punta a NULL, è sufficiente questo singolo puntatore esterno per mantenere le coordinate di partenza. In assenza di tale riferimento, non sarà più possibile accedere alla lista e deallocare (tramite free) la memoria occupata, generando un memory leak permanente per tutta la durata dell’esecuzione del programma.

Questi costituiscono i fondamenti teorici per la gestione di una lista. Tuttavia, la piena comprensione di queste dinamiche si acquisisce unicamente attraverso la pratica.

11.2.1 Crea e visualizza una lista

Vediamo un esempio dedicato alla gestione di una lista concatenata di interi. Il codice illustra la creazione dinamica (con inserimento in coda), la scansione per la stampa e, infine, la deallocazione della memoria per prevenire memory leak.

Il programma inizia con la definizione della struttura lista e la dichiarazione dei prototipi delle funzioni. Nel blocco del main si dichiara il puntatore di testa (punt_lista) e si inseriscono le chiamate alle funzioni, verificando che l’allocazione iniziale sia andata a buon fine.

#include <stdio.h>
#include <stdlib.h>
struct lista {
    int num;
    struct lista *next;
};
struct lista *crealista();
void visualizza_lista(struct lista *);
void libera_lista(struct lista *);

int main(void) {
    struct lista *punt_lista;
    punt_lista = crealista();    
    if(punt_lista != NULL) {
        visualizza_lista(punt_lista);
        libera_lista(punt_lista);
    }
    return 0;
}

La funzione crealista deve istanziare i nodi e concatenarli opportunamente attraverso l’uso di due puntatori:

  • p: funge da riferimento alla “testa” della lista. È l’indirizzo che verrà restituito al main al termine dell’esecuzione.
  • paux (puntatore ausiliario): partendo dalla testa, si sposta progressivamente in avanti per agganciare i nuovi nodi in coda.
struct lista *crealista() {
    int n, i;
    struct lista *p, *paux;    
    printf("Quanti elementi vuoi inserire? ");
    scanf("%d", &n);    
    if(n < 1) p = NULL;
    else {
        // Allocazione e inizializzazione del nodo di testa
        p = malloc(sizeof(struct lista));
        printf("Inserisci valore: ");
        scanf("%d", &p->num);        
        paux = p; // Il puntatore ausiliario si allinea alla testa        
        // Ciclo di creazione e concatenazione dei nodi successivi
        for(i = 2; i <= n; i++) {
            paux->next = malloc(sizeof(struct lista));
            paux = paux->next; // Avanzamento sul nuovo nodo
            printf("Inserisci valore: ");
            scanf("%d", &paux->num);
        }
        paux->next = NULL; // Terminazione della lista
    }
    return p;
}

Per scansionare la lista, la funzione iterativa sfrutta il passaggio dei parametri per valore tipico del linguaggio C. Il parametro formale p riceve una copia dell’indirizzo di testa. All’interno del ciclo while, l’istruzione p = p->next permette di “scorrere” la lista nodo per nodo fino a incontrare il terminatore NULL. Operando su una copia, il puntatore originario nel main rimane intatto.

void visualizza_lista(struct lista *p) {
    while(p != NULL) {
        printf("%d ", p->num);
        p = p->next;
    }
    printf("\n");
}

L’ultima fase affronta la distruzione della struttura dati. La liberazione della memoria richiede un’attenzione particolare all’ordine delle operazioni. Se si eseguisse la sequenza free(p); p = p->next;, il programma tenterebbe di leggere il campo next di un’area di memoria che è già stata liberata, scatenando un errore noto come Use After Free. Per evitare tale situazione, è d’obbligo l’impiego di un puntatore temporaneo.

void libera_lista(struct lista *p) {
    struct lista *paux;

    while(p != NULL) {
        paux = p; // 1. Salva l'indirizzo del nodo corrente
        p = p->next; // 2. Avanza al nodo successivo
        free(paux); // 3. Dealloca il nodo corrente, isolato
    }
}

11.2.2 Inserisci elementi in una lista

Rispetto alla creazione in blocco vista in precedenza, un approccio più flessibile prevede l’aggiunta dinamica e iterativa dei singoli nodi durante l’esecuzione del programma. Le due tipologie standard per questa operazione sono l’inserimento in testa (che inserisce il nuovo elemento come primo nodo della catena) e l’inserimento in coda (che lo aggancia come ultimo elemento).

Di seguito viene analizzato un programma che implementa l’inserimento in coda, permettendo all’utente di gestire la lista tramite un menu testuale.

Il main funge da gestore di tutte le funzioni. È fondamentale notare l’inizializzazione del puntatore di testa: struct lista *punt_lista = NULL;. Questa istruzione stabilisce in modo esplicito che, all’avvio del programma, la lista è vuota. L’interfaccia utente è governata da un ciclo while accoppiato a uno switch-case, che chiama le funzioni mantenendo aggiornato il puntatore principale.

#include <stdio.h>
#include <stdlib.h>
struct lista {
    int num;
    struct lista *next;
};
struct lista *ins_coda(struct lista *);
void visualizza_lista(struct lista *);
int main(void) {
    struct lista *punt_lista = NULL; // Inizializzazione a lista vuota
    int sel = -1;    
    while(sel != 0) {
        printf("\n1- Inserisci elemento\n");
        printf("2- Visualizza elementi\n");
        printf("0- Esci\n");
        printf("Scelta: ");
        scanf("%d", &sel);        
        switch (sel) {
            case 1:
                // Il puntatore viene aggiornato con il valore restituito
                punt_lista = ins_coda(punt_lista);
                break;
            case 2:
                if(punt_lista != NULL) {
                    printf("\nLista elementi: ");
                    visualizza_lista(punt_lista);
                } else {
                    printf("\nLista vuota\n");
                }
                break;
            case 0:
                printf("\nProgramma terminato\n");
                break;
            default:
                printf("\nScelta non valida\n");
        }
    }
    return 0;
}

L’operazione di inserimento in coda richiede una gestione dei casi limite. La funzione ins_coda accetta come parametro l’indirizzo di testa della lista e restituisce il valore (che potrebbe essere mutato). L’algoritmo è organizzato in tre fasi:

  1. Allocazione: si crea in memoria il nuovo nodo isolato (p1) e se ne popola il campo dati con l’input dell’utente.
  2. Gestione del caso base (lista vuota): se il puntatore di testa ricevuto in ingresso è NULL, significa che la lista è ancora vuota. Il nuovo nodo diviene la testa della lista. Il suo campo next viene impostato a NULL e l’indirizzo di p1 viene assegnato al puntatore principale p.
  3. Gestione del caso generale (lista popolata): se la lista contiene già dei nodi, il nuovo elemento p1 è destinato a diventarne la coda e di conseguenza, il suo campo next viene forzato a NULL. Successivamente, si utilizza un puntatore ausiliario (paux) per attraversare l’intera lista partendo dalla testa, fino a individuare l’attuale ultimo elemento (condizione: while(paux->next != NULL)). Trovato l’elemento terminale, se ne modifica il campo next per agganciarlo fisicamente al nuovo nodo p1.
struct lista *ins_coda(struct lista *p) {
    struct lista *p1, *paux;
    // 1. Allocazione e popolamento del nuovo nodo
    p1 = malloc(sizeof(struct lista));
    printf("Inserisci valore: ");
    scanf("%d", &p1->num);    
    // 2. Caso Base: la lista è attualmente vuota
    if(p == NULL) {
        p = p1; // Il nuovo nodo diventa la testa
        p->next = NULL; // La lista termina immediatamente
    }
    // 3. Caso generale: la lista ha già degli elementi
    else {
        p1->next = NULL; // Il nuovo nodo va in coda
        paux = p; // Il puntatore ausiliario parte dalla testa        
        // Scorrimento fino all'ultimo nodo esistente
        while(paux->next != NULL) {
            paux = paux->next;
        }        
        // Aggancio del nuovo nodo in coda all'ultimo elemento
        paux->next = p1;
    }    
    // Restituzione del puntatore di testa
    return p;
}
ConsiglioArchitettura della Memoria: Stack vs Heap

Ogni programma C in esecuzione gestisce la memoria allocata secondo due paradigmi fondamentali: allocazione statica e allocazione dinamica.

  • Lo Stack (allocazione statica): è una regione di memoria a dimensione fissa, gestita in modo automatico dal compilatore secondo una logica LIFO (Last-In, First-Out). Ospita le variabili locali e i parametri delle funzioni. Ha un tempo di accesso estremamente rapido, ma la sua rigidità dimensionale (definita a compile-time) espone al rischio di esaurimento dello spazio (Stack Overflow) se si tenta di allocare array statici troppo grandi.
  • L’Heap (allocazione dinamica): è un’ampia area di memoria gestita manualmente dal programmatore tramite funzioni specifiche (es. malloc, free). La sua dimensione è elastica e determinata a run-time, permettendo di gestire strutture dati che crescono o si riducono dinamicamente (come le liste concatenate). L’accesso ai dati (che avviene tramite puntatori) è leggermente meno rapido rispetto allo stack, ma offre una maggiore flessibilità.

11.3 Array dinamici

Sebbene nel linguaggio C non esista nativamente il concetto di array a dimensione dinamica, è possibile simularne perfettamente il comportamento richiedendo al sistema operativo l’allocazione di blocchi contigui di memoria tramite le funzioni malloc o calloc.

Si analizzi il seguente esempio applicativo:

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

int main(void) {
    int i, n;
    int *ptr;
    printf("Inserisci la dimensione dell'array: ");
    scanf("%d", &n);
    // Allocazione dinamica tramite calloc (azzera anche la memoria)
    ptr = calloc(n, sizeof(int));    
    // Alternativa equivalente con malloc (non azzera la memoria):
    // ptr = (int*) malloc(n * sizeof(int));
    for(i = 0; i < n; i++) {
        printf("\nInserisci valore: ");        
        // Acquisizione tramite aritmetica dei puntatori
        scanf("%d", ptr + i);
        // Equivalente alla notazione vettoriale: scanf("%d", &ptr[i]);
    }
    printf("\nArray inserito: ");
    for(i = 0; i < n; i++) {
        printf("%d ", *(ptr + i));
        // Equivalente alla notazione vettoriale: printf("%d ", ptr[i]);
    }
    // Passaggio fondamentale: rilascio della memoria allocata
    free(ptr);    
    return 0;
}

11.4 Array dinamici e funzioni

L’integrazione tra l’allocazione dinamica e la programmazione modulare richiede una gestione attenta degli indirizzi di memoria. Quando si demanda a una funzione il compito di allocare e inizializzare un array dinamico, si pone il problema di come trasferire l’indirizzo della memoria allocata al blocco chiamante (il main), affinché quest’ultimo possa utilizzarla (per visualizzarne i valori) o deallocarla.

Le due soluzioni proposte mostrano due paradigmi differenti per risolvere questo problema.

11.4.1 Soluzione 1: restituzione dell’indirizzo

#include <stdio.h>
#include <stdlib.h>
int * allocate_array(int size);
int main (void) {
    int i,n, *ptr;
    printf("\nInserisci dimensione array: ");
    scanf("%d",&n);
    ptr=allocate_array(n);
    printf("ptr: %p\n",ptr);
    for(i=0;i<n;i++) printf("%d ",*(ptr+i));
    free(ptr);
}
int * allocate_array(int size) {
    int i,*p;
    p=calloc(size, sizeof(int));
    printf("p: %p\n",p);
    for(i=0;i<size;i++)
        scanf("%d",p+i);
    return p;
}

Il primo approccio è il più intuitivo. La funzione viene progettata per restituire esplicitamente un puntatore al tipo di dato allocato. All’interno della funzione viene dichiarato un puntatore locale p a cui si assegna l’indirizzo generato da calloc. Dopo aver popolato l’array acquisendo i dati dall’utente, la funzione termina con l’istruzione return p;. Nel main, l’indirizzo restituito viene semplicemente catturato tramite un’operazione di assegnamento: ptr = allocate_array(n);. Da questo momento, il puntatore ptr del main referenzia correttamente l’area Heap allocata dalla funzione.

11.4.2 Soluzione 2: doppio puntatore

#include <stdio.h>
#include <stdlib.h>
void allocate_array(int size, int **p);
int main (void) {
    int i,n, *ptr;
    printf("Inserisci dimensione array: ");
    scanf("%d",&n);
    printf("Indirizzo ptr: %p\n",&ptr);
    allocate_array(n,&ptr);
    printf("Valore di ptr in main: %p\n",ptr);
    for(i=0;i<n;i++) printf("%d ",*(ptr+i));
    free(ptr);
}
void allocate_array(int size, int **p) { //p=&ptr;
    int i;
    printf("Indirizzo ptr nella f: %p\n",p);
    *p=calloc(size, sizeof(int));
    //*p equivale al valore di ptr del main -> ptr = calloc...
    printf("Contenuto di ptr in f: %p \n",*p);
    for(i=0;i<size;i++) scanf("%d",*p+i); //carico in array dinamico
}

Il secondo approccio è di grande rilevanza, in quanto elimina l’istruzione di return e la funzione non restituisce nulla (void), ma modifica direttamente il puntatore definito nel main. Per far sì che la funzione modifichi in modo permanente la variabile del modulo chiamante, è necessario passare l’indirizzo di tale variabile. Poiché la variabile da modificare nel main è già un puntatore (int *ptr), il suo indirizzo &ptr sarà inevitabilmente un puntatore a puntatore (int **p). All’interno della funzione, l’istruzione *p = calloc(size, sizeof(int)); esegue una dereferenziazione, non sta assegnando la memoria al parametro locale p, ma sta scrivendo l’indirizzo restituito dalla calloc direttamente dentro la variabile ptr del main. Per scorrere e popolare l’array, si utilizza l’espressione *p + i, in questo modo si legge prima l’indirizzo base contenuto nel main (*p) e poi si applica l’aritmetica dei puntatori aggiungendo l’offset i.