Lezione di Mercoledi' 30/01/02
-
ultimo aggiornamento: 31/01/02
Liste linkate: creazione, e ancora funzioni di visita.
CHE COSA E' STATO FATTO A LEZIONE
Creazione di una lista
Creazione di una lista di interi leggendo gli interi da terminale
(IN DUE VERSIONI: lista restituita come valore della funzione E
lista passata come parametro per referenza).
Ulteriore generalizzazione della visita (degli elementi) di una lista
Il seguente schema generalizza ulteriormente gli schemi
presentati nella precedente lezione
(al solito, 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)
&&
(<< CONDIZIONE CHE COINVOLGE lis->data
E EVENTUALI PARAMETRI E VARIABILI LOCALI >>))
{ << 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:
-
Restituire un puntatore al primo nodo di una lista di interi
che contiene l'intero x (parametro della funzione).
-
Prima versione
Specializzazione "meccanica" dello schema.
/*
AI: "lis" e' il puntatore ad una lista L
AF: restituisce un puntatore al primo nodo di L che contiene x
(e NULL se la lista non contiene x).
*/
node* find0 (node *lis, int x)
{
int trovato = 0;
node *q = NULL;
while ((lis!=NULL) && (!trovato))
{
if (lis->data == x)
{
trovato = 1;
q=lis;
}
lis=lis->next;
}
return q;
}
-
Seconda versione
La versione precedente puo' essere migliorata eliminando sia "q"
che "trovato".
/*
AI: "lis" e' il puntatore ad una lista L
AF: restituisce un puntatore al primo nodo di L che contiene x
(e NULL se la lista non contiene x).
*/
node* find1 (node *lis, int x)
{
while (lis!=NULL)
{
if (lis->data == x)
return lis;
lis=lis->next;
}
return NULL;
}
-
Terza versione
E' ancora possibile introdurre un miglioramento
/*
AI: "lis" e' il puntatore ad una lista L
AF: restituisce un puntatore al primo nodo di L che contiene x
(e NULL se la lista non contiene x).
*/
node* find2 (node *lis, int x)
{
while ((lis!=NULL) && (lis->data != x))
lis=lis->next;
return lis;
}
OSSERVAZIONE:
quando si scrive una function non si deve pensare di scrivere subito
("al primo colpo") la versione migliore possibile.
Di solito si procede per passi.
-
Si scrive una prima versione che (come nell'esempio
precedente) puo' essere ottenuta specializzando uno "schema generale".
La correttezza di tale versione sara' facile da dimostrare
(in quanto derivabile da quella dello schema generale).
-
Poi si cerca di migliorare il codice della funzione
(e questo puo' essere fatto in piu passi).
-
Ad un certo punto si potrebbe anche individuare una soluzione
completamente diversa (che non ricade nello schema generale da cui si
era partiti), magari piu' efficiente.
Con l'esperianza si potranno saltare alcuni passi (magari per funzioni
semplici che risolvono problemi simili ad altri
che si sono gia' incontrati).
Si tenga comunque sempre presente che procedere per passi
aiuta a non commettere errori.
COSA SI DEVE LEGGERE
-
[NOTE1: pag. 8-13, e la prima funzione di pag. 14]
ESERCIZI DA SVOLGERE
-
Simulare l'esecuzione delle funzioni
"find0", "find1", e "find2" sviluppate in precedenza
per i seguenti valori dei parametri:
-
*lis = (2,4,6,8)
x = 6
-
*lis = (2,4,6,8)
x = 7
-
Scrivere gli invarianti di ciclo per le funzioni
"find0", "find1", e "find2" sviluppate in precedenza.
-
Considerate il codice della funzione "find" in [NOTE1: pag. 11].
Tale codice rientra nello schema generale descritto in precedenza?
|