Lezione di Mercoledi' 6/02/02 - ultimo aggiornamento: 7/02/02

Ancora liste linkate.

CHE COSA E' STATO FATTO A LEZIONE

Funzioni che operano su piu' di una lista

Altra versione della funzione "duplist" in [NOTE1:pag. 20].

/*
  AI: "l" e' una liste di interi L
  AF: Restituisce una copia di L (ovvero una lista i cui nodi contengono gli 
      stessi valori del campo "data" presenti in L)
*/
node *duplist1 (node *l)
{

    if (l==NULL) return NULL;

    node *head = newnode();
    node *tail = head;
    head->data = l->data;
    l = l->next;

    /* 
       IC:  la lista "head" contiene copia dei i nodi di L
            dal primo fino al nodo puntato da "l" (escluso)
    */
    while (l!=NULL)
    {
        tail->next = newnode();
        tail = tail->next;
        tail->data = l->data;
        l = l->next;
    }

    tail->next = NULL;
    return head;   

Altra versione della funzione "equallis" in [NOTE1:pag. 22].

/*
  AI: "l1" e "l2" sono due liste di interi L1 e L2
  AF: Restituisce:
      -  1 se "l1" e "l2" sono uguali (elemento per elemento)
      -  0 altrimenti
*/
int equallis1 (node *l1, node *l2)
{
    /* 
       IC:  i nodi di L1 e L2 sono uguali dai primi nodi fino ai nodi puntati
            da "l1" e "l2" (esclusi)
    */
    while ((l1!=NULL) && (l2!=NULL) && (l1->data==l2->data))
    {
        l1=l1->next;
        l2=l2->next;
    }

    return ((l1==NULL) && (l2==NULL));   

COSA SI DEVE LEGGERE

• [NOTE1: pag. 20-22]

ESERCIZI DA SVOLGERE

• Simulare l'esecuzione delle funzioni sviluppate in precedenza.
• Sviluppare una funzione

  node *buildmergelis (node *l1, node *l2)
  

  che date due liste ordinate L1 e L2 (possibilmente con nodi duplicati) costruisce una nuova lista ordinata che contiene le copie di tutti i nodi di L1 e L2 (NOTA: i duplicati sono inseriti nello stesso ordine in cui compaiono, e i nodi in L1 precedono quelli in L2).
  Ad esempio, date:

  L1: 1 -> 5 -> 6 -> 6' -> 8
  L2: 0 -> 1' -> 3 -> 6'' - 7
  

  restituisce:

  0 -> 1 -> 1' -> 3 -> 5 -> 6 -> 6' -> 6'' -> 7 -> 8
  

  e L1 e L2 sono inalterate.
• Sviluppare una funzione

  node *mergelis (node **l1, node **l2)
  

  che date due liste ordinate L1 e L2 (possibilmente con nodi duplicati), PASSATE PER REFERENZA, "distrugge" L1 e L2 e restituisce (senza allocare nuovi nodi, e limitandosi a copiare i link) una lista ordinata che contiene i nodi di L1 e L2 (NOTA: i duplicati sono inseriti nello stesso ordine in cui compaiono, e i nodi in L1 precedono quelli in L2).
  Ad esempio, date:

  L1: 1 -> 5 -> 6 -> 6' -> 8
  L2: 0 -> 1' -> 3 -> 6'' - 7
  

  restituisce:

  0 -> 1 -> 1' -> 3 -> 5 -> 6 -> 6' -> 6'' -> 7 -> 8
  

  e dopo l'esecuzione della funzione L1 e L2 sono liste vuote.
• Sviluppare una funzione

  void bubbleSort (node **l)
  

  che (senza allocare nuovi nodi, e limitandosi a copiare i link) ordina la lista che riceve come parametro (PASSATO PER REFERENZA) utilizzando la metodologia di ordinamento bubble sort (che a Programmazione I avete visto usare sugli array).
• Sviluppare una funzione

  void insertionSort (node **l)
  

  che (senza allocare nuovi nodi, e limitandosi a copiare i link) ordina la lista che riceve come parametro (PASSATO PER REFERENZA) utilizzando la metodologia di ordinamento insertion sort (che a Programmazione I avete visto usare sugli array).