LabASD - Liste doppiamente concatenate con sentinella

Moreno Marzolla

Ultimo aggiornamento: 2024-03-18

(Crediti: prof. Violetta Lonati, Università di Milano)

Versione modificata rispetto a quanto originariamente mostrato in laboratorio: il nodo sentinella è ora un puntatore anziché una struttura membro di List come in precedenza. Questo consente di evitare il cast che era necessario a eliminare il const nella funzione list_end(). In generale, eliminare il const in modo forzoso non è consigliabile e andrebbe evitato.

Fonte: https://www.youtube.com/watch?v=UqmnUe4pDdU
Fonte: https://www.youtube.com/watch?v=UqmnUe4pDdU

Implementare la struttura dati “lista doppiamente concatenata con sentinella”, la cui interfaccia è specificata nel file list.h. In una lista doppiamente concatenata, ogni nodo (che ha tipo ListNode) contiene un attributo val di tipo ListInfo (che qui è un intero), e due puntatori succ e pred al nodo successivo e precedente, rispettivamente.

typedef int ListInfo;

typedef struct ListNode {
    ListInfo val;
    struct ListNode *succ, *pred;
} ListNode;

La struttura List contiene un attributo length che indica la lunghezza della lista (escluso il nodo sentinella), e un puntatore sentinel al nodo sentinella.

typedef struct {
    int length;
    ListNode *sentinel;
} List;

In questo tipo di lista è infatti presente un nodo speciale, detto “sentinella”, che non contiene alcuna informazione utile ma serve solo per marcare l’inizio (o la fine) della lista; di fatto la presenza della sentinella trasforma la lista in un anello. La sentinella consente di accedere in tempo \(O(1)\) al primo e ultimo nodo della lista: il primo è il successore della sentinella, mentre l’ultimo è il predecessore (Figura 1).

Figura 1: Lista doppiamente concatenata con sentinella
Figura 1: Lista doppiamente concatenata con sentinella

Nel caso di lista vuota, è comunque presente il nodo sentinella, il cui successore e predecessore è se stesso (Figura 2).

Figura 2: Lista vuota con sentinella
Figura 2: Lista vuota con sentinella

Oltre a consentire accesso in tempo costante agli estremi della lista, la sentinella semplifica le operazioni di inserimento e cancellazione, perché garantisce che ogni nodo abbia sempre un predecessore e un successore. Non occorre quindi gestire in modo speciale la lista vuota o le operazioni che coinvolgono il primo o l’ultimo elemento.

Nel file list.h vengono descritte le funzioni dell’interfaccia del tipo List. L’unico punto di attenzione è l’iterazione. Come esempio consideriamo la funzione list_print(L) che stampa il contenuto di L. La funzione si può realizzare mediante un ciclo while

void list_print(List *L)
{
    ListNode *node = list_first(L);
    while (node != list_end(L)) {
        printf("%d ", node->val);
        node = list_succ(node);
    }
    printf("\n");
}

oppure for

void list_print(List *L)
{
    ListNode *node;
    for (node = list_first(L); node != list_end(L); node = list_succ(node)) {
        printf("%d ", node->val);
    }
    printf("\n");
}

list_first(L) restituisce un puntatore al primo nodo di L, oppure alla sentinella se la lista è vuota; list_succ(node) restituisce un puntatore al successore di node, mentre list_end() restituisce un puntatore alla sentinella. Questa interfaccia è conforme a strutture dati analoghe di linguaggi come Java o C++;

Il file list-main.c contiene un programma che esegue una sequenza di comandi da un file il cui nome va specificato sulla riga di comando. L’elenco dei comandi con il relativo significato è riportato nella Tabella 1.

Tabella 1: Comandi nel file di input
Operazione Significato
+ k Inserisci un nuovo nodo contenente k in testa alla lista. Sono ammessi valori duplicati.
- k Cancella il primo nodo contenente k, se presente; altrimenti, non fa nulla.
? k Cerca il valore k nella lista, e stampa un opportuno messaggio per indicarne o meno la presenza.
n idx Stampa il valore contenuto nel nodo in posizione idx; il primo nodo ha posizione idx = 0, il secondo ha posizione idx = 1, e così via. Se idx è maggiore o uguale al numero di elementi della lista, stampa un opportuno messaggio.
l Stampa la lunghezza della lista.
p Stampa tutto il contenuto della lista.
c Svuota la lista, cancellando tutti i nodi in essa contenuti.

È possibile inserire più volte lo stesso valore; in caso di cancellazione di un valore ripetuto, è sufficiente cancellarne una occorrenza qualsiasi.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic list.c list-main.c -o list-main

Per eseguire in ambiente Linux/MaxOSX:

    ./list-main list.in

Per eseguire in ambiente Windows:

    .\list-main list.in

Come sempre, è possibile realizzare ulteriori funzioni di supporto.

Suggerimento

Le funzioni list_add_first() e list_add_last() possono essere espresse facilmente sfruttando una funzione ausiliaria (da definire)

    static void list_insert_after(List *L, ListNode *n, ListInfo k)

che crea un nuovo nodo contenente il valore k, e lo inserisce immediatamente dopo il nodo n della lista L.

File