Uno dei vantaggi di usare una lista, invece di un array, sta nel fatto che la lista non va dimensionata staticamente, ovvero non e` necessario stabilire a priori il numero massimo di elementi che puo` contenere (NOTA1: ovviamente il limite a tale numero viene implicitamente dato dai limiti fisici della heap, che e` la parte di memoria in cui vengono memorizzate le liste; NOTA2: in alcuni linguaggi, il trattamento degli array non e` cosi' rigido come in Pascal...).
Uno dei vantaggi di usare un array e` che questo ci permette di accedere direttamente ai suoi elementi, mentre una lista ne consente solo un accesso sequenziale (vedere la funzione 'el_pos' piu' avanti).
La struttura dati "ideale" quindi non esiste, e la scelta di una struttura piuttosto che un'altra dipende dall'uso che se ne vuole fare!
Rivediamo ora gli esempi presentati a lezione. Consideriamo il tipo introdotto da Giovannetti:
type elemtype = integer;
list = ^node;
node = record
elem:elemtype;
next:list
end;
function length(l:list):integer;
{AF: restituisce il numero di elementi contenuti nella lista (puntata da) 'l'}
var i:integer;
begin
i:=0; {se l=nil, allora il numero degli elementi e` 0}
while l<>nil do
begin
i:=i+1;
l:=l^.next;
end;
length:=i;
end;
Notate che 'l' e` passata per valore, siccome non dobbiamo modificarla. Passarla per referenza, pero', sarebbe un GRAVE ERRORE, poiche' la funzione restituirebbe ancora il corretto numero di elementi, ma avrebbe l'effetto collaterale di assegnare alla lista di partenza, quella che passiamo a 'length' dal main, il valore finale di 'l', il quale e` uguale a nil (a causa delle successive esecuzioni di 'l:=l^.next') e non piu' alla "testa" della lista. Ricordiamo che nel passaggio per riferimento, il parametro attuale passato alla funzione nel main va a coincidere con quello formale.
Questa osservazione ci e` utile perche' ci saranno casi in cui DOVREMO passare la lista per riferimento. La soluzione al problema di cui sopra e`, in generale, l'uso di un puntatore ausiliario che fara` il lavoro di scorrimento della lista al posto di 'l'. Vedremo esempi in proposito...
function el_pos(a:VettInt; p:integer; n:integer):integer;
{AF: restituisce l'elemento del VETTORE 'a' in posizione 'p'}
begin
if 1<=p<=n {controllo che 'p' sia un indice "legale"}
then el_pos:=a[p];
end;
function el_pos(a:list; p:integer):integer;
{AF: restituisce l'elemento della LISTA 'a' in posizione 'p'}
{usa la funzione 'length' definita qui sopra}
var i:integer;
begin
if p<=length(a) {controllo che 'p' sia un indice "legale"}
then
begin
i:=1;
while p>i do {si puo` mettere anche un 'for' da 1 a p-1}
begin
a:=a^.next; i:=i+1;
end;
el_pos:=a^.elem;
end;
end;
Nel primo caso 'a' e` un array, nel secondo 'a' e` una lista: qui potete notare cosa si intendeva piu' sopra quando si diceva che gli elementi di un array sono accessibili direttamente, mentre quelli di una lista no.
function cerca_el(l:list; e:elemtype):bool;
{AF: restituisce TRUE se l'elemento 'e' appartiene alla lista 'l',
FALSE altrimenti}
begin
if (l=nil) then cerca_el:=false {CASO BASE 1}
else if (l^.elem=e) then cerca_el:=true {CASO BASE 2}
else cerca_el:=cerca_el(l^.next, e); {CASO RICORSIVO}
end;
Notate che il caso base "1" si applica sia quando la lista 'l' e` vuota, sia quando la computazione ha esaminato una lista non vuota fino alla fine (ovvero non si e` trovato nessun elemento = a 'e'), nel qual caso la chiamata ricorsiva in questione avra` proprio come parametro 'l=nil', che permette di terminare la serie di chiamate ricorsive. Nel caso ricorsivo, se l'elemento corrente (la testa della lista 'l') e` quello voluto, si sospende la ricerca (ovvero si termina la serie di chiamate ricorsive) e si restituisce TRUE (caso base "2"), altrimenti si procede la ricerca nella coda della lista, puntata da 'l.next'.
function copy(l:list):list
{AF: restituisce una copia della lista 'l'}
{VERSIONE RICORSIVA, VISTA A LEZIONE CON GIOVANNETTI}
begin
if l=nil then copy:=nil {caso base}
else copy:=cons(l^.elem, copy(l^.next)) {caso ricorsivo}
{'cons(e,l)' inserisce l'elemento
'e' in testa alla lista 'l'}
end;
function copy_if(l:list):list
{AF: restituisce in una lista tutti gli elementi della lista l che sono > 3}
begin
if l=nil then copy:=nil {CASO BASE}
else
if (l^.elem>3) then copy:=cons(l^.elem, copy(l^.next)) {CASO RICORSIVO 1}
else copy:=copy(l^.next) {CASO RICORSIVO 2}
end;
La funzione 'copy' e` quella vista a lezione con Giovannetti. La 'copy_if' e` una modifica della funzione precedente che inserisce nella nuova lista solo gli elementi di 'l' che rispettano un certo predicato (nel nostro esempio il predicato e` '>3'). Le due clausole ricorsive seguono esattamente questa spiegazione informale:
- "1": se l'elemento considerato nell'esecuzione corrente soddisfa '>3', allora la 'copy_if' si comporta esattamente come la 'copy', restituendo come risultato una 'cons' che mettera` l'elemento corrente in testa alla lista risultante dalle successive chiamate ricorsive (atte a esaminare la coda della lista corrente, che potrebbe contenere ulteriori elementi da inserire nella lista che stiamo costruendo);
- "2": altrimenti se l'elemento considerato non e` >3, restituisce semplicemente la lista risultante dalle successive chiamate ricorsive (atte a esaminare la coda della lista corrente, che potrebbe contenere ulteriori elementi da inserire nella lista che stiamo costruendo).
PROVATE A SIMULARE QUESTA FUNZIONE A MANO: e` un utile esercizio per arrivare a capire il meccanismo della ricorsione una volta per tutte!
procedure delete(var l:list; e:elemtype);
{AF: cancella dalla lista 'l' l'elemento 'e', se presente nella lista}
{VERSIONE ITERATIVA}
???
Abbiamo poi introdotto la 'delete', senza completarla. Alcune riflessioni ci hanno portato a concludere che 'l' va passata per referenza (perche'?), e che se l'elemento da cancellare e` la testa della lista occorre fare una certa attenzione. Inoltre, non dimenticate le precauzioni da prendere nel caso in cui la lista (che, ricordiamo, e` il puntatore al suo primo elemento) e` passata per referenza. Pensateci...
{versione ricorsiva}
...
if eoln then
begin
l:=nil;
readln; {****}
end
else ...
{versione iterativa}
...
while not eoln do
begin
...
end;
last^.next:=nil;
readln; {****}
end;
end; {end finale della procedura}
Cosa succede se non la si mette?
- Scrivete la versione ricorsiva delle funzioni 'length' e 'el_pos' viste a lezione in versione iterativa e riportate piu' su nella pagina.
- Scrivete la versione iterativa della 'cerca_el' vista a lezione in versione ricorsiva e riportata piu' su nella pagina.
- Modificate la versione iterativa Pascal Standard di 'copy', vista a lezione con Giovannetti, per ottenere una versione iterativa della 'copy_if', vista a lezione in versione ricorsiva e riportata piu' su nella pagina.
- Simulate a mano e fate eseguire al calcolatore la 'copy_if' ricorsiva (vedi sopra).
Soluzioni (Non ancora presenti)