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 ilconst
nella funzionelist_end()
. In generale, eliminare ilconst
in modo forzoso non è consigliabile e andrebbe evitato.
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.
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).
Nel caso di lista vuota, è comunque presente il nodo sentinella, il cui successore e predecessore è se stesso (Figura 2).
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.
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.
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
.