
DIPARTIMENTO DI INFORMATICA Università di Torino

ESERCIZI (ALCUNI DEI QUALI CON SOLUZIONE) - ultimo aggiornamento 06/03/02

Attenzione si consiglia di provare a fare questi esercizi e di confrontare in seguito la propria soluzione con l'eventuale soluzione fornita dal docente.

Esercizi sulle liste linkate.

ELENCO DEGLI ESERCIZI

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 il "merge di L1 e L2". Cioe' 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 il merge di L1 e L2. Cioe' contiene tutti i nodi che erano in 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 splitlis (node **l, node **l2, node **l2)
```
che data una lista L PASSATA PER REFERENZA, e due liste inizialmente vuote PASSATE PER REFERENZA, "distrugge" L e restituisce (senza allocare nuovi nodi, e limitandosi a copiare i link) nel secondo e nel terzo parametro due liste L1 e L2 che contengono rispettivamente i nodi di L in posizione dispari (L1) e i nodi di L in posizione pari (L2). (NOTA: per convenzione il primo nodo di L1 e' in posizione 1, quindi in posizione dispari)
Ad esempio, data:
```
L: 0 -> 5 -> 4 -> 3 -> 6 -> 7 -> 2
```
restituisce:
```
L1: 0 -> 4 -> 6 -> 2
L2: 5 -> 3 -> 7
```
Sviluppare una funzione
```
void splitlisN (int n, node **l, node **l2, node **l2)
```
che dato un intero n >= 2, una lista L contenente esattamente n nodi PASSATA PER REFERENZA, e due liste inizialmente vuote PASSATE PER REFERENZA, "distrugge" L e restituisce (senza allocare nuovi nodi, e limitandosi a copiare i link) nel secondo e nel terzo parametro due liste L1 e L2 che contengono rispettivamente i nodi di L dal primo all'(n/2)-esimo (L1) e i nodi di L dall'(n/2 + 1)-esimo all'ultimo (L2)
Ad esempio, data:
```
L: 0 -> 5 -> 4 -> 3 -> 6 -> 7 -> 2
di lunghezza n=7
```
restituisce:
```
L1: 0 -> 5 -> 4 
L2: 3 -> 6 -> 7 -> 2
```

SOLUZIONE (DI ALCUNI) DEGLI ESERCIZI

Soluzione all'esercizio 1

Prima versione

ATTENZIONE: la soluzione messa on-line il 14/02/02 (che ora ho tolto) era sbagliata: se una sola delle due liste era vuota il primo if deferenziava un puntatore a NULL.
La seguente soluzione e' la versione corretta (si noti che la gestione dell'inserimento del primo nodo nella lista risultato richiede di considerare 4 casi distinti, per questo motivo e' preferibile la "Seconda versione" della soluzione).

/*
  AI: l1 e l2 sono due liste di interi L1 e L2 ordinate (in ordine cresente)
  AF: Restituisce il merge di L1 e L2 (L1 e L2 non sono modificate)
*/
node *buildmergelis (node *l1, node *l2)
{

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

    node *head = newnode();
    node *tail = head;
    
    if ((l1!=NULL) && (l2==NULL)) 
       {
          tail->data = l1->data;
          l1 = l1->next;
       }
    else if ((l2!=NULL) && (l1==NULL)) 
       {
          tail->data = l2->data;
          l2 = l2->next;
       }
    else if (l1->data <= l2->data)
       {
          tail->data = l1->data;
          l1 = l1->next;
       }
    else
       {
          tail->data = l2->data;
          l2 = l2->next;
       }

    /* 
       IC:  la lista head NON E' VUOTA e 
            contiene il merge (delle copie)  
               dei nodi di L1 dal primo fino al nodo puntato da l1 (escluso)
               e
               dei nodi di L2 dal primo fino al nodo puntato da l2 (escluso)
            tail contiene il puntatore all'ultimo nodo della lista head
             
    */
    while ((l1 != NULL) && (l2 != NULL))
    {
       tail->next = newnode();
       tail = tail->next;
       if (l1->data <= l2->data)
          {
             tail->data = l1->data;
             l1 = l1->next;
          }
       else
          {
             tail->data = l2->data;
             l2 = l2->next;
          }
    } 

    while (l1 != NULL)
    {
       tail->next = newnode();
       tail = tail->next;
       tail->data = l1->data;
       l1 = l1->next;
    }
    
    while (l2 != NULL)
    {
       tail->next = newnode();
       tail = tail->next;
       tail->data = l2->data;
       l2 = l2->next;
    }

    tail->next = NULL;
    return head;   
}

La complessita' in tempo di questa funzione e' lineare nella somma delle lunghezze di L1 e L2.
La giustificazione e' identica a quella data per la "Seconda versione" (vedi paragrafo successivo).

Seconda versione

ATTENZIONE: la soluzione messa on-line il 18/02/02 (che ora ho tolto) era sbagliata: se una sola delle due liste era vuota nel secondo o nel terzo while venivsa dfeferenziato un puntatore a NULL (il puntatore tail).
La seguente soluzione e' la versione corretta:

/*
  AI: l1 e l2 sono due liste di interi L1 e L2 ordinate (in ordine cresente)
  AF: Restituisce il merge di L1 e L2 (L1 e L2 non sono modificate)
*/
node *buildmergelis (node *l1, node *l2)
{
    node *head = NULL;
    node *tail = NULL;
    node *temp = NULL;

    /* 
       IC:  la lista head, 
            contiene il merge (delle copie)  
               dei nodi di L1 dal primo fino al nodo puntato da l1 (escluso)
               e
               dei nodi di L2 dal primo fino al nodo puntato da l2 (escluso)
            tail contiene il puntatore all'ultimo nodo della lista head
             
    */
    while ((l1 != NULL) && (l2 != NULL))
    {
       temp = newnode();
       temp->next = NULL;

       if (l1->data <= l2->data)
          {
             if (head == NULL) head = temp; 
             else tail->next = temp;

             tail = temp;  
             tail->data = l1->data;
             l1 = l1->next;
          }
       else
          {
             if (head == NULL) head = temp; 
             else tail->next = temp; 

             tail = temp; 
             tail->data = l2->data;
             l2 = l2->next;
          }
    } 

    while (l1 != NULL)
    {
       temp = newnode();

       if (head == NULL) head = temp; 
       else tail->next = temp; 

       tail = temp; 
       tail->data = l1->data;
       tail->next = NULL;

       l1 = l1->next;
    }
    
    while (l2 != NULL)
    {
       temp = newnode();

       if (head == NULL) head = temp; 
       else tail->next = temp; 

       tail = temp; 
       tail->data = l2->data;
       tail->next = NULL;

       l2 = l2->next;
    }

    return head;   
}

La complessita' in tempo di questa funzione e' lineare nella somma delle lunghezze di L1 e L2.
Giustificazione:

Se L1 e L2 sono vuote si termina subito.
Ad ogni iterazione del primo ciclo while si passa ad un nodo successivo di L1 o di L2. (Quando si esce dal ciclo almeno una delle due liste e' stata scandita completamente. Quindi alpiu' uno solo dei due cicli che seguono fara' almeno un'iterazione.)
Ad ogni iterazione del secondo ciclo while si passa ad un nodo successivo di L1.
Ad ogni iterazione del terzo ciclo while si passa ad un nodo successivo di L2.

Soluzione all'esercizio 2

Prima versione

ATTENZIONE: la soluzione messa on-line il 14/02/02 (che ora ho tolto) era sbagliata: se una sola delle due liste era vuota il primo if deferenziava un puntatore a NULL.
La seguente soluzione e' la versione corretta (si noti che la gestione dell'inserimento del primo nodo nella lista risultato richiede di considerare 4 casi distinti, per questo motivo sono preferibili la "Seconda versione" o la "Terza versione" della soluzione).

/*
  AI: *pl1 e *pl2 sono due liste di interi L1 e L2 ordinate (in ordine 
      cresente)
  AF: Restituisce il merge di L1 e L2 (L1 e L2 sono distrutte
      e *pl1 e *pl2 contengono NULL)
*/
node *mergelis (node **pl1, node **pl2)
{
    if ((*pl1==NULL) && (*pl2==NULL) return NULL;

    node *head = NULL;
    node *tail = NULL;

    if ((*pl1!=NULL) && (*pl2==NULL) 
       {
          head = *pl1;
          *pl1 = (*pl1)->next;
       }
    else if ((*pl1==NULL) && (*pl2!=NULL) 
       {
          head = *pl2;
          *pl2 = (*pl2)->next;
       }
    else if ((*pl1)->data <= ((*pl2)->data)
       {
          head = *pl1;
          *pl1 = (*pl1)->next;
       }
    else
       {
          head = *pl2;
          *pl2 = (*pl2)->next;
       }

    tail = head;

    /* 
       IC:  la lista head NON E' VUOTA e 
            contiene il merge 
               dei nodi di L1 dal primo fino al nodo puntato da *pl1 (escluso)
               e
               dei nodi di L2 dal primo fino al nodo puntato da *pl2 (escluso)
            tail contiene il puntatore all'ultimo nodo della lista head
    */
    while ((*pl1 != NULL) && (*pl2 != NULL))
    {

       if ((*pl1)->data <= ((*pl2)->data)
          {
             tail->next = *pl1;
             *pl1 = (*pl1)->next;
          }
       else
          {
             tail->next = *pl2;
             *pl2 = (*pl2)->next;
          }

       tail = tail->next;
    } 

    while (*pl1 != NULL)
    {
       tail->next = *pl1;
       *pl1 = (*pl1)->next;
       tail = tail->next;
    }
    
    while (*pl2 != NULL)
    {
       tail->next = *pl2;
       *pl2 = (*pl2)->next;
       tail = tail->next;
    }

    tail->next = NULL;
    return head;   
}

La complessita' in tempo di questa funzione e' lineare nella somma delle lunghezze di L1 e L2.
La giustificazione e' identica a quella data per la funzione precedente.

Seconda versione

ATTENZIONE: la soluzione messa on-line il 18/02/02 (che ora ho tolto) era sbagliata: se una sola delle due liste era vuota nel secondo nel terzo while veniva deferenziato un puntatore a NULL (il puntatore tsail).
La seguente soluzione e' la versione corretta:

/*
  AI: *pl1 e *pl2 sono due liste di interi L1 e L2 ordinate (in ordine 
      cresente)
  AF: Restituisce il merge di L1 e L2 (L1 e L2 non distrutte
      e *pl1 e *pl2 contengono NULL)
*/
node *mergelis (node **pl1, node **pl2)
{
    node *head = NULL;
    node *tail = NULL;

    /* 
       IC:  la lista head, 
            contiene il merge 
               dei nodi di L1 dal primo fino al nodo puntato da *pl1 (escluso)
               e
               dei nodi di L2 dal primo fino al nodo puntato da *pl2 (escluso)
            tail contiene il puntatore all'ultimo nodo della lista head
    */
    while ((*pl1 != NULL) && (*pl2 != NULL))
    {
       if ((*pl1)->data <= (*pl2)->data)
          {
             if (head == NULL) head = *pl1;
             else tail->next = *pl1;

             tail = *pl1;  
             *pl1 = (*pl1)->next;
          }
       else
          {
             if (head == NULL) head = *pl2; 
             else tail->next = *pl2;

             tail =*pl2;  
             *pl2 = (*pl2)->next;
          }
    } 

    while (*pl1 != NULL)
    {
       if (head == NULL) head = *pl21 
       else tail->next = *pl1;

       tail = *pl1;  
       *pl1 = (*pl1)->next;
    }
    
    while (l2 != NULL)
    {
       if (head == NULL) head = *pl2; 
       else tail->next = *pl2;

       tail = *pl2;  
       *pl2 = (*pl2)->next;
    }

    return head;

La giustificazione e' identica a quella data per la funzione precedente.

Terza versione (FARE MOLTA ATTENZIONE)

/*
  AI: *pl1 e *pl2 sono due liste di interi L1 e L2 ordinate (in ordine 
      cresente)
  AF: Restituisce il merge di L1 e L2 (L1 e L2 non sono distrutte
      e *pl1 e *pl2 contengono NULL)
*/
node *mergelis (node **l1, node **l2)
{
    node *head = NULL;
    node **pend = &head;

    /* 
       IC:  la lista head, 
            contiene il merge 
               dei nodi di L1 dal primo fino al nodo puntato da *pl1 (escluso)
               e
               dei nodi di L2 dal primo fino al nodo puntato da *pl2 (escluso)
            pend contiene l'indirizzo della locazione che memorizza
                  il puntatore (di valore NULL) che termina la lista head
                  (ovvero: l'indirizzo di head o l'indirizzo del campo
                   next del penultimo nodo della lista head)
             
    */
    while ((*pl1 != NULL) && (*pl2 != NULL))
    {
       if ((*pl1)->data <= ((*pl2)->data)
          {
             *pend = *pl1;
             pend = &((*pl1)->next);
             *pl1 = (*pl1)->next;
          }
       else
          {
             *pend = *pl2;
             pend = &((*pl2)->next);
             *pl2 = (*pl2)->next;
          }
    } 

    while (*pl1 != NULL)
    {
       *pend = *pl1;
       pend = &((*pl1)->next);
       *pl1 = (*pl1)->next;
    }
    
    while (*pl2 != NULL)
    {
       *pend = *pl2;
       pend = &((*pl2)->next);
       *pl1 = (*pl2)->next;
    }

    *pend = NULL;
    return head;   
}

Notate che se la funzione avesse restituito il risultato in un terzo parametro, ovvero se avesse avuto prototipo:

/*
  AI: *pl1 e *pl2 sono due liste di interi L1 e L2 ordinate (in ordine 
      cresente)
  AF: Restituisce il merge di L1 e L2 (L1 e L2 sono distrutte
      e *pl1 e *pl2 contengono NULL) nel parametro 
     (PASSATO PER REFERENZA) *pl3
*/
void mergelisp (node **pl1, node **pl2, **pl3)

si sarebbe potuto evitare dichiarare la variabile head, e usare *pl3 al posto di head.

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


	Last update: Mar 06, 2002