Lezione di Lunedi' 28/01/02 - ultimo aggiornamento: 31/01/02

Liste linkate: introduzione, funzioni di visita.

CHE COSA E' STATO FATTO A LEZIONE

Dichiarazioni di tipo

typedef struct nod
        { int data;
          struct nod *next;
        } node;

Stampa (degli elementi) di una lista

void printlis(node *lis)
{
   while (lis!=NULL)
   {  printf("%d\n",lis->data);
      lis=lis->next;
   }
}

Visita (degli elementi) di una lista

Dalla funzione precedente e' possibile ricavare uno "schema generale" per funzioni che "visitano la lista" (ovvero la percorrono dall'inizio alla fine) facento una determiata operazione su ogni nodo.

void visit(node *lis)
{
   << EVENTUALI DICHIARAZIONI DI VARIABILI LOCALI E INIZIALIZZAZIONI >>
   while (lis!=NULL)
   { << VISITA IL NODO PUNTATO DA lis, 
        EFFETTUANDO OPERAZIONI SU lis->data 
                    E SULLE EVENTUALI VARIABILI LOCALI >>
      lis=lis->next;
   }
}

Ad esempio lo schema di funzione precedente puo' essere specializzato come segue:

• Stampa degli elementi pari di una lista di interi (ovvero: degli elementi in cui il campo data contiene un numero pari).
• Stampa degli elementi in posizione pari di una lista di interi (il primo elemento ha posizione 1 (quindi dispari), il secondo elemento ha posizione 2 (quindi pari), e cosi' via...)

Ancora visita (degli elementi) di una lista

Lo schema precedente puo' essere ulteriormente generalizzato come segue (si noti che, quando << TIPO DEL RISULTATO >> = void, il return finale deve essere omesso).

<< TIPO DEL RISULTATO >> visit(node *lis, << EVENTUALI ALTRI PARAMETRI >>)
{
   << EVENTUALI DICHIARAZIONI DI VARIABILI LOCALI E INIZIALIZZAZIONI >>
   while (lis!=NULL)
   { << VISITA IL NODO PUNTATO DA lis, 
        EFFETTUANDO OPERAZIONI SU lis->data 
                    E SUGLI EVENTUALI PARAMETRI E VARIABILI LOCALI >>
      lis=lis->next;
   }
   return << ESPRESSIONE CHE RAPPRESENTA IL RISULTATO >>
}

Ad esempio, questo nuovo schema di funzione puo' essere specializzato come segue:

• Stampa degli elementi in posizione multipla di m (m parametro della funzione) di una lista di interi.
• Restituire la somma degli elementi di una lista di interi.
• Restituire la somma degli elementi in posizione multipla di m (m parametro della funzione) di una lista di interi .

COSA SI DEVE LEGGERE

• [NOTE1: pag. 4-5]
  ATTENZIONE: se la funzione buildlis a pag. 7 riceve come argomento il numero 0, allora restituisce la lista vuota. Quindi il commento iniziale puo' essere modificato sostituendo "n>0" con "n>=0". L'invariante dovra' invece essere sostituito con:

  /*Invariante:
  
  
    0<=n<=N  e  lis e' la lista dei nodi contenenti n+1..N 
  
    (NOTAZIONE: 
     - N e' il valore di n all'inizio dell'esecuzione della funzione;
     - se i > j allora i..j e' la sequenza vuota.)
  
  */
  

ESERCIZI DA SVOLGERE

• Scrivere le funzioni di "visita specializzata" descritte in precedenza.

SOLUZIONE DI ALCUNI DEGLI ESERCIZI ASSEGNATI

• Stampa degli elementi in posizione pari di una lista di interi (il primo elemento ha posizione 1 (quindi dispari), il secondo elemento ha posizione 2 (quindi pari), e cosi' via...)

  SECIALIZZIAMO IL PRIMO SCHEMA

  /* 
     AI: "lis" e' il puntatore ad una lista L
     AF: gli elementi di L in posizione pari sono stati scritti su terminale
  */
  void printEven (node *lis)
  {
     int position = 1;
     /* IC: "lis" punta al nodo di L in posizione "position"
             (e vale NULL se tale nodo non esiste)
             AND
             gli elementi di L in posizione pari e < "position"
             sono stati stampati
     */
     while (lis!=NULL)
     { 
        if ((position % 2) == 0) 
           printf("%d\n",lis->data);
        position++;
        lis=lis->next;
     }
  }
  

• Restituire la somma degli elementi in posizione multipla di m (m parametro della funzione) di una lista di interi .

  SPECIALIZZIAMO IL SECONDO SCHEMA

  /* 
     AI: "lis" e' il puntatore ad una lista L
     AF: restituisce la somma degli elementi di L in posizione
         multipla di "m" 
  */
  int sumPosMulti (node *lis, int m)
  {
     int position = 1;
     int sum = 0
     /* IC: "lis" punta al nodo di L in posizione "position"
             (e vale NULL se tale nodo non esiste)
             AND
             "sum" = somma degli elementi di L in posizione 
             multipla di "m" e < "position"
     */
     while (lis!=NULL)
     { 
        if ((position % m) == 0) 
           sum+=lis->data;
        position++;
        lis=lis->next;
     }
     return sum;
  }