Salta al contenuto
Note per Studenti Esercizio 26 · C, pulizia del file system (albero binario)

Esercizio 26C, pulizia del file system (albero binario)

In questa pagina 4

Testo (scritto del 30/01/2026, parte 3, in C). Pulizia del file system. Svolgi il seguente esercizio sviluppando le funzioni richieste in C. I prototipi delle funzioni non possono essere modificati. Durante l'esame non è possibile consultare appunti o materiale didattico; è consentito usare la documentazione Linux con man.

Si vuole implementare un algoritmo di pulizia automatica del file system (system cleaner) con complessità Θ(n)\Theta(n), in grado di individuare ed eliminare file inutili e cartelle vuote. Il file system è rappresentato tramite un albero binario, dove ogni nodo rappresenta un file o una directory. In particolare:

  • un file ha una dimensione in byte size ≥0\ge 0;
  • un file di 00 byte è considerato inutile e deve essere eliminato;
  • una directory ha dimensione in byte pari a 11;
  • una directory vuota è una directory senza figli;
  • ogni directory può contenere al più due elementi (file o directory).

Le foglie dell'albero rappresentano file (anche di 00 byte) o directory vuote, mentre i nodi interni rappresentano solo directory non vuote. L'algoritmo di pulizia deve: eliminare tutti i file di dimensione 00 byte; eliminare tutte le directory vuote; se una directory diventa vuota dopo la pulizia dei figli, deve essere eliminata anch'essa. La visita deve avvenire in un'unica scansione dell'albero, con complessità Θ(n)\Theta(n).

c
typedef struct node {
    int size;
    char filename[64];
    struct node *left;
    struct node *right;
} Node;

Pseudocodice di cleanFileSystem(root) (Input: puntatore alla radice; Output: numero totale di nodi eliminati; side effect: il file system viene modificato in loco): se root = NULL restituisce 00; deleted <- 0; deleted <- deleted + cleanFileSystem(root.left); deleted <- deleted + cleanFileSystem(root.right); se root.size = 0 e root.left = NULL e root.right = NULL: elimina root, root <- NULL, restituisce deleted + 1; se root.size = 1 e root.left = NULL e root.right = NULL: elimina root, root <- NULL, restituisce deleted + 1; altrimenti restituisce deleted. Lo pseudocodice non è codice C completo (tipi, puntatori, chiamate a free); si possono definire funzioni ausiliarie.

Funzione da implementare: int cleanFileSystem(Node **root), che elimina file inutili e directory vuote e restituisce il numero totale di nodi eliminati.

Richiami

Albero binario in C e visita in postorder (prima i figli, poi il nodo), vedi 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 →; passaggio di Node ** per poter azzerare un puntatore del chiamante, vedi Puntatori, struct e memoria dinamica in CPuntatori e passaggio per riferimento in C, array e aritmetica dei puntatori, stringhe, struct e typedef con l'operatore ->, malloc e free, puntatore a puntatore per modificare una testa; compilazione con Makefile; errori tipici (puntatori pendenti, perdite di memoria, off-by-one).Puntatori, struct e memoria dinamica in C →.

Soluzione

c
int cleanFileSystem(Node **root) {
    if (*root == NULL)
        return 0;
    int deleted = 0;
    deleted += cleanFileSystem(&(*root)->left);       /* prima i figli (postorder) */
    deleted += cleanFileSystem(&(*root)->right);
    Node *r = *root;
    if (r->left == NULL && r->right == NULL && (r->size == 0 || r->size == 1)) {
        free(r);                                       /* file di 0 byte o directory vuota */
        *root = NULL;                                  /* il genitore (o il chiamante) vede NULL */
        return deleted + 1;
    }
    return deleted;
}

Perché Node **. Il prototipo ha un puntatore a puntatore: *root è il puntatore nel genitore (il campo left o right, o la variabile radice del chiamante). Dopo free(r) bisogna scrivere *root = NULL, altrimenti il genitore resterebbe con un puntatore pendente a memoria liberata. Le chiamate sui figli passano &(*root)->left e &(*root)->right, cioè gli indirizzi dei campi.

Perché postorder. Il padre può essere eliminato solo dopo aver ripulito i figli: una directory con due file da 00 byte diventa vuota dopo la pulizia e viene eliminata nella stessa visita (un'unica scansione). Con un preorder la si vedrebbe ancora non vuota.

Complessità. Ogni nodo è visitato una volta con lavoro costante (al più una free): Θ(n)\Theta(n) tempo, O(h)O(h) stack.

Prova eseguita

Albero root (1)(1) con figlio sinistro cartella (1)(1), che ha i figli file valido (5)(5) e cartella vuota (1)(1), e figlio destro file vuoto (0)(0). cleanFileSystem(&root) elimina cartella vuota e file vuoto e restituisce 22: restano root →\to cartella →\to file valido. Secondo caso: root (1)(1) con solo figlio sinistro sub (1)(1), a sua volta con due file da 00 byte: vengono eliminati i due file, poi sub (diventata vuota) e infine root: restituisce 44 e la radice del chiamante diventa NULL.

Nota sul modello. Con questa rappresentazione un file di esattamente 11 byte è indistinguibile da una directory vuota (entrambi size =1= 1 e nessun figlio): lo pseudocodice del testo li elimina entrambi, ed è quanto richiede l'esame.

Errori comuni

  • Usare Node *root come parametro: dopo free il puntatore del chiamante resta pendente e il nodo non viene scollegato dal genitore.
  • Dimenticare *root = NULL dopo free(*root).
  • Eliminare il nodo prima di ripulire i figli (preorder): le directory che si svuotano dopo la pulizia rimarrebbero.
  • Leggere r->left dopo free(r).
  • Non contare i nodi eliminati dai figli nel valore restituito.

Versione ripasso

Testo. Albero binario di file e directory (size ≥0\ge 0 per i file, 11 per le directory); eliminare i file da 00 byte e le directory vuote (anche quelle che si svuotano) in un'unica scansione Θ(n)\Theta(n); int cleanFileSystem(Node **root) restituisce il numero di nodi eliminati.

Teoria collegata