LabASD - Lista concatenata con sentinella

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-07

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

Implementare una lista doppiamente concatenata con sentinella; il file list.h contiene la specifica dell'interfaccia. In una lista concatenata, ogni nodo (che ha tipo ListNode) ha un puntatore al nodo precedente e al nodo successivo, oltre ad un attributo val che contiene il valore memorizzato in quel nodo. I valori sono di tipo ListInfo, che di default è impostato al tipo int.

In una lista con sentinella è presente un nodo speciale, detto "sentinella", che non contiene alcuna informazione utile ma serve solo per marcare l'inizio (o la fine) della lista. La lista vuota viene rappresentata come mostrato in Figura 1.

Figura 1: Lista vuota con sentinella
Figura 1: Lista vuota con sentinella

Il tipo di dato List è una struttura contenente un intero che indica la lunghezza della lista (esclusa la sentinella), e la sentinella. Nel caso di lista vuota, i puntatori succ e pred della sentinella puntano alla sentinella stessa.

Una lista non vuota appare come mostrato in Figura 2.

Figura 2: Lista doppiamente concatenata con sentinella
Figura 2: Lista doppiamente concatenata con sentinella

Tramite la sentinella è possibile avere accesso diretto al primo e all'ultimo elemento della lista, in modo da supportare l'inserimento in testa o in coda in tempo \(O(1)\). La sentinella inoltre semplifica le operazioni sulla lista, in quanto non occorre gestire il caso particolare di lista vuota; inoltre, il primo e l'ultimo nodo della lista non devono essere gestiti in modo speciale.

Il file list-main.c contiene un main() che legge da standard input una sequenza di operazioni da eseguire su una lista inizialmente vuota.

Operazione Significato
+ k Inserisci un nuovo nodo contenente k
- k Cancella uno dei nodi contenenti 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
l Stampa la lunghezza della lista
p Stampa il contenuto della lista
r Svuota la lista, cancellando tutti i nodi in essa contenuti

Si tenga presente che è possibile inserire più volte lo stesso valore; in caso di cancellazione di un valore ripetuto, sarà sufficiente cancellarne una occorrenza qualsiasi.

Esempio di file di input list.in; su sistemi Linux/MacOSX, dopo aver compilato il programma con

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

è possibile provare l'input con il comando:

    ./list-main < list.in

oppure

    ./list-main list.in

Come sempre, è possibile realizzare ulteriori funzioni di supporto.

Per approfondire

Chi lo desidera può implementare ulteriori operazioni (es., inserimento in coda o in testa; cancellazione dalla testa o dalla coda), oppure realizzare una variante della lista in cui gli elementi vengono mantenuti ordinati.

File