Fondamenti di Informatica Prof. E. Clementini A.A. 2008-09ing.univaq.it/eliseo/dispense algoritmi e...

Fondamenti di Informatica – Prof. E. Clementini

Università degli Studi dell‟Aquila 1

Fondamenti di Informatica

Prof. E. Clementini

Dispensa didattica

A.A. 2008-09

Argomenti:

1. Efficienza dei programmi. La funzione t(n). Modello di costo. Calcolo della t(n) per programmi iterativi. Caso

migliore, caso peggiore, e caso medio. Complessità computazionale. Notazione asintotica

))(( ngO , ))(( ng , ))(( ng . Delimitazioni alla complessità di un problema. Calcolo della

t(n) per programmi ricorsivi. Soluzione dell‟equazione di ricorrenza per il fattoriale e per i

numeri di Fibonacci.

2. Algoritmi di ricerca e ordinamento. Ricerca sequenziale. Ricerca binaria. Inserimento e cancellazione in un array ordinato.

SelectionSort. InsertionSort. Bubblesort. Mergesort. Quicksort: analisi della complessità

nel caso migliore e nel caso peggiore.

3. Tipi di dato astratti. Liste: definizioni, rappresentazione con array, rappresentazione con lista collegata,

rappresentazione con lista collegata bidirezionale, operazioni primitive sulle liste. Pile:

definizioni, rappresentazione con array, rappresentazione con lista collegata, operazioni

primitive sulle pile. Code: definizioni, prima rappresentazione con array, seconda

rappresentazione con array (gestione circolare), rappresentazione con lista collegata,

operazioni primitive sulle code. Alberi: definizioni, alberi n-ari, alberi binari, algoritmi di

visita in profondità e in larghezza. Alberi binari: rappresentazione con puntatori, codifica

delle operazioni primitive. Calcolo della complessità in programmi che fanno uso di tipi

astratti.



3

1 2

4

5

6

7

1. Efficienza dei programmi

Calcolo della t(n)

Calcolo della t(n) per un ciclo for

Numeriamo le istruzioni elementari rispettando lo stesso ordine di esecuzione del diagramma

di flusso. Quindi nell‟esempio seguente l‟incremento della variabile è numerato dopo le

istruzioni interne al ciclo:

for(i=0;i<n;i++)

{

cin>>x;

somma=somma+x;

}

Tabella costo/frequenza:

# istr. costo freq.

1 1 1

2 1 n+1

3 1 n

4 1 n

5 1 n

t(n)=4n+2

Calcolo della t(n) per un doppio ciclo. Due casi:

a) il numero di esecuzioni del ciclo interno non dipende dall‟iterazione del ciclo esterno;

b) il numero di esecuzioni del ciclo interno dipende dall‟iterazione del ciclo esterno.

Caso a)

somma dei valori di una tavola pitagorica:

for (i=1;i<=n;i++)

{

for (j=1;j<=n;j++)

somma=somma+ i*j;

}

1

4

5 2

3



3

1 2

4

5

6

7

# istr. costo freq.

1 1 1

2 1 n+1

3 1 n

4 1 n(n+1)

5 1 2n

6 1 2n

7 1 n

t(n)=3 2n +4n+2

Caso b)

Piramide di numeri:

for (i=1;i<=n;i++)

for (j=1;j<=i;j++)

cout<<j;

Il costo del ciclo interno può essere calcolato determinando la sua frequenza per ogni valore

del contatore esterno i:

per i=1: 11 j , freq. 1

per i=2: 21 j , freq. 2

…

per i=n: nj1 , freq. n

Il totale delle frequenze parziali è n

k

k1

= 2

)1(nn.

Tabella:

# istr. costo freq.

1 1 1

2 1 n+1

3 1 n

4 1 n(n+1)/2+n

5 1 n(n+1)/2

6 1 n(n+1)/2

7 1 n

t(n)= 22

11

2

3 2 nn



Complessità computazionale

Notazione asintotica

Limite asintotico superiore ))(( ngO

))(( ngO = }),()(0,,|)({ 00 nnncgnfncnf

Limite asintotico inferiore ))(( ng

))(( ng = }),()(0,,|)({ 00 nnnfncgncnf

Limite asintotico stretto ))(( ng

))(( ng = }),()()(0,,,|)({ 021021 nnngcnfngcnccnf

Proprietà della notazione asintotica:

- fattore costante: k , )(nf , ))(()( nfnfk

- transitività: ))(()( ngnf , ))(()( nhng ))(()( nhnf

- somma: )()( ngnf = )})(),((max{ ngnf

- prodotto: ))(()( 11 ngnf , ))(()( 22 ngnf )()( 21 nfnf = ))()(( 21 ngng

Istruzione dominante

L‟istruzione dominante è l‟istruzione che viene ripetuta con frequenza maggiore in un

programma. Se riusciamo a calcolare la frequenza e quindi la complessità dell‟istruzione

dominante, conosciamo la complessità di tutto l‟algoritmo.

Delimitazione superiore di un problema

Un problema ha una delimitazione superiore ))(( nfO se esiste almeno un algoritmo che lo

risolve con complessità ))(( nfO .

Delimitazione inferiore di un problema

Un problema ha una delimitazione inferiore ))(( nf se ogni algoritmo che lo risolve ha

complessità almeno ))(( nf .

Soluzione ottima di un problema

Dato un problema con una delimitazione inferiore ))(( nf , una soluzione ottima è un

algoritmo che risolve il problema con complessità ))(( nf .



3

1

Calcolo t(n) di una funzione ricorsiva

Funzione fattoriale

int fatt (int n)

{

if (n==0) return 1;

else return n*fatt(n-1);

}

# istr. costo freq. (n>0) freq. (n=0)

1 1 1 1

2 1 0 1

3 t(n-1) 1 0

Equazione di ricorrenza:

t(n)=t(n-1)+1 per n>0 e t(0)=2

Risolviamo per sostituzione:

t(n-1)=t(n-2)+1

t(n)=t(n-2)+2

t(n-2)=t(n-3)+1

t(n)=t(n-3)+3

…

t(n)=t(0) +n

t(n)=n+2

Numeri di Fibonacci

Un termine della serie di Fibonacci è definito matematicamente come:

0 1f ;

1 1f ;

1 2n n nf f f , 1n .

2



3

1

Soluzione ricorsiva:

int fib(int n)

{

if (n==0 || n==1) return 1;

else return fib(n-1)+fib(n-2);

}

# istr. costo freq. (n>1) freq. (n=0 or n=1)

1 1 1 1

2 1 0 1

3 t(n-1)+t(n-2) 1 0


t(n)=t(n-1)+t(n-2)+1 per n>1 e t(n)=2 per n=0 or n=1

per sostituzione:

t(n-1)=t(n-2)+t(n-3)+1

t(n)= t(n-2)+t(n-3)+1 +t(n-2) +1 = 2 t(n-2) +t(n-3) +2

t(n-2)=t(n-3)+t(n-4)+1

t(n)=2 t(n-3) +2 t(n-4) +2 +t(n-3) +2 = 3 t(n-3)+2t(n-4)+4

t(n-3)=t(n-4)+t(n-5)+1

t(n)=3t(n-4)+3t(n-5)+3+2t(n-4)+4 = 5t(n-4)+3t(n-5) +7

t(n-4)=t(n-5)+t(n-6)+1

t(n)=5t(n-5)+5t(n-6)+5+3t(n-5) +7 = 8t(n-5)+5t(n-6)+12 = 5f t(n-5)+ 4f t(n-6)+ 6f -1

t(n)= 6f t(n-6) + 5f t(n-7) + 7f -1

....

t(n)= 1nf t(1) + 2nf t(0) + nf -1 = 2 1nf +2 2nf + nf -1 = 2( 1nf + 2nf )+ nf -1 = 3 nf -1.

t(n)= 13 nf

La funzione t(n) cresce come i numeri di Fibonacci, quindi è esponenziale. Infatti, si trova

empiricamente che una delimitazione per i numeri di Fibonacci è la seguente:

12 2n

nf

L‟algoritmo iterativo per calcolare i numeri di Fibonacci ha invece costo lineare.

2



2. Algoritmi di ricerca e ordinamento

Ricerca sequenziale

L‟ordinamento dei valori contenuti in un array, in senso crescente o decrescente, è utile per

ritrovare più facilmente i valori in svariate applicazioni. Sono i tempi di calcolo ad essere

inferiori se dobbiamo ritrovare un valore all‟interno di un array ordinato piuttosto che

all‟interno di un array non ordinato. Il problema della ricerca può essere formulato come

segue: “Esiste il valore k all‟interno dell‟array v?”. Per rispondere, in un array non ordinato

possiamo solo adottare un cosiddetto algoritmo di ricerca sequenziale, costituito da un ciclo

che scandisce tutto l‟array. Osserviamo il seguente frammento di codice:

i=0;

trovato=false;

while(i<n && !trovato)

{

if (v[i]==k)

trovato=true;

i++;

}

Come si può vedere, il tempo di esecuzione è più o meno sfavorevole a seconda della

posizione che l‟elemento cercato assume all‟interno dell‟array. Se l‟elemento non dovesse

essere presente, abbiamo dovuto esaminare tutto l‟array per giungere a questa conclusione.

Il caso peggiore corrisponde a trovare l‟elemento in ultima posizione (oppure in modo quasi

equivalente a non trovarlo affatto), mentre il caso migliore corrisponde a trovare l‟elemento in

prima posizione. Il caso medio può essere calcolato con considerazioni statistiche: se

ipotizziamo che il numero di elementi dell‟array n sia uguale al numero di valori possibili, è

lecito ipotizzare che mediamente il valore k si trova a metà array.

# istr. costo freq. (c.p.) freq.

(c.migliore)

freq.

(c.medio)

1 1 1 1 1

2 1 1 1 1

3 1 n+1 2 n/2+1

4 1 n 1 n/2

5 1 1 1 1

6 1 n 1 n/2

Caso peggiore t(n)=3n+4

Caso migliore t(n)=7

Caso medio t(n)=3n/2 + 4

1

2

3

4

5

6



Applicando lo stesso algoritmo ad un array ordinato in senso crescente, possiamo migliorare il

codice aggiungendo un‟ulteriore condizione di uscita quando il valore contenuto nell‟array

supera il valore da cercare:

i=0;

trovato=false;

while(i<n && !trovato && v[i]<=k)

{

if (v[i]==k)

trovato=true;

i++;

}

In questa versione il caso peggiore si verifica quando l‟elemento cercato è in ultima posizione

oppure quando è più grande di tutti i valori dell‟array. Il caso migliore si verifica quando

l‟elemento cercato è più piccolo di tutti i valori dell‟array (in questo caso non si entra per

niente nel ciclo):

# istr. costo freq. (c.p.) freq. (c.m.)

1 1 1 1

2 1 1 1

3 1 n+1 1

4 1 n 0

5 1 1 0

6 1 n 0



Ricerca binaria

In un array ordinato, è possibile applicare un algoritmo molto più efficiente, la cosiddetta

ricerca binaria. In questo algoritmo, si accede all‟elemento di mezzo dell‟array v[med] e si

controlla se esso è maggiore o minore del valore cercato k: se è maggiore, il valore k dovrà

trovarsi nella prima metà dell‟array, altrimenti nella seconda metà. Pertanto dopo un solo

controllo l‟algoritmo ha escluso metà degli elementi. Ripetendo il procedimento sulla metà

interessata, si potrà escludere un altro quarto di array, e così via. Si intuisce che dopo pochi

controlli, si arriva subito alla conclusione. Consideriamo il seguente esempio:

3 7 12 18 25 27 42 50 61 64 72

0

max

1 2 3 4 5 6 7 8 9 10

min med

v



3 4

5

6

8

Il valore di med in questo caso è uguale a 5. Supponiamo che k sia uguale a 10. Poiché v[5] è

maggiore di 10, si assegna a max il valore di med-1. Nell‟iterazione successiva, in questo

modo si considera la prima metà dell‟array per cercare il valore k. La codifica in C++ è la

seguente:

max=n-1;

min=0;

trovato=false;

while(max>=min && !trovato)

{

med=(max+min)/2;

if (v[med]==k)

trovato=true;

else

if (v[med]>k)

max=med-1;

else

min=med+1;

}

Il caso peggiore corrisponde all‟elemento non presente nell‟array e il caso migliore

all‟elemento trovato durante la prima iterazione:


1 1 1 1

2 1 1 1

3 1 1 1

4 1 n2log +2 2

5 1 n2log +1 1

6 1 n2log +1 1

7 1 0 1

8 1 n2log +1 0

9 1 n2log +1

0

10 1 0

Caso peggiore t(n)=5 n2log +9


Il costo logaritmico è dovuto al numero di divisioni necessarie partendo da un vettore di n

elementi per arrivare a una parte di vettore costituita da un solo elemento.

1

2

7

9

10



1 2

3

4

5

6

Inserimento e cancellazione in un array ordinato

Quando si ha a disposizione un array ordinato, è conveniente mantenerlo ordinato anche in

seguito all‟aggiunta o alla cancellazione di nuovi valori. Partiamo ad esempio dall‟array

seguente e supponiamo di voler inserire un nuovo valore x=20: per mantenere l‟ordinamento,

dobbiamo memorizzare x in posizione p=4 e spostare tutti gli altri valori in avanti di una

posizione:

3 7 12 18 25 27 42 50 61 64 72

0 1 2 3 4 5 6 7 8 9 10

v

Il frammento di codice seguente esegue l‟inserimento di un valore x in un array ordinato in

posizione p:

for (int i=n-1;i>=p;i--)

v[i+1]=v[i];

v[p]=x;

n++;

Il risultato sarà il seguente:

3 7 12 18 25 27 42 50 61 64 72

0 1 2 3 4 5 6 7 8 9 10

v

11

20

Ovviamente per poter spostare i valori in avanti, l‟array deve essere stato dichiarato con un

numero di elementi maggiore di n.

Il caso peggiore corrisponde all‟inserimento per p=0, quando bisognerà spostare tutti gli

elementi presenti in avanti, e il caso migliore all‟inserimento per p=n, quando sarà sufficiente

memorizzare il valore nella prima posizione libera del vettore senza dover spostare elementi:


1 1 1 1

2 1 n+1 1

3 1 n 0

4 1 n 0

5 1 1 1

6 1 1 1





1 2

3

4

5

In maniera equivalente, per la cancellazione di un valore in posizione p, si dovranno spostare

all‟indietro tutti i valori successivi alla posizione stessa. Si osservi il frammento di codice:

for (int i=p;i<n-1;i++)

v[i]=v[i+1];

n--;

Il caso peggiore corrisponde alla cancellazione per p=0, quando bisognerà spostare i restanti

n-1 elementi del vettore all‟indietro, e il caso migliore all‟inserimento per p=n-1, quando sarà

sufficiente diminuire di 1 il numero n senza dover spostare elementi:


1 1 1 1

2 1 n 1

3 1 n-1 0

4 1 n-1 0

5 1 1 1

Caso peggiore t(n)=3n




3 4 5

6 7

8

9

10

11

12

Selectionsort

Per poter usare la ricerca binaria, è necessario ordinare i valori di un array nel caso si parta da

valori disordinati. Esistono svariati algoritmi di ordinamento, che si differenziano in base alle

prestazioni. In questa sezione, vediamo un semplice algoritmo, chiamato ordinamento per

selezione, che non è tra i più efficienti. L‟ordinamento per selezione si basa sul trovare il

valore più piccolo dell‟array e scambiare tale valore con quello in prima posizione.

Successivamente, si trova il valore più piccolo tra gli n-1 valori rimasti e si mette in seconda

posizione, e così via. Il frammento di codice relativo è il seguente:

for (i=0;i<n-1;i++)

{

min=i;

for (j=i+1;j<n;j++)

if (v[j]<v[min]) min=j;

temp=v[i];

v[i]=v[min];

v[min]=temp;

}

Il caso peggiore corrisponde ad un array ordinato in senso inverso, mentre il caso migliore ad

un array già ordinato. Tuttavia, come si vede nella tabella costi-frequenze, i due casi

praticamente coincidono a meno del costo dell‟istruzione n. 7.



per i=0: 11 nj , freq. n-1

per i=1: 12 nj , freq. n-2

…

per i=n-2: 11 njn , freq. 1

Il totale delle frequenze parziali è 1

1

n

k

k = 2

)1(nn.

1 2



Tabella:


1 1 1 1

2 1 n n

3 1 n-1 n-1

4 1 n-1 n-1

5 1 n(n-1)/2+n-1 n(n-1)/2+n-1

6 1 n(n-1)/2 n(n-1)/2

7 1 n(n-1)/2 0

8 1 n(n-1)/2 n(n-1)/2

9 1 n-1 n-1

10 1 n-1 n-1

11 1 n-1 n-1

12 1 n-1 n-1

Caso peggiore t(n)= 662 2 nn

Caso migliore t(n)= 62

13

2

3 2 nn



3

4 5

6

7

8

9

Insertionsort

L‟algoritmo di ordinamento per inserimento, o insertionsort, si basa sull‟inserire man mano

dei valori all‟interno di una parte di array già ordinata. Il frammento di codice relativo è il

seguente:

for (i=0;i<n-1;i++)

{

x=v[i+1];

for (j=i;j>=0 && v[j]>x;j--)

v[j+1]=v[j];

v[j+1]=x;

}


un array già ordinato. Nel caso migliore l‟algoritmo diventa lineare. Il costo del ciclo interno

può essere calcolato determinando la sua frequenza per ogni valore del contatore esterno i:

per i=0: 00 j , freq. 1

per i=1: 01 j , freq. 2

…

per i=n-2: 02 jn , freq. n-1


1

n

k

k = 2

)1(nn.


1 1 1 1

2 1 n n

3 1 n-1 n-1

4 1 n-1 n-1

5 1 n(n-1)/2+n-1 n-1

6 1 n(n-1)/2 0

7 1 n(n-1)/2 0

8 1 n-1 n-1

9 1 n-1 n-1

Caso peggiore t(n)= 42

9

2

3 2 nn

Caso migliore t(n)= 46n

1 2



3

8

4

6

7

9

10

11

5

12

Bubblesort

L‟algoritmo di ordinamento a bolle, o bubblesort, si basa sull‟effettuare confronti tra elementi

adiacenti, che vanno scambiati se non rispettano l‟ordinamento. Il procedimento va ripetuto

fino all‟ordinamento completo del vettore. Ad ogni iterazione interna, l‟algoritmo assicura che

l‟elemento più piccolo della parte ancora da ordinare affiora fino ad accodarsi alla parte già

ordinata. Questo schema base può essere migliorato osservando che se un‟iterazione interna

non effettua nessuno scambio di elementi, allora il vettore risulta essere ordinato e quindi si

può interrompere il procedimento.

Il frammento di codice relativo è il seguente:

i=0;

do

{

scambio=false;

for (j=n-1;j>i;j--)

if (v[j]<v[j-1])

{

temp=v[j];

v[j]=v[j-1];

v[j-1]=temp;

scambio=true;

}

i=i+1;

}

while(i<n-1 && scambio);


un array già ordinato. Nel caso migliore l‟algoritmo diventa lineare.



per i=0: 11 jn , freq. n-1

per i=1: 21 jn , freq. n-2

…

per i=n-2: 11 njn , freq. 1


1

n

k

k = 2

)1(nn.

1

2




1 1 1 1

2 1 n-1 1

3 1 n-1 1

4 1 n(n-1)/2+n-1 n

5 1 n(n-1)/2 n-1

6 1 n(n-1)/2 0

7 1 n(n-1)/2 0

8 1 n(n-1)/2 0

9 1 n(n-1)/2 0

10 1 n(n-1)/2 n-1

11 1 n-1 1

12 1 n-1 1

Caso peggiore t(n)= 42

3

2

7 2 nn

Caso migliore t(n)= 33n

Tabella comparativa dei tre metodi quadratici di ordinamento:

Algoritmo Caso peggiore Caso migliore

Selectionsort 662 2 nn 6

2

13

2

3 2 nn

Insertionsort 4

2

9

2

3 2 nn 46n

Bubblesort 4

2

3

2

7 2 nn 33n



3 1 2

4

5

6

7

Mergesort

L‟algoritmo di ordinamento per fusione (mergesort) segue l‟approccio “divide et impera”:

si divide il problema in sottoproblemi;

si risolvono i sottoproblemi;

si combinano i risultati.

In particolare, in questo algoritmo si divide il vettore per 2 fino ad ottenere segmenti di

lunghezza 1: successivamente si riassemblano segmenti di vettori ordinati in un vettore di

lunghezza doppia tramite fusione.

Per capire come funziona l‟algoritmo, è necessario descrivere la fusione. La fusione (o merge)

si riferisce al problema di ottenere, dati due vettori ordinati, un unico vettore ordinato che

contiene gli elementi di entrambi i vettori di partenza. Il vettore risultante sarà di lunghezza

pari alla somma delle due lunghezze dei vettori dati.

2 5 6 9 13 20 1 3 8 15 21 24

1 2 3 5 6 8 9 13 15 20 21 24

La seguente funzione ottiene la fusione di due parti di vettore comprese tra gli indici q e t, e

t+1 e r, rispettivamente. Il vettore dato si chiama v, mentre w è un vettore di appoggio.

void merge (vettore v, int q, int t, int r)

{

vettore w;

int i=q; int j=t+1; int k=q;

while (i<=t && j<=r)

{

if (v[i]<=v[j])

{

w[k]=v[i];

i=i+1;

}

else



8

9

10

11

12

13

14

15

16

17

18

19

20 21

22

23

{

w[k]=v[j];

j=j+1;

}

k=k+1;

}

if (i<=t)

do

{

w[k]=v[i];

k=k+1;

i=i+1;

}

while (i<=t);

else

do

{

w[k]=v[j];

k=k+1;

j=j+1;

}

while (j<=r);

for (k=q; k<=r; k=k+1)

v[k]=w[k];

}

Pongo n=r-q+1

n1=t-q+1

n2=r-t

n1+n2=n


1 1 1 1

2 1 1 1

3 1 1 1

4 1 n n1+1

5 1 n-1 n1

6 1 n1 n1

7 1 n1 n1

8 1 n2-1 0

9 1 n2-1 0



3

1

2

4

5

10 1 n-1 n1

11 1 1 1

12 1 0 0

13 1 0 0

14 1 0 0

15 1 0 0

16 1 1 n2

17 1 1 n2

18 1 1 n2

19 1 1 n2

20 1 1 1

21 1 n+1 n+1

22 1 n n

23 1 n n

Nel caso peggiore consideriamo il caso in cui il ciclo while ricopia il massimo di elementi (n-

1 elementi), cioè, per semplificare, il caso in cui si alterna la copia di un elemento dal primo e

dal secondo vettore:

t(n)=6n+2n1+2n2+6= (ponendo n1=n2=n/2)

=8n+6

nel caso migliore, consideriamo il caso in cui il primo ciclo ricopia gli elementi solo del primo

vettore e mai del secondo, cioè quando gli elementi del primo vettore vengono tutti prima

degli elementi del secondo vettore:

t(n)=3n+5n1+4n2+7= (ponendo n1=n2=n/2)

=15/2 n +7

Il seguente codice realizza l‟algoritmo di mergesort:

void mergesort (vettore v, int q, int r)

{

int t;

if (q<r)

{

t=(q+r)/2;

mergesort (v,q,t);

mergesort (v,t+1,r);

merge (v,q,t,r);

}

}

1° chiamata: mergesort (v,0,n-1);



n=r-q+1

q<r n>1

# istr. costo freq. (n>1) freq. (n=1)

1 1 1 1

2 1 1 0

3 t(n/2) 1 0

4 t(n/2) 1 0

5 8n+6 1 0


t(n) =2t(n/2)+8n+8

t(1)=1

Per avere un‟equazione più generale, poniamo:

t(n)=2t(n/2)+cn+d

Soluzione:

t(n/2)=2t(n/4)+cn/2+d

t(n)=4t(n/4)+cn+2d+cn+d=4t(n/4)+2cn+3d

t(n/4)=2t(n/8)+cn/4+d

t(n)=8t(n/8)+cn+4d+2cn+3d=8t(n/8)+3cn+7d

t(n/8)=2t(n/16)+cn/8+d

t(n)= 16t(n/16)+cn+8d +3cn+7d= 16t(n/16)+4cn+15d

….

t(n) = dncnntn )1(log)1( 2 =

= dndncn )1(log2 =

= 89log8 2 nnn

Applichiamo l‟algoritmo a un vettore con numero di elementi pari a una potenza di 2, per

descrivere più facilmente il funzionamento. Consideriamo ad esempio il seguente vettore con

8 elementi:

7 1 4 6 2 3 9 5

0 1 2 3 4 5 6 7

v

Le chiamate ricorsive determinate dall‟algoritmo sono schematizzate come nella figura

seguente. Abbiamo un numero di chiamate della funzione mergesort per pn 2 pari a:



1+2+4+8+... = ...2222 3210 = p

k

k

0

2 = 12 1p = 2n-1.

Il numero di chiamate della funzione merge è 12 p = n-1

E‟ possibile stimare il tempo di calcolo osservando che abbiamo un tempo di esecuzione

lineare per ogni livello della figura dovuto alle attivazioni della funzione merge su n elementi.

Inoltre i livelli sono pari a p e quindi in totale abbiamo un tempo nlogn.

7 1 4 6 2 3 9 5

0 1 2 3 4 5 6 7

7 1 4 6

0 1 2 3

2 3 9 5

4 5 6 7

7 1

0 1

4 6

2 3

2 3

4 5

9 5

6 7

7

0

1

1

4

2

6

3

2

4

3

5

9

6

5

7

1 7

0 1

merge(v,0,0,1)

4 6

2 3

merge(v,2,2,3)

2 3

4 5

merge(v,4,4,5)

5 9

6 7

merge(v,6,6,7)

merge(v,0,1,3)

1 4 6 7

0 1 2 3

merge(v,4,5,7)

2 3 5 9

4 5 6 7

1 2 3 4 5 6 7 9

0 1 2 3 4 5 6 7

merge(v,0,3,7)

livello 0

livello 1

livello 2

livello 3

livello 2

livello 1

livello 0



Quicksort

Anche il quicksort è un algoritmo basato su una strategia “divide et impera”. La suddivisione

dell‟array da ordinare non avviene nel punto di mezzo come nel mergesort, ma attraverso una

operazione di „partizione‟ che suddivide l‟array in due parti tali che nella prima parte ci siano

tutti i valori minori o uguali a un valore fissato (detto pivot) e nella seconda parte ci siano tutti

i valori maggiori o uguali al pivot.

La seguente funzione che realizza la partizione dell‟array sceglie come elemento pivot il

primo elemento dell‟array. La funzione scandisce l‟array con due indici da estremi opposti,

scambiando di volta in volta le coppie di valori che non rispettano la condizione desiderata.

Esempio di vettore v con pivot x[0]=8:



3 1 2

4

8

5 6

7

10 9

11

int partizione (vettore v, int q, int r)

{

int i,j,x ;

x=v[q] ; i=q-1 ; j=r+1 ; //x pivot

while (i<j)

{

do j=j-1 while (v[j]>x);

do i=i+1 while (v[i]<x);

if (i<j) scambia (v[i],v[j]);

}

return j;

}



3

1

2

4

Calcolo della t(n):

n=r-q+1

# istr. costo freq. (array

ordinato)

freq.

(suddivisione a

metà, con 1 solo

scambio)

freq. (suddivisione

a metà, con max

scambi)

1 1 1 1 1

2 1 1 1 1

3 1 1 1 1

4 1 2 3 n/2+1

5 1 n n/2 n/2

6 1 n n/2 n/2

7 1 1 n/2 n/2

8 1 1 n/2 n/2

9 1 1 2 n/2

10 3 0 1 n/2

11 1 1 1 1

Caso peggiore per il quicksort: array ordinato t(n)=2n+9

Caso migliore per il quicksort: suddivisione sempre a metà

- con 1 scambio (scambio solo pivot): t(n)=2n+12

- con max scambi: t(n)=9/2 n + 5

La funzione quicksort:

void quicksort (vettore v, int q, int r)

{

int t;

if (q<r)

{

t=partizione(v,q,r);

quicksort (v,q,t);

quicksort (v,t+1,r);

}

}

# istr. costo (c.p.) costo (c.m.) freq. (n>1) freq. (n=1)

1 1 1 1 1

2 2n+9 2n+12 1 0

3 t(1) t(n/2) 1 0

4 t(n-1) t(n/2) 1 0



Caso migliore (suddivisione perfettamente bilanciata, la funzione partizione ogni volta divide

il vettore a metà):

t(n)=2t(n/2) + 2n + 13

t(1)=1

soluzione come il mergesort:

t(n) = dndncn )1(log2 = 1314log2 2 nnn .

• Caso ottimale:

– Partizione bilanciata

– Costo n log n pari al numero dei livelli per il costo lineare della partizione:

Caso peggiore (array già ordinato e conseguente suddivisione totalmente sbilanciata; ogni

chiamata di partizione suddivide il vettore in una parte di un solo elemento e una parte dei

restanti elementi):

t(n)= t(n-1) + t(1) + 2n +10

t(1)=1

Poniamo:

t(n) = t(n-1) + 2n + 11 = t(n-1) + cn +d

soluzione:

t(n-1)=t(n-2) + c(n -1) +d

t(n)=t(n-2) + c(n -1) +d + cn +d =t(n-2)+ c(n -1) + cn +2d

t(n-2)=t(n-3) + c(n-2) +d

t(n)= t(n-3) + c(n-2) +d + c(n -1) + cn +2d =t(n-3)+ c(n-2) + c(n -1) + cn +3d

t(n-3)=t(n-4) + c(n-3) +d

t(n)= t(n-4) + c(n-3) +d + c(n-2) + c(n -1) + cn +3d = t(n-4)+c(n-3)+c(n-2)+c(n -1)+cn +4d

.....

t(n)= t(1) + c 2 + c 3 + ... + c(n-3)+c(n-2)+c(n -1)+cn + (n-1) d =



= 1 + c n

k

k2

+ d (n-1) = 1 + c 2

)1(nn - c +d(n-1) = 2 1

2 2

c cn d n c d

= 2 12 12n n

• Caso peggiore:

– Partizione sbilanciata

– Costo quadratico pari al numero dei livelli per il costo lineare della partizione



Tabella comparativa dei metodi nlogn di ordinamento:

Algoritmo Caso peggiore Caso migliore

t(n) ))(( ng t(n) ))(( ng

Mergesort 89log8 2 nnn )log( nn 89log8 2 nnn )log( nn

Quicksort 2 12 12n n )( 2n 1314log2 2 nnn )log( nn

Tabella comparativa dei metodi di ordinamento:

Caso peggiore Caso medio Caso migliore

Mergesort )log( nn )log( nn )log( nn

Quicksort )( 2n )log( nn )log( nn

Selectionsort )( 2n )( 2n )( 2n

Insertionsort )( 2n )( 2n )(n

Bubblesort )( 2n )( 2n )(n

Algoritmi ottimi:

Per il problema dell‟ordinamento, la delimitazione inferiore della complessità è )log( nn .

Pertanto, il solo algoritmo ottimo che abbiamo trattato è il mergesort che ha complessità nel

caso peggiore )log( nn .

Per il problema della ricerca, la delimitazione inferiore della complessità è )(logn . Pertanto

la ricerca binaria è un algoritmo ottimo perché risolve il problema in tempo )(logn .

Le notazioni asintotiche si possono applicare anche allo spazio di memoria utilizzato e non

solo al tempo.

Occupazione di memoria degli algoritmi di ordinamento:

Il mergesort ha un‟occupazione di memoria pari a 2n, mentre per tutti gli altri si ha n.



Strutture dati fondamentali (tipi astratti)

• I tipi astratti sono strutture dati generali di particolare importanza in informatica.

• Tra di essi abbiamo: insiemi, liste, pile, code, matrici, alberi, grafi.

• Possiamo studiare le proprietà e le operazioni dei tipi di dato astratto

indipendentemente dalla loro realizzazione tramite i tipi offerti dai linguaggi di

programmazione

• Distinguiamo tra tipi astratti e tipi concreti: un tipo astratto può avere più

rappresentazioni concrete. Ad esempio, possiamo studiare le liste in generale, ma poi

implementarle con diverse tecniche: array statici, array dinamici, liste collegate con

record e puntatori, etc.

• La programmazione con tipi astratti prevede la scrittura di programmi

indipendentemente dalla rappresentazione utilizzata.

Liste

Le liste sono sequenze ordinate di elementi. Per sequenza ordinata si intende un insieme in cui

è possibile riconoscere un primo elemento, un secondo, e così via. Si tratta quindi di un

ordinamento sulle posizioni degli elementi e non sui loro valori. Quindi i valori all‟interno di

una lista sono in generale disordinati, non rispettando alcun ordinamento particolare,

crescente o decrescente.

• Introduciamo tre rappresentazioni per le liste:

– Rappresentazione con array

– Rappresentazione con liste collegate di record e puntatori

– Rappresentazione con liste collegate bidirezionali

Rappresentazione con array

Una lista può essere rappresentata con un array. È utile associare a quest‟ultimo un campo che

indica il numero di elementi della lista. L‟occupazione di memoria è pari a n.

Rappresentazione:

const int D=100 ;

typedef int vettore[D];

struct lista

{

int n ; //numero valori lista

vettore valori; //valori lista

};

Considerazioni sulla complessità:



L‟accesso a un elemento di una lista rappresentata con un array è )1( . L‟inserimento di un

elemento in una determinata posizione è )(n nel caso peggiore a causa dello spostamento

degli altri elementi.

Rappresentazione con liste collegate di record e puntatori

Per ogni elemento, abbiamo bisogno di un record con campo valore e campo puntatore al

record successivo. L‟occupazione di memoria è pari a 2n.

struct elemento

{

int valore; //campo valore

elemento* succ; //campo puntatore al successivo

};

typedef elemento* lista;

Considerazioni sulla complessità:

L‟accesso a un elemento di una lista collegata è )(n nel caso peggiore, perché bisogna

scorrere la lista. L‟inserimento di un elemento dopo un certo elemento è )1( , perché non è

necessario spostare elementi.

Rappresentazione con liste collegate bidirezionali

Questa rappresentazione prevede un puntatore all‟elemento precedente, oltre al puntatore

all‟elemento successivo. Può essere utile per scorrere facilmente la lista in entrambe le

direzioni. L‟occupazione di memoria aumenta ed è pari a 3n. È necessario mantenere due

puntatori iniziali, al primo e all‟ultimo elemento.

7

l1

3 8 5

struct elemento

{

int valore; //campo valore

elemento* succ; //campo puntatore al successivo

elemento* prec; //campo puntatore al precedente

};

typedef elemento* pelem;

struct lista

{

pelem primo;

pelem ultimo;



};

Vediamo alcune funzioni, come CreaLista e StampaLista:

void CreaLista (lista & l, int n)

{

if (n==0)

{

l.primo = NULL;

l.ultimo = NULL;

}

else if (n>0)

{

l.primo = new elemento;

pelem p1;

p1=l.primo;

p1->prec=NULL;

cout<<"elemento 0=";

cin >> p1->valore;

for (int i=1;i<n;i++)

{

p1->succ=new elemento;

p1->succ->prec=p1;

p1=p1->succ;

cout<<"elemento "<<i<<"=";

cin >> p1->valore;

}

p1->succ=NULL;

l.ultimo=p1;

}

}

void StampaLista (lista l)

{

if (l.primo!=NULL)

{

pelem p1=l.primo;

while (p1!=NULL)

{

cout<<p1->valore<<" ";

p1=p1->succ ;

}

}

}

La funzione StampaListaInv, che in versione iterativa per le liste collegate semplici aveva

complessità )( 2n , per le liste bidirezionali è )(n .

void StampaListaInv (lista l)

{

if (l.ultimo!=NULL)

{

pelem p1=l.ultimo;



while (p1!=NULL)

{

cout<<p1->valore<<" ";

p1=p1->prec ;

}

}

}

Di seguito si riporta una versione ricorsiva per la creazione di una lista bidirezionale. Sono

necessarie due funzioni: la funzione ricorsiva CreaListaRic è richiamata dalla funzione

CreaLista:

void CreaListaRic (pelem & p, pelem prec, int n, pelem & ultimo)

{

if (n>0)

{

p = new elemento;

cin >> p->valore;

p->prec=prec;

CreaListaRic (p->succ,p,n-1,ultimo);

}

else

{

p = NULL;

ultimo=prec;

}

}

void CreaLista (lista & l, int n)

{

CreaListaRic (l.primo, NULL, n, l.ultimo);

}

Operazioni elementari sulle liste

Sulle liste non c‟è un modo univoco di definire le operazioni elementari. Si può seguire la

strada di definire un insieme molto ristretto di operazioni, ma questo va spesso a scapito

dell‟efficienza degli algoritmi su liste più complessi a seconda delle rappresentazioni.

Un insieme minimale di operazioni può essere il seguente:

Inserisci (x, pos, l): inserisce un nuovo elemento con valore x in posizione pos. Deve

verificarsi che pos è compresa tra 0 e n. Per pos = 0 abbiamo un inserimento in testa.

Per pos = n abbiamo un inserimento in coda.

Cancella(pos, l): cancella l‟elemento in posizione pos, per pos compresa tra 0 e n-1.

Per pos = 0 abbiamo la cancellazione in testa. Per pos=n-1 abbiamo la cancellazione in

coda.

Accedi(pos, l): restituisce il valore dell‟elemento in posizione pos.

Init(l): inizializza una lista vuota.

ListaVuota(l): effettua il test di lista vuota.



È utile considerare anche le seguenti operazioni elementari per risolvere in maniera efficace

alcuni problemi tipici:

InsTesta(x, l): inserisce l‟elemento x in testa alla lista l;

InsCoda(x,l): inserisce l‟elemento x in coda alla lista l;

CancTesta(l): cancella l‟elemento di testa;

CancCoda(l): cancella l‟elemento di coda;

AccediTesta(l): restituisce l‟elemento di testa;

AccediCoda(l): restituisce l‟elemento di coda;

numElementi(l): restituisce il numero di elementi di una lista;

Copia(l1,l2): copia la lista l1 nella lista l2;

CancellaLista(l): cancella l‟intera lista l.

Consideriamo i seguenti prototipi:

void Inserisci(int x, int pos, lista & l);

void Cancella(int pos, lista & l);

int Accedi(int pos, lista l);

lista Init();

bool ListaVuota(lista l);

void InsTesta(int x, lista & l);

void InsCoda(int x, lista & l);

void CancTesta(lista & l);

void CancCoda(lista & l);

int AccediTesta(lista l);

int AccediCoda(lista l);

int numElementi(lista l);

void Copia(lista l1, lista & l2);

void CancellaLista(lista & l);

Scriviamo alcune funzioni facendo uso delle sole operazioni elementari. La funzione

CreaLista:

lista CreaLista (int n)

{

int x;

lista l=Init();

for (int i=0; i<n; i++)

{

cin>>x;

Inserisci(x,i,l);

}

return l;

}

La funzione CreaLista fa uso dell‟operazione Inserisci. Per la rappresentazione con array,

scriviamo la funzione relativa:



void Inserisci(int x, int pos, lista & l)

//inserisce un elemento con valore x in posizione pos. pos è compresa tra 0

e n. Per pos =0 abbiamo un inserimento in testa. Per pos=n abbiamo un

inserimento in coda.

{

if (pos<0) cout << pos << "negativo";

else if (pos>l.n) cout << pos << " troppo grande"; else

{

for (int i=l.n-1;i>=pos;i--)

l.valori[i+1]= l.valori[i]; l.valori[pos]=x; //memorizzazione valore x in posizione p

l.n++;

}

}

La complessità nel caso peggiore (corrispondente all‟inserimento in testa) è )(n , mentre nel

caso migliore (corrispondente all‟inserimento in coda) è )1( .

Per la rappresentazione con liste collegate semplici, abbiamo la seguente funzione:


//inserisce un elemento con valore x in posizione pos. pos è compresa tra 0

e n. Per pos =0 abbiamo un inserimento in testa. Per pos=n abbiamo un

inserimento in coda.

{

if (pos<0) cout << pos << "negativo"; else

if (pos==0)

{

elemento* p1=new elemento;

p1->valore=x;

p1->succ=l;

l=p1;

}

else

{

elemento* p=l ;

for (int i=0 ; p!=NULL && i<(pos-1); i++)

p=p->succ;

if (p!=NULL)

{

elemento* paux;

paux=p->succ;

p->succ=new elemento ;

p=p->succ;

p->valore=x ;

p->succ=paux ;

}

else cout << pos << "troppo grande";

}



}

La complessità nel caso peggiore (corrispondente all‟inserimento in coda) è )(n , mentre nel

caso migliore (corrispondente all‟inserimento in testa) è )1( .

La complessità della funzione CreaLista con le due rappresentazioni:

1. nella rappresentazione con array, le chiamate ad Inserisci avvengono inserendo sempre

in coda l‟elemento, che coincide con il caso migliore di Inserisci, pari a )1( .

Complessivamente la CreaLista ha tempo )(n ;

2. Nella rappresentazione con liste collegate, ogni chiamata di Inserisci corrisponde al

caso peggiore per questa rappresentazione, cioè )(n . Complessivamente si ha

)( 2n .

Nella rappresentazione con liste bidirezionali possiamo avere un miglioramento a patto che

usiamo l‟operazione elementare InsCoda, che ha costo costante, al posto della generica

Inserisci:

void InsCoda(int x, lista & l)

{

if (l.ultimo==NULL)

{

l.primo = new elemento;

l.primo->prec=NULL;

l.primo->valore=x;

l.primo->succ=NULL;

l.ultimo=l.primo;

}

else

{

l.ultimo->succ=new elemento;

l.ultimo->succ->prec=l.ultimo;

l.ultimo=l.ultimo->succ;

l.ultimo->valore=x;

l.ultimo->succ=NULL;

}

}

La funzione CreaLista modificata ha costo lineare con la rappresentazione con liste

bidirezionali:

lista CreaLista (int n)

{

int x;

lista l=Init();

for (int i=0; i<n; i++)

{

cin>>x;

InsCoda(x,l);

}

return l;

}



Altri esempi:

invertire una lista, facendo uso di sole operazioni primitive:

void InvertiLista(lista & l)

{

lista l1=Init();

int x;

while(!ListaVuota(l))

{

x=AccediTesta(l);

CancTesta(l);

InsTesta(x,l1);

}

Copia(l1,l);

CancellaLista(l1);

}

Concatenare due liste, facendo uso di sole operazioni primitive:

void ConcatenaListe(lista & l1, lista & l2, lista & l3)

{

l3=Init();

Copia(l1,l3);

int x;

while(!ListaVuota(l2))

{

x=AccediTesta(l2);

CancTesta(l2);

InsCoda(x,l3);

}

CancellaLista(l1);

}

void Fusione(lista & l1, lista & l2, lista & l3)

{

l3=Init();

while (!ListaVuota(l1)&&!ListaVuota(l2))

{

if (AccediTesta(l1)<AccediTesta(l2))

{

InsCoda(AccediTesta(l1), l3);

CancTesta(l1);

}

else

{

InsCoda(AccediTesta(l2), l3);

CancTesta(l2);

}

}




{

InsCoda(AccediTesta(l1),l3);

CancTesta(l1);

}


{

InsCoda(AccediTesta(l2),l3);

CancTesta(l2);

}

}

Scrivere una funzione che, data una lista contenente valori ordinati in senso crescente, crei una nuova

lista senza i valori ripetuti (per esempio, se la prima lista contiene i valori 2, 4, 4, 6, 7, 7, 8, al termine

della funzione la seconda lista dovrà contenere i valori 2, 4, 6, 7, 8). La prima lista deve rimanere

invariata. Si deve fare uso di sole operazioni primitive su liste. Qual è la complessità computazionale?

void CreaSenzaRipetuti(lista l, lista & l1)

{

int x=AccediTesta(l);

l1=Init();

InsTesta(x,l1);

for(int i=1;i<numElementi(l);i++)

{

x=Accedi(i,l);

if (x!=AccediCoda(l1))

InsCoda(x,l1);

}

}

Nel caso della rappresentazione con array, le operazioni primitive utilizzate hanno tutte costo )1( .

Pertanto la complessità computazionale, determinata dal costo del ciclo, è )(n . Nel caso della

rappresentazione con liste collegate, le operazioni primitive presenti in questa funzione hanno un costo

)(n , determinando una complessità della funzione pari a )( 2n .

Scrivere una funzione che, data una lista contenente valori ordinati in senso crescente, cancelli dalla

lista i valori ripetuti (per esempio, se la lista contiene i valori 2, 4, 4, 6, 7, 7, 8, al termine della

funzione la lista dovrà contenere i valori 2, 4, 6, 7, 8). Si deve fare uso di sole operazioni primitive su

liste. Qual è la complessità computazionale?

Soluzione a:

void CancellaValoriRipetuti(lista & l)

{

int x=AccediTesta(l);

lista l1=Init();

InsTesta(x,l1);

for(int i=1;i<numElementi(l);i++)



{

x=Accedi(i,l);

if (x!=AccediCoda(l1))

InsCoda(x,l1);

}

CancellaLista(l);

Copia(l1,l);

}

Soluzione b:

void CancellaValoriRipetuti(lista & l)

{

int i=0;

while (i<numElementi(l)-1)

{

if (Accedi(i,l)==Accedi(i+1,l))

Cancella(i+1,l);

else

i++;

}

}

Data una lista, scrivere una funzione che trasferisca in una nuova lista gli elementi che contengono

valori maggiori di un dato intero x. Pertanto la lista data non deve più contenere al termine della

funzione gli elementi trasferiti. Inoltre la lista creata deve contenere i valori trasferiti nello stesso

ordine in cui si trovavano nella lista data. Si deve fare uso di sole operazioni primitive su liste. Qual è

la complessità computazionale?

soluzione:

void TrasferisciValoriMaggiori(lista & l, int x, lista & l1)

{

int elem;

lista l2=Init();

while (!ListaVuota(l))

{

elem=AccediTesta(l);

if (elem>x)

InsCoda(elem,l1);

else

InsCoda(elem,l2);

CancellaTesta(l);

}

Copia(l2,l);

CancellaLista(l2);

}



Nel caso della rappresentazione con array, l‟operazione primitiva più costosa all‟interno del ciclo è

CancellaTesta che ha costo )(n . Pertanto la complessità computazionale, determinata dal costo del

ciclo, è )( 2n . Nel caso della rappresentazione con liste collegate, l‟operazione primitiva più costosa

all‟interno del ciclo è InsCoda che ha costo )(n , determinando una complessità della funzione pari a

)( 2n .

Codifica operazioni primitive nella rappresentazione con array

lista Init()

{

lista l;

l.n=0;

return l;

}

int Accedi(int pos, lista l)

{


else if (pos>l.n) cout << pos << " troppo grande";

else

return l.valori[pos];

}

int AccediTesta(lista l)

{

if (l.n==0) cout << "lista vuota";

else

return l.valori[0];

}

int AccediCoda(lista l)

{


else

return l.valori[l.n-1];

}

bool ListaVuota(lista l)

{

return (l.n==0);

}




//inserisce un elemento con valore x in posizione pos. pos è

//compresa tra 0 e n. Per pos =0 abbiamo un inserimento in

//testa. Per pos=n abbiamo un inserimento in coda.

{


else if (pos>l.n) cout << pos << " troppo grande";

else

{

for (int i=l.n-1;i>=pos;i--)

l.valori[i+1]=l.valori[i];

l.valori[pos]=x; //memorizzazione valore x in

//posizione p

l.n++;

}

}

void InsTesta(int x, lista & l)

{

for (int i=l.n-1;i>=0;i--)

l.valori[i+1]=l.valori[i];

l.valori[0]=x; //memorizzazione valore x in posizione 0

l.n++;

}


{

l.valori[l.n]=x; //memorizzazione valore x in posizione l.n

l.n++;

}

void Cancella(int pos, lista & l)

{


else

{

for (int i=pos;i<l.n-1;i++)

l.valori[i]=l.valori[i+1];

l.n--;

}

}

void CancTesta(lista & l)

{




else

{

for (int i=0;i<l.n-1;i++)

l.valori[i]=l.valori[i+1];

l.n--;

}

}

int numElementi(lista l)

{

return l.n;

}

void Copia(lista l1, lista & l2)

{

for (int i=0;i<l1.n;i++)

l2.valori[i]=l1.valori[i];

l2.n=l1.n;

}

void CancellaLista(lista & l)

{

l.n=0;

}

Codifica operazioni primitive nella rappresentazione con liste collegate

lista Init()

{

lista l;

l=NULL;

return l;

}

int Accedi(int pos, lista l)

{


else

if (pos==0)

{

return l->valore;

}

else

{



elemento* p=l ;

for (int i=0 ; p!=NULL && i<pos; i++)

p=p->succ;

if (p!=NULL)

{

return p->valore;

}


}

}

int AccediTesta(lista l)

{

if (l==NULL) cout << "lista vuota";

else

return l->valore;

}

bool ListaVuota(lista l)

{

return (l==NULL);

}


//inserisce un elemento con valore x in posizione pos. pos è

compresa tra 0 e n. Per pos =0 abbiamo un inserimento in

testa. Per pos=n abbiamo un inserimento in coda.

{


else

if (pos==0)

{


p1->valore=x;

p1->succ=l;

l=p1;

}

else

{

elemento* p=l ;

for (int i=0 ; p!=NULL && i<(pos-1); i++)

p=p->succ;

if (p!=NULL)

{

elemento* paux;

paux=p->succ;



p->succ=new elemento ;

p=p->succ;

p->valore=x ;

p->succ=paux ;

}


}

}

void InsTesta(int x, lista & l)

{


p1->valore=x;

p1->succ=l;

l=p1;

}


{

if (l==NULL) //lista nulla

{

l=new elemento;

l->valore=x;

l->succ=NULL;

}

else

{

elemento* paux;

paux=l;

while (paux->succ!=NULL)

paux=paux->succ;

paux->succ=new elemento;

paux=paux->succ;

paux->valore=x;

paux->succ=NULL;

}

}

void CancTesta(lista & l)

{

if (l!=NULL)

{

elemento* paux=l;

l=l->succ;

delete paux;



}

}

int numElementi(lista l)

{

int i=0;

while (l!=NULL)

{

l=l->succ;

i++;

}

return i;

}

void Copia(lista l1, lista & l2)

{

if (l1==NULL) l2=NULL;

else

{

l2 = new elemento;

l2->valore=l1->valore;

elemento *p1=l1->succ, *p2=l2;

while (p1!=NULL)

{

p2->succ=new elemento;

p2=p2->succ;

p2->valore=p1->valore;

p1=p1->succ;

}

p2->succ=NULL;

}

}

void CancellaLista(lista & l)

{

elemento *p=l;

while (l!=NULL)

{

l=l->succ;

delete p;

p=l;

}

}



Pile e code

Pile e code sono sequenze ordinate di elementi (come le liste) in cui si disciplina la strategia

di accesso. La lettura di un elemento di queste strutture dati, così come la cancellazione di un

elemento o l‟inserimento di un nuovo elemento, avvengono con delle regole ben precise.

Pile

Nella pila („stack‟ in inglese), l‟accesso è limitato ad una sola estremità della sequenza. Esiste

quindi un elemento affiorante (l‟elemento „top‟ della pila) a cui è possibile accedere, mentre

non è possibile accedere agli altri elementi, se non rimuovendo l‟elemento affiorante.

L‟operazione di cancellazione dalla pila dell‟elemento affiorante si chiama „pop‟, mentre

l‟operazione di inserimento di un nuovo elemento al di sopra dell‟elemento affiorante si

chiama „push‟. Questa strategia di accesso per le pile va sotto il nome di „LIFO‟ (last in first

out): l‟ultimo elemento ad entrare in una pila sarà il primo ad uscirne.

7

1

5

9

4

3

Le pile sono strutture dati molto comuni in informatica. Ad esempio, la gestione della

memoria per le chiamate a funzioni avviene tramite uno „stack‟ di sistema. Nello stack sono

depositate le informazioni relative alle chiamate di funzioni. L‟ultima funzione ad essere

chiamata sarà quella affiorante nello stack. Ad esempio, nel caso di chiamate ricorsive,

l‟ultima chiamata sarà anche la prima ad essere completata.

In totale, possiamo definire cinque operazioni primitive su pile:

Crea(p): inizializza una nuova pila p;

Top(p): accede all‟elemento affiorante della pila p;

Push(x,p): aggiunge un elemento x alla pila p;

Pop(p): rimuove un elemento dalla pila p;

Vuota(p): compie il test di pila vuota.



Codifichiamo queste operazioni con le seguenti funzioni, supponendo di aver già dichiarato

un tipo „pila‟ ed un tipo „elemento‟:

pila CreaPila();

elemento Top(pila p);

void Push(elemento x, pila & p);

void Pop(pila & p);

bool PilaVuota(pila p);

Con queste operazioni primitive, possiamo costruire qualsiasi algoritmo che opera su pile. Ad

esempio, vogliamo leggere e cancellare l‟ultimo elemento di una pila. Allo scopo, abbiamo

bisogno di una pila di appoggio:

pila p=CreaPila();

…

//riempimento della pila p

…

pila p1=CreaPila();

elemento x;

while(!PilaVuota(p))

{

x=Top(p);

Pop(p);

Push(x,p1);

}

x=Top(p1);

Stampa(x);

Pop(p1);

while(!PilaVuota(p1))

{

x=Top(p1);

Pop(p1);

Push(x,p);

}



Rappresentazioni per le pile

Le pile possono essere rappresentate in vari modi. Esaminiamo una rappresentazione con

array e una con liste collegate.

Rappresentazione con array

7

1

5

9

4

3 top

const int D=100 ;

typedef int elemento; //dipende dalla definizione dell’elemento

typedef elemento vettore[D];

struct pila

{

int top ; //indice elemento top, se -1 pila vuota

vettore elementi; //elementi pila

};

Vediamo come le operazioni primitive sono implementate con questa rappresentazione:

pila CreaPila()

{

pila p;

p.top=-1;

return p;

}

elemento Top(pila p)

{

if (p.top==-1) cout<<”Pila vuota”;

else return p.elementi[p.top];

}

void Push(elemento x, pila & p)

{

if (p.top==D-1)

cout<<”Pila piena”;

else

{

p.elementi[p.top+1]=x;



p.top++;

}

}

void Pop(pila & p)

{

if (p.top==-1) cout<<”Pila vuota”;

else p.top--;

}

bool PilaVuota(pila p)

{

return (p.top==-1);

}

L‟operazione primitiva Push può dar luogo ad un errore se l‟array è tutto pieno.

Scriviamo una funzione per la memorizzazione di n valori letti da tastiera in una pila:

pila LeggiPila(int n)

{

pila p;

p=CreaPila();

elemento x;

for (int i=0;i<n;i++)

{

cout<<"elemento "<<i<<"=";

cin >> x;

Push(x,p);

}

return p;

}

Scriviamo una funzione per la stampa su video degli elementi di una pila. Notiamo che la

funzione non svuota la pila perché il parametro è passato per valore: quindi la funzione svuota

una copia della pila originaria.

void ScriviPila(pila p)

{

elemento x;


{

x=Top(p);

cout << x << “ “;

Pop(p);

}

}



Rappresentazione con liste collegate


struct record

{

elemento valore;

record* succ;

};

typedef record* pila;

5 1 6 8pila

In questa rappresentazione, il puntatore iniziale alla lista punta all‟elemento affiorante della

pila. Vediamo la codifica delle operazioni primitive con questa rappresentazione.

pila CreaPila()

{

pila p;

p=NULL;

return p;

}

elemento Top(pila p)

{

if (p==NULL) cout<<”Pila vuota”;

else return p->valore;

}

void Push(elemento x, pila & p)

{

record* paux=new record;

paux->valore=x;

paux->succ=p;

p=paux;

}

void Pop(pila & p)

{

if (p==NULL) cout<<”Pila vuota”;

else

{

record* paux=p;

p=p->succ;

delete paux ;

}

}

bool PilaVuota(pila p)

{

return (p==NULL);

}



Con questa rappresentazione, la funzione scritta in precedenza per la stampa degli elementi di

una pila non funziona correttamente dato che essa causa lo svuotamento della pila stessa. Non

è infatti possibile effettuare la copia della lista collegata passando il parametro per valore.

Quindi la funziona ScriviPila va riscritta, salvando gli elementi in una pila di appoggio man

mano che vengono estratti dalla pila data, e poi ricostituendo la pila originaria:

void ScriviPila(pila & p)

{

elemento x;

pila p1=CreaPila();


{

x=Top(p);

cout << x << " ";

Pop(p);

Push(x,p1);

}

while(!PilaVuota(p1))

{

x=Top(p1);

Pop(p1);

Push(x,p);

}

}

In entrambe le rappresentazioni viste, le operazioni primitive sulle pile hanno un tempo di

esecuzione costante. La funzione ScriviPila ha un tempo di esecuzione lineare.



Code

Nelle code („queue‟ in inglese), l‟accesso in ingresso è limitato ad una estremità della

sequenza, mentre l‟accesso in uscita all‟altra estremità. Dal lato in uscita, c‟è il solo elemento

che è possibile esaminare (l‟elemento „front‟ della coda). L‟operazione di cancellazione dalla

coda di tale elemento si chiama „pop‟, mentre l‟operazione di inserimento di un nuovo

elemento nell‟altra estremità si chiama „push‟. Questa strategia di accesso per le code va sotto

il nome di „FIFO‟ (first in first out): il primo elemento ad entrare in una coda sarà il primo ad

uscirne.

7 1 5 9 4 3

Le code sono strutture dati molto comuni in informatica. Ad esempio, molte funzioni del

sistema operativo per la gestione delle periferiche si basano sulle code. Varie richieste da più

utenti o programmi per l‟uso di una stampante saranno gestite con una coda: la richiesta che

arriva per prima sarà servita per prima.

In totale, possiamo definire cinque operazioni primitive su code:

Crea(c): inizializza una nuova coda c;

Front(c): accede all‟elemento affiorante della coda c;

Push(x,c): aggiunge un elemento x alla coda c;

Pop(c): rimuove un elemento dalla coda c;

Vuota(c): compie il test di coda vuota.

Codifichiamo queste operazioni con le seguenti funzioni, supponendo di aver già dichiarato

un tipo „coda‟ ed un tipo „elemento‟:

coda CreaCoda();

elemento Front(coda c);

void Push(elemento x, coda & c);

void Pop(coda & c);

bool CodaVuota(coda c);

Con queste operazioni primitive, possiamo costruire qualsiasi algoritmo che opera su code.

Supponiamo di voler svuotare una coda e stampare gli elementi sul video:

coda c=CreaCoda();

…

//riempimento della coda c

…

elemento x;

while(!CodaVuota(c))

{

x=Front(c);

Stampa(x);

Pop(c);

}



Rappresentazioni per le code

Le pile possono essere rappresentate in vari modi. Esaminiamo due rappresentazioni con array

e una con liste collegate.

Prima rappresentazione con array

Gli elementi sono inseriti alla fine del vettore ed estratti all‟inizio. Le due estremità sono

indicate con due indici front e last. L‟indice front rappresenta l‟elemento da estrarre dalla

coda e l‟indice last l‟ultimo elemento arrivato. Se l‟indice last è inferiore all‟indice front, si ha

la coda vuota. Inizialmente, l‟indice last è posto a -1 e l‟indice front a 0. Quando l‟indice last

raggiunge la fine dell‟array, è necessaria una traslazione all‟indietro di tutti gli elementi della

coda.

3 4 9 5 1 7

front last

const int D=100 ;



struct coda

{

int front ; //indice elemento front

int last ; //indice elemento ultimo

vettore elementi; //elementi coda

};


coda CreaCoda ()

{

coda c;

c.last=-1;

c.front=0;

return c;

}

elemento Front(coda c)

{

if (c.last<c.front) cout<<”Coda vuota”;

else return c.elementi[c.front];

}



void Push(elemento x, coda & c)

{

if (c.last==D-1 && c.front==0)

cout<<”Coda piena”;

else

{

if (c.last==D-1) //traslazione

{

for (int i=c.front;i<=c.last;i++)

c.elementi[i-c.front]=c.elementi[i];

c.last=c.last-c.front;

c.front=0;

}

c.elementi[c.last+1]=x;

c.last++;

}

}

void Pop(coda & c)

{

if (c.last<c.front) cout<<”Coda vuota”;

else c.front++;

}

bool CodaVuota(coda c)

{

return (c.last<c.front);

}

Le operazioni primitive per le code appena viste hanno un tempo di esecuzione costante,

tranne l‟operazione Push che nel caso peggiore della traslazione dell‟array ha un tempo

lineare.



Seconda rappresentazione con array (gestione circolare)

Questa seconda rappresentazione con array è una variante della precedente in cui, se l‟indice

last raggiunge la fine dell‟array, si prosegue ad inserire i nuovi elementi ricominciando

dall‟inizio dell‟array. Si ha pertanto una cosiddetta gestione circolare dell‟array senza

ricorrere a traslazioni. Il vantaggio è che l‟operazione Push è sempre eseguita in tempo

costante. Di conseguenza non possiamo effettuare il test di coda vuota confrontando gli indici

last e front. Per semplificare leggermente la gestione degli indici, in questa rappresentazione

poniamo l‟indice last alla prima posizione libera dell‟array dove effettuare la Push. La

condizione in cui gli indici last e front coincidono può corrispondere sia alla condizione di

coda vuota che alla condizione di coda piena. L‟ambiguità può essere risolta con

l‟introduzione di un campo booleano nella struttura dati che indica il caso di coda vuota. .

La due figure seguenti illustrano due possibili situazioni all‟interno dell‟array gestito in modo

circolare:

3 4 9 5 1 7

front last

3 4 9 51 7

frontlast

const int D=100 ;



struct coda

{

int front ; //indice elemento front

int last ; //indice dopo elemento ultimo

bool vuota; //coda vuota

vettore elementi; //elementi coda

};




coda CreaCoda ()

{

coda c;

c.last=0;

c.front=0;

c.vuota=true;

return c;

}


{

if (c.vuota) cout<<”Coda vuota”;

else return c.elementi[c.front];

}


{

if (c.last==c.front && !c.vuota)

cout<<”Coda piena”;

else

{

c.elementi[c.last]=x;

c.last=(c.last+1)%D;

c.vuota=false;

}

}

void Pop(coda & c)

{

if (c.vuota) cout<<”Coda vuota”;

else

{

c.front=(c.front+1)%D;

if (c.front==c.last) c.vuota=true;

}

}


{

return (c.vuota);

}



Rappresentazione con liste collegate

Nella rappresentazione con liste collegate, eseguiamo l‟operazione Push alla fine della lista e

l‟operazione Pop all‟inizio della lista dato che in una lista è più semplice togliere un elemento

all‟inizio che alla fine.

9 5 1 7

coda

front

last

typedef int elemento;

struct record

{

elemento valore;

record* succ;

};

typedef record* precord;

struct coda

{

precord front;

precord last;

};


coda CreaCoda ()

{

coda c;

c.last=NULL;

c.front=NULL;

return c;

}


{

if (c.front==NULL) cout<<”Coda vuota”;

else return c.front->valore;

}


{

precord paux=new record;

paux->valore=x;

paux->succ=NULL;

if (c.last==NULL)

{

c.last=paux ;



c.front=paux ;

}

else

{

c.last->succ=paux;

c.last=paux ;

}

}

void Pop(coda & c)

{

if (c.front==NULL) cout<<”Coda vuota”;

else

{

if (c.front==c.last) //un solo elemento

{

delete c.front;

c.front=NULL;

c.last=NULL;

}

else

{

precord paux=c.front;

c.front=c.front->succ;

delete paux ;

}

}

}


{

return (c.front==NULL);

}



Alberi

Le liste, le pile e le code sono strutture dati sequenziali: i loro elementi rispettano un

ordinamento totale, dato che per ogni elemento è possibile identificare un predecessore e un

successore. Gli alberi rappresentano insiemi di elementi in cui è possibile stabilire un

ordinamento parziale: per ogni elemento è possibile stabilire un solo predecessore ma più

successori immediati.

Gli elementi di un albero si chiamano nodi. In un albero, esiste un solo nodo che non ha

predecessore, chiamato radice. Gli elementi che non hanno successori sono chiamati foglie

dell‟albero. I successori di un nodo sono anche chiamati figli, mentre il predecessore di un

nodo è anche chiamato genitore. Se applichiamo la proprietà transitiva alla relazione di

successione, possiamo definire un nodo discendente di un altro se esiste un percorso

nell‟albero che porta dal primo nodo al secondo. Viceversa, definiamo un nodo antenato di un

altro. Nodi figli dello stesso genitore sono fratelli. La profondità di un nodo è la lunghezza del

percorso dalla radice al nodo. L‟altezza di un nodo è la lunghezza del percorso più lungo dal

nodo a una foglia. La profondità (o altezza) di un albero è la lunghezza più lunga dalla radice

a una foglia. Un sottoalbero con radice in un certo nodo è l‟albero che si ottiene considerando

il nodo come radice e come elementi tutti i discendenti del nodo.

Un albero è di ordine k se ogni nodo ha al massimo k figli. Quanti nodi può avere un albero di

ordine k e profondità d? A profondità 0 c‟è solo la radice che può avere k figli a profondità 1.

A profondità d possiamo avere al massimo un numero di nodi:

2 31 dk k k k =0

di

i

k =1 1

1

dk

k

Il numero di nodi n di un albero di ordine k e profondità d può variare tra: 1 1

11

dkd n

k

Viceversa, un albero di ordine k con n nodi può avere un numero di livelli d compreso tra:

log ( )1 1 1k kn n d n

Gli alberi si dicono ordinati se esiste un ordinamento su ogni insieme di fratelli, per cui è

possibile stabilire per un nodo il figlio sinistro e per quest‟ultimo il fratello più a destra.

Gli alberi binari sono alberi ordinati di ordine 2. In un albero binario, ogni nodo può avere al

più due figli: un figlio sinistro e un figlio destro.

Rappresentare gli alberi in generale è piuttosto complicato perché è arbitrario il numero di

figli, mentre possiamo costruire facilmente delle rappresentazioni per alberi binari. Inoltre

queste rappresentazioni vanno bene anche per alberi di ordine k perché è possibile trasformare

un qualsiasi albero ordinato in un albero binario, con le seguenti regole:

1) L‟albero binario ha gli stessi nodi dell‟albero ordinato;

2) Un figlio più a sinistra nell‟albero ordinato corrisponde al figlio sinistro nell‟albero

binario;



3) Un fratello più a destra nell‟albero ordinato corrisponde al figlio destro nell‟albero

binario.

Per esempio, il seguente albero ternario, può essere mappato in un albero binario

corrispondente considerando gli archi tratteggiati in rosso al posto degli archi originari.

2

5 7

4

8 9

1

6

1110

3

sx

dx

dx dx

dx

dx

dx

sx sx

sx

L‟albero binario corrispondente può essere meglio visualizzato come segue:

2

5

7

4

8

9

1

6

11

10

3

sx

dx

dx

dx

dx

dx

dx

sx

sx

sx



Algoritmi di visita degli alberi.

Per visita di un albero, si intende l‟ordine in cui si esaminano gli elementi (nodi) presenti

nell‟albero. Dato che manca un ordine lineare tra gli elementi, si possono identificare strategie

diverse per percorrere tutti gli elementi. Una ricerca in profondità si effettua partendo dalla

radice e scendendo fino alla foglia più a sinistra; poi risalendo fino al primo percorso non

ispezionato e scendendo di nuovo in profondità. Una ricerca in larghezza, invece, prevede

che siano ispezionati tutti i nodi a profondità 1, poi quelli a profondità 2, etc.

Consideriamo la definizione ricorsiva di albero binario: un albero binario è costituito da una

radice, da un sottoalbero sinistro e un sottoalbero destro. La ricerca in profondità può essere

espressa in modo ricorsivo e ha tre varianti, visita in ordine anticipato, in ordine centrale, e in

ordine posticipato, a seconda se il nodo radice viene visitato prima, in mezzo, o dopo i

sottoalberi sinistro e destro. Osservate le seguenti funzioni ricorsive:

void VisitaOrdineAnticipato(albero t)

{

if (!Vuoto(t))

{

Accedi(t);

VisitaOrdineAnticipato(FiglioSx(t));

VisitaOrdineAnticipato(FiglioDx(t));

}

}

void VisitaOrdineCentrale(albero t)

{

if (!Vuoto(t))

{

VisitaOrdineCentrale(FiglioSx(t));

Accedi(t);

VisitaOrdineCentrale(FiglioDx(t));

}

}

void VisitaOrdinePosticipato(albero t)

{

if (!Vuoto(t))

{

VisitaOrdinePosticipato(FiglioSx(t));

VisitaOrdinePosticipato(FiglioDx(t));

Accedi(t);

}

}



Consideriamo ad esempio il seguente albero binario:

5

10 1

8

7 9

3

6 42

La ricerca in profondità percorre l‟albero secondo il percorso evidenziato in figura:

5

10 1

8

7 9

3

6 42

La visita in ordine anticipato esaminerà i nodi nell‟ordine seguente:

3 5 10 1 6 2 8 7 4 9

La visita in ordine centrale esaminerà i nodi come segue:

10 5 6 1 2 3 7 4 8 9

Infine, la visita in ordine posticipato corrisponderà alla sequenza:

10 6 2 1 5 4 7 9 8 3

La visita dell‟albero in larghezza, invece, produrrà la sequenza:

3 5 8 10 1 7 9 6 2 4

Gli algoritmi di visita degli alberi hanno un tempo lineare con il numero di nodi.



Le funzioni di cui sopra fanno uso di alcune operazioni elementari su alberi:

Vuoto: fa il test di albero vuoto;

Accedi: recupera il valore contenuto nel nodo radice;

FiglioSx: restituisce il sottoalbero sinistro;

FiglioDx: restituisce il sottoalbero destro.

Altre operazioni elementari che possiamo considerare sugli alberi sono:

Genitore: restituisce il sottoalbero di cui il nodo dato è figlio;

InserisciSottoAlberoSx: inserisce un sottoalbero sinistro;

InserisciSottoAlberoDx: inserisce un sottoalbero destro;

CancellaSottoAlberoSx: cancella un sottoalbero sinistro;

CancellaSottoAlberoDx: cancella un sottoalbero destro;

CreaFoglia: crea un nuovo nodo senza figli.

CancellaFoglia: dealloca un nodo.

La visita in larghezza di un albero può essere fatta con l‟aiuto di un‟altra struttura dati di

appoggio. In particolare, si può fare ricorrendo a una coda dove depositare i figli di ogni nodo

visitato. Nella coda ipotizziamo di memorizzare i puntatori ai nodi.

void VisitaLarghezza(albero t)

{

coda c=CreaCoda();

Push(t,c);

albero t1;

while (!CodaVuota(c))

{

t1= Front(c);

Accedi(t1);

if (!Vuoto(FiglioSx(t1)))

Push(FiglioSx(t1),c);

if (!Vuoto(FiglioDx(t1)))

Push(FiglioDx(t1),c);

Pop(c);

}

}

La seguente funzione può essere utile per inserire i valori di un albero:

bool conferma()

{

char ch;

do

cin>>ch;

while (ch!='S' && ch!='N');

return (ch=='S');

}



albero LeggiAlberoOrdineAnticipato()

{

int val;

cout<<"valore nodo";

cin>>val;

albero t=CreaFoglia(val);

cout<<"vuoi inserire figlio sx del nodo "<<val<<" ? (S/N) ";

if (conferma())

InserisciSottoAlberoSx(t, LeggiAlberoOrdineAnticipato());

else

InserisciSottoAlberoSx(t, NULL);

cout<<"vuoi inserire figlio dx del nodo "<<val<<" ? (S/N) ";

if (conferma())

InserisciSottoAlberoDx(t, LeggiAlberoOrdineAnticipato());

else

InserisciSottoAlberoDx(t, NULL);

return t;

}

Rappresentazioni degli alberi binari.

Una naturale rappresentazione per gli alberi binari è tramite una struttura dinamica in cui ogni

record possiede un campo valore e due campi puntatore al figlio sinistro e al figlio destro. Un

albero è individuato dal puntatore iniziale alla radice e un sottoalbero è vuoto quando il

corrispondente puntatore è posto a NULL.

3

5 8

1 7 9

typedef int elemento;

struct nodo

{ elemento valore; //valore di un nodo

nodo* sx; //puntatore al figlio sinistro

nodo* dx; //puntatore al figlio destro

};



Codifica delle operazioni elementari con questa rappresentazione.

int Accedi(albero t)

{

return t->valore;

}

albero FiglioSx(albero t)

{

return t->sx;

}

albero FiglioDx(albero t)

{

return t->dx;

}

bool Vuoto(albero t)

{

return (t==NULL);

}

albero CreaFoglia(int valore)

{

nodo* temp=new nodo;

temp->valore=valore;

temp->sx=NULL;

temp->dx=NULL;

return temp;

}

void CancellaFoglia(albero & t)

{

delete t;

t=NULL;

}

void InserisciSottoAlberoSx(albero pos_alb, albero s_alb)

{

pos_alb->sx=s_alb;

}

void InserisciSottoAlberoDx(albero pos_alb, albero s_alb)

{

pos_alb->dx=s_alb;

}

void CancellaSottoAlberoSx(albero pos_alb)

{

delete pos_alb->sx;

pos_alb->sx=NULL;

}



void CancellaSottoAlberoDx(albero pos_alb)

{

delete pos_alb->dx;

pos_alb->dx=NULL;

}

La funzione Genitore è complicata per questa rappresentazione. È l‟unica a non avere un

tempo di esecuzione costante, ma lineare nel numero di nodi. Una possibile implementazione

è la seguente, in cui il parametro “pos_alb” rappresenta il puntatore al nodo di cui bisogna

trovare il genitore, il parametro “t” rappresenta la radice dell‟albero, e il parametro “pos_gen”

conterrà il puntatore al genitore trovato. Non si può richiamare la funzione passando

“pos_alb” uguale alla radice “t”.

void Genitore(albero pos_alb, albero t, albero & pos_gen)

{

if (!Vuoto(t))

{

if (FiglioSx(t)==pos_alb || FiglioDx(t)==pos_alb)

pos_gen=t;

Genitore(pos_alb,FiglioSx(t),pos_gen);

Genitore(pos_alb,FiglioDx(t),pos_gen);

}

}

Per concludere si propone una funzione che dealloca un albero binario. La funzione si basa su

una visita in ordine posticipato, perché non si può deallocare un nodo genitore prima di aver

deallocato i suoi figli.

void CancellaAlbero(albero t)

{

if (!Vuoto(t))

{

CancellaAlbero(FiglioSx(t));

CancellaAlbero(FiglioDx(t));

CancellaFoglia(t);

}

}

Fondamenti di Informatica Prof. E. Clementini A.A. 2008-09ing.univaq.it/eliseo/dispense algoritmi e...

Documents

Transcript of Fondamenti di Informatica Prof. E. Clementini A.A. 2008-09ing.univaq.it/eliseo/dispense algoritmi e...