
DIPARTIMENTO DI INFORMATICA Università di Torino

Lezione di Mercoledi' 20/02/02 - ultimo aggiornamento: 22/02/02

Funzioni ricorsive che operano su liste linkate - liste doppiamente linkate e altre varianti delle liste linkate

CHE COSA E' STATO FATTO A LEZIONE

Funzioni ricorsive che operano su liste linkate

Costruzione della lista che contiene i nodi nell'intervallo da 1 a N, genearando (cioe' facendo la newnode()) i singoli nodi nell'ordine da 1 a N.

Funzione ricorsiva lineare

La funzione "buildlis_n_rnf" in [NOTE1:pag. 42] puo' essere riscritta nel seguente modo:

/*
  AI: 
  AF: Restituisce la lista degli interi nell'intervallo da i a j
      (generando i nodi in ordine da i a j)
*/
node *buildlis_int_rn (int i, int j)
{
   if (i > j) 
      return NULL;
   else
   {
      node *p = newnode();
      p->data = i;
      p->next = buildlis_int_rn (i+1,j)
      return p;
   }
}

La complessita' in tempo della funzione "buildlis_int_rn" e' lineare nella lunghezza della lista L prodotta (ovvero: costante se j > i, e lineare in j-i+1 altrimenti).

Funzione ricorsiva di coda (versione 1)

La funzione "buildlis_int_rn" e' ricorsiva lineare. Trasformiamo tale funzione in una funzione lineare di coda (mantenendo la proprieta' che i nodi vengono generati in ordine da i a j)

/*
  AI: 
  AF: Restituisce la lista degli interi nell'intervallo da i a j
      (generando i nodi in ordine da i a j)
*/
node *buildlis_int (int i, int j)
{
   return buildlis_int_rt (i, j, NULL);
}

/*
  AI: acc contiene una lista L
  AF: Restituisce la lista ottenuta aggiungento in coda alla lista acc
      gli interi nell'intervallo da i a j
*/
node *buildlis_int_rt (int i, int j, node *acc)
{
   if (i > j) 
      return acc;
   else
   {
      node *p = newnode();
      p->data = i;
      p->next = NULL;
      return buildlis_int_rt (i+1 ,j, 
                              << LISTA OTTENUTA INSERENDO p IN CODA AD acc >>)
   }
}

Lo pseudo-codice

<< LISTA OTTENUTA INSERENDO p IN CODA AD acc >>)

puo' essere raffinato in vari modi. Il modo piu' semplice e' il seguente:

append(acc,p);

dove "append e' la funzione:

/*
  AI: lis1 contiene una lista L1, lis2 contiene una lista L2
  AF: Restituisce la lista ottenuta aggiungento in coda alla lista L1
      la lista L2 (non vengono creati nuovi nodi)
*/
node *append (node *lis1, node *lis2)
{
   if (lis1 == NULL) return lis2;

   node *q = lis1;
   while (q->next != NULL) 
      q = q->next;

   q->next = lis2;

   return lis1;
}

Tuttavia, siccome la funzione "append" ha complessita' in tempo lineare nella lunghezza della lista acc, la funzione "buildlis_int" risultante avrebbe complessita' quadratica nella lunghezza della lista prodotta. Questo non e' accettabile. Per questo motivo proponiamo una nuova versione della funzione, che usa come parametro acc una struttura (che chiameremo "list") che contiene un puntatore al primo nodo e un puntatore all'ultimo nodo della lista che "accumula" il risultato.

Funzione ricorsiva di coda (versione 2)

typed struct {
         node *first;
         node *tail;
      } list;

/*
  AI: 
  AF: Restituisce la lista degli interi nell'intervallo da i a j
      (generando i nodi in ordine da i a j)
*/
node *buildlis_int (int i, int j)
{
   list acc = {NULL, NULL};

   return buildlis_int_rt (i, j, acc);
}

/*
  AI: acc.head contiene una lista L,
      acc.tail punta all'ultimo nodo di L
  AF: Restituisce la lista ottenuta aggiungento in coda alla lista L
      gli interi nell'intervallo da i a j
*/
node *buildlis_int_rt (int i, int j, list acc)
{
   if (i > j) 
      return acc.head;
   else
   {
      node *p = newnode();
      p->data = i;
      p->next = NULL;
      if (acc.head == NULL)
         acc.head = p;
      else 
         acc.tail->next = p;
      acc.tail = p;
             
      return buildlis_int_rt (i+1 ,j, acc)
   }
}

La funzione cosi' ottenuta ha complessita' lineare nella lunghezza della lista generata.

Un possibile miglioramento della funzione puo' essere ottenuto passando il parametro acc per referenza (nelle chiamate ricorsive, invece di copiare la struttura, si copierebbe solo il suo indirizzo). Nel paragrafo succesivo desciveremo un'altra possibilita'.

Funzione ricorsiva di coda (versione 3)

La seguente funzione e' una piccola variante della funzione precedente, che tratta separatamente il caso in cui occorre generare una lista vuota.

typed struct {
         node *first;
         node *tail;
      } list;

/*
  AI: 
  AF: Restituisce la lista degli interi nell'intervallo da i a j
      (generando i nodi in ordine da i a j)
*/
node *buildlis_int (int i, int j)
{
   if (i > j) return NULL;

   list acc;
   acc.head = newnode();
   acc.tail = acc.head;
   acc.head->data = i;
   acc.head->next = NULL;

   return buildlis_int_rt (i+1, j, acc);
}

/*
  AI: acc.head contiene una lista non vuota L,
      acc.tail punta all'ultimo nodo di L
  AF: Restituisce la lista ottenuta aggiungento in coda alla lista L
      gli interi nell'intervallo da i a j
*/
node *buildlis_int_rt (int i, int j, list acc)
{
   if (i > j) 
      return acc.head;
   else
   {
      acc.tail->next = newnode();
      acc.tail = acc.tail->next;
      acc.tail->data = i;
      acc.tail->next = NULL;
      return buildlis_int_rt (i+1 ,j, acc)
    }
}

Funzione ricorsiva di coda (versione 4)

La seguente funzione e' un'ulteriore piccola variante della funzione precedente, che evita di usare la struttura "list".

/*
  AI: 
  AF: Restituisce la lista degli interi nell'intervallo da i a j
      (generando i nodi in ordine da i a j)
*/
node *buildlis_int (int i, int j)
{
   if (i > j) return NULL;

   node *head = newnode();
   head->data = i;
   head->next = NULL;
   buildlis_int_rt (i+1, j, head);

   return head;
}

/*
  AI: tail punta all'ultimo nodo di una lista non vuota L
  AF: Gli interi nell'intervallo da i a j 
      sono stati aggiunti in coda alla lista L
*/
void buildlis_int_rt (int i, int j, node *tail)
{
   if (i <= j) 
   {
      tail->next = newnode();
      tail = tail->next;
      tail->data = i;
      tail->next = NULL;
      buildlis_int_rt (i+1 ,j, tail)
    }
}

Funzione iterativa (ottenuta dalla versione 4)

La funzione "buildlis_int" rimane come prima. Applicando la trasformazione alla funzione "buildlis_aux" si ottiene la funzione:

/*
  AI: tail punta all'ultimo nodo di una lista non vuota L
  AF: Gli interi nell'intervallo da i a j 
      sono stati aggiunti in coda alla lista L
*/
void buildlis_int_it (int i, int j, node *tail)
{
   while (i <= j) 
   {
      tail->next = newnode();
      tail = tail->next;
      tail->data = i;
      tail->next = NULL;
    }
}

Ora e' possibile migliorare il codice, compattando le funzioni "buillis_int" e "buildlis_int_it" in un'unica funzione iterativa.

/*
  AI: 
  AF: Restituisce la lista degli interi nell'intervallo da i a j
      (generando i nodi in ordine da i a j)
*/
node *buildlis_int (int i, int j)
{
   if (i > j) return NULL;

   node *head = newnode();
   head->data = i;
   node *tail = head;
   i++;
   
   while (i <= j) 
   {
      tail->next = newnode();
      tail = tail->next;
      tail->data = i;
    }

   tail->next = NULL;
   return head;
}

Liste doppiamente linkate e altre varianti delle liste linkate

Liste doppiamente linkate

Le liste doppiamente linkate sono liste linkate in cui ogni nodo contiene, oltre al puntatore al nodo successivo, anche un puntatore al nodo precedente.

typedef struct nod2 {
           int data;
           struct nod2 *next;
           struct nod2 *prev;
        } node2;

Una variante belle liste doppiamente linkate sono le liste doppiamente linkate circolari: il campo prev del primo nodo punta all'ultimo nodo, e il campo next dell'ultimo nodo punta al primo nodo (per capitre quando si e' arrivati alla "fine" della lista si usa il puntatore al primo nodo al posto di NULL).

Liste con nodo di testa fittizio

L'inserimento/cancellazione in testa alla lista (operazione sul primo nodo della lista) richiede codice diverso da quello per gestire l'inserimento/cancellazione su altri nodi. Per ovviare a questo incoveniente si puo' decidere di lasciare sempre un nodo "vuoto" in testa alla lista: tale nodo non sara' usato per contenere informazioni. Questa tecnica introduce una sottile distinzione: data una variabile:

node *l;

si ha che (in base alla definizione data in precedenza) l contiene la lista vuota quando punta ad un nodo il cui campo next vale NULL. Se l vale NULL, allora l non contiene una lista!!!

La tecnica del nodo di testa fittizio puo' essere applicata sia alle liste linkate semplici che alle liste doppiamente linkate (cirolari e non).

Liste che contengono il numero dei nodi, e altre informazioni

In numerose applicazioni puo' essere utile conoscere il numero dei nodi contenuti in una lista. Si puo' pensare allora di introdurre una dichiarazione:

typedef struct {
           int length;
           node first;
        } lista;

Data una variabile:

list *l;

si ha che (in base alla definizione data in precedenza) l contiene la lista vuota quando: il campo length contiene 0 e il campo length contiene NULL.

Se, oltre al numero dei nodi, si vuole mantenere anche un puntatore all'ultimo nodo, si puo' dichiarare lista nel seguente modo:

typedef struct {
           int length;
           node first;
           node last;
        } lista;

Al solito le varie tecniche si possono combinare. Ad esempio: il nodo first potrebbe puntare ad una sequenza di nodi in cui c'e' un nodo di testa fittizio...

COSA SI DEVE LEGGERE

[NOTE1: pag. 39-40]
[NOTE1: pag. 30-32]
[KRUSE: pag.197, dall'inizio fino alla figura 5.3 inclusa]

ESERCIZI DA SVOLGERE

Simulare l'esecuzione delle funzioni sviluppate in precedenza. In caso di dubbi non esitate a consultare il docente.
ATTENZIONE: l'esercizio che segue e' molto importante, in caso di dubbi non esitate a consultare il docente.
In generale tutte le funzioni ricorsive che operano su array presentate in [NOTE1: pag. 38-40] possono essere riscritte come funzioni ricorsive che operano su un intervallo a[first..last] dell'array. Ad esempio la funzione "palind_rn" in [NOTE1:pag. 39] puo' essere riscritta secondo la seguente specifica:
```
/*
  AI: first e last sono indici validi per a
  AF: Restituisce:
      1 se a[first..last] contiene una sequenza palindroma di interi:
      0 altrimenti
*/
int isPalind_rn (int a[], int first, int last)
```
Dopo aver scritto tale funzione come una funzione ricorsiva lineare:
1. SE LA FUNZIONE NON E' GIA' RICORSIVA DI CODA, trasformarla in una funzione ricorsiva di coda in cui il parametro aggiuntivo "acc" e' passato per valore (seguire lo schema illustrato a lezione e in [NOTE1:pag.35]),
2. SE LA FUNZIONE NON E' GIA' RICORSIVA DI CODA, trasformarla in una funzione ricorsiva di coda in cui il parametro aggiuntivo "acc" e' passato per referenza (seguire lo schema illustrato a lezione),
3. trasformare le funzioni ricorsive di coda ottenute ai passi precedenti in funzioni iterative (seguire lo schema illustrato a lezione e in [NOTE1:pag.36]).
L'esercizio descitto al punto precedente per la funzione "palind_rn" puo' essere applicato a tutte le funzioni ricorsive che operano su array presentate in [NOTE1: pag. 38-40]. Ripetere l'esercizio per alcune di queste funzioni.

[Ferruccio Damiani - DIDATTICA] [Corsi di Studi in Informatica]


	Last update: Feb 25, 2002