Memoria dinamica

Matteo Spanio
spanio@dei.unipd.it
Giulio Pitteri
giulio.pitteri@phd.unipd.it

10 aprile 2025

Strutture dati

Strutture dati

Le strutture sono molto utili per definire… strutture dati.

Per esempio si possono definire array dinamici, liste concatenate, alberi, pile, code…

Array con strutture

Gli array in C sono molto limitati, infatti dobbiamo gestire la loro lunghezza a mano…

Si può creare una struttura che contenga un array e la sua lunghezza:

#define MAX 1024

typedef struct intarray {
    int array[MAX];
    int length;
} IntArray;

Array con strutture

Adesso si può passare la struttura come argomento di una funzione:

void stampa_array(IntArray a) {
    for (int i = 0; i < a.length; i++) {
        printf("%d ", a.array[i]);
    }
    printf("\n");
}

Si nota subito che non abbiamo più bisogno di passare la lunghezza dell’array come argomento.

Array con strutture

int append(IntArray *a, int value) {
    if (a->length < MAX) {
        a->array[a->length] = value;
        a->length++;
        return 0;
    }
    return 1;
}
  1. append prende come argomento un puntatore a IntArray e un intero da aggiungere all’array, l’array è passato by reference perché i suoi campi vengono modificati
  2. Prima di effettuare l’inserimento viene controllato che l’array non sia già pieno, per accedere ai membri di un puntatore a una struttura si usa l’operatore ->, che è una forma abbreviata di (*p).membro

Esercizio

Per esercizio si implementino le funzioni:

int get(IntArray a, int index) che restituisce l’elemento in posizione index, int insert(IntArray *a, int index, int value) che inserisce l’elemento value in posizione index, int remove(IntArray *a, int index) che rimuove l’elemento in posizione index.

Scarica il main dell’esercizio

Consiglio

Si noti che le funzioni insert e remove possono fallire se l’array è pieno o vuoto, rispettivamente, inoltre è necessario spostare tutti gli elementi dell’array.

Array con strutture

L’implementazione che abbiamo visto ha due grossi problemi:

  1. la dimensione dell’array è fissa
  2. la struttura IntArray funziona solo con array di interi, per fare array di float, char, ecc. bisogna creare ogni volta una nuova struttura

Memoria dinamica

Memoria dinamica

  • Le strutture dati in C hanno dimensione fissa. Infatti gli array vengono inizializzati con un valore costante.

  • Esistono però dei comandi che permettono di allocare dinamicamente zone di memoria, permettendo di fare strutture che crescono o si rimpiccioliscono durante l’esecuzione del programma.

Memoria dinamica

Le operazioni per gestire la memoria dinamica si trovano nella libreria stdlib.h e sono:

  1. malloc (memory allocation): alloca una zona di memoria di una certa dimensione
  2. calloc (clear allocation): alloca una zona di memoria di una certa dimensione e la inizializza a 0
  3. realloc (reallocate): cambia la dimensione di una zona di memoria già allocata

Puntatore a void

malloc, calloc e realloc restituiscono un puntatore a void, che è un puntatore generico.

Questo puntatore non fa riferimento a un certo tipo di dato, ma solo a un indirizzo di memoria.

malloc

void* malloc(size_t size);

Supponendo di voler creare un array di interi di dimensione variabile, c’è bisogno di creare un puntatore ad interi e poi assegnargli l’indirizzo della nuova zona di memoria:

int *a;
a = malloc(10 * sizeof(int));

La funzione malloc accetta come argomento il numero di byte da allocare. L’esempio crea 10 cellette di memoria, ciascuna grande quanto un intero (4 byte).

calloc

void* calloc(size_t num, size_t size);

  • Per inizializzare array torna comoda anche la funzione calloc, che ha due parametri: numero di membri e dimensione (in byte) dei membri
  • Inoltre ha come effetto aggiuntivo di porre a zero tutti i byte interessati (quindi tutti i membri dell’array che creo)
double *a;
a = calloc(10, sizeof(double));

L’effetto di questo codice è lo stesso del precedente (con la malloc), ma con tutti i membri dell’array inizializzati a 0.

realloc

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

  • Questa funzione cambia la dimensione di uno spazio allocato dinamicamente.

  • L’argomento ptr deve essere un puntatore ottenuto da una funzione ..alloc, altrimenti porta a comportamento non definito.

  • I dati già presenti nella zona di memoria vengono mantenuti.

NULL

  • Quando si usa la memoria dinamica, è importante controllare che l’allocazione sia andata a buon fine.

  • Se malloc, calloc o realloc non riescono a trovare spazio in memoria, restituiscono NULL.

  • NULL è una costante che rappresenta un puntatore all’indirizzo 0x0. NULL è definito in stdlib.h.

malloc, calloc, realloc

  • Queste funzioni scrivono in una zona di memoria nota come heap;
  • Le variabili locali e i parametri delle funzioni sono invece memorizzati nello stack;
  • Usando ricorsione e molta memoria dinamica si può esaurire la memoria disponibile
  • Occorre quindi fare uso oculato della memoria e pulire quella usata che non serve più

free

void free(void* ptr);

  • La funzione free permette di liberare un blocco di memoria (e quindi renderlo disponibile per un’altra allocazione)
  • ptr dopo l’esecuzione di free continua a puntare alla stessa zona di memoria, ma il contenuto di quella zona non è più garantito, si chiama dangling pointer
  • Occorre, subito dopo la free, assegnare a ptr il valore NULL (oppure una nuova memoria)
  • accedere un blocco deallocato è un gravissimo errore

Array dinamico

Un array dinamico è un array la cui dimensione può cambiare durante l’esecuzione del programma.

Per implementare un array dinamico si può usare una struttura che contiene un puntatore all’array e la sua lunghezza:

typedef struct {
    int *array;
    int capacity;
    int length;
} ArrayList;

ArrayList

Il nuovo tipo ArrayList ha tre membri:

  • array è un puntatore ad interi, che punta all’array dinamico
  • capacity è la dimensione massima dell’array
  • length è il numero di elementi attualmente presenti nell’array

Quando length raggiunge capacity, bisogna riallocare la memoria per l’array, aumentando la sua dimensione.

Scarica l’implementazione dell’arraylist

Linked list

  • Una lista concatenata è una struttura dati composta da nodi, ciascuno dei quali contiene un valore e un puntatore al nodo successivo.
  • La differenza con un array è che i nodi non sono memorizzati in posizioni contigue di memoria.
  • La lista concatenata è una struttura ricorsiva: un nodo contiene un valore e un puntatore al nodo successivo.

Linked list

L’implementazione classica della lista concatenata in C è:

typedef struct node {
    int value;
    struct node *next;
} Node;

Scarica l’implementazione della linked list

Esercizio: lista concatenata

Dato il file con il main e i prototipi delle funzioni, implementare:

  • recursive_list_print
  • recursive_list_delete