LabASD - Algoritmi ricorsivi per liste concatenate

Scopo di questa esercitazione è di prendere confidenza con gli algoritmi ricorsivi per la gestione di liste concatenate. Rappresentiamo una lista \(L\) come un puntatore ad una struttura List definita come segue:

typedef struct List {
  int val;
  struct list *next;
} List;

Possiamo notare come la definizione precedente sia già di per sé ricorsiva, dato che può essere letta nel modo seguente:

1. NULL è la lista vuota;

2. Altrimenti, se \(L\) non è la lista vuota, allora è costituita da una nodo contenente un valore val, seguito da una lista L->next.

Una definizione un po’ più formale che si trova in certi libri consiste nel definire una lista \(L\) come:

1. la lista vuota \(L = ()\), oppure

2. una coppia \(L = (v, L_1)\) costituita da un valore \(v\) seguito da una lista \(L_1\).

Ad esempio, in base alla definizione precedente, \(L = (0, (1, (2, (3, ()))))\) rappresenta la lista contenente gli interi \(0, 1, 2, 3\), in questo ordine.

Si vede che la definizione è ricorsiva perché al punto 2 si definisce il concetto di “lista” in termini di un’altra lista. In modo analogo è possibile definire altre strutture dati come gli alberi binari in termini di tipi di dato ricorsivi. Ad esempio, un albero binario \(B\) può essere definito come:

1. l’albero vuoto \(B = ()\), oppure

2. una terna \(B = (v, B_L, B_R)\) dove \(v\) è un valore, e \(B_L, B_R\) sono alberi binari.

Scopo di questo esercizio è realizzare alcune funzioni ricorsive che operano su liste; l’unica eccezione è la funzione list_reverse() per la quale si richiede una implementazione iterativa (sebbene sia possibile realizzarla in modo ricorsivo). Il codice contiene dei suggerimenti su come procedere nei vari casi.

Come esempio, consideriamo la funzione list_length(L) che restituisce la lunghezza (numero di nodi) di \(L\). La definizione ricorsiva di lista suggerisce una definizione ricorsiva di lunghezza come segue:

1. La lunghezza della lista vuota \(L = ()\) è zero.

2. La lunghezza di una lista non vuota \(L = (v, L_1)\) è data dalla lunghezza di \(L_1\) (calcolata ricorsivamente) più uno.

Traducendo in C la definizione precedente si ottiene:

int list_length(const List *L)
{
  if (L == NULL) {
    return 0;
  } else {
    return 1 + list_length(L->next);
  }
}

File

• list-rec.c