MODULO STRUTTURE DATI FONDAMENTALI:
Strutture dinamiche
classe 4° INDUSTRIALE ABACUS
Ud1 Strutture dati lineari
Tempi
-Liste semplicemente puntate
3h+3h lab
-Parallelo tra vettori e liste
1h
-Pile
-Code
Focus on
2h+2h lab
2h+ 2h lab
Ud2 Strutture dati non lineari
Tempi
-Alberi binari
4h+4h lab
-Alberi binari di ricerca
4h+4h lab
1
Ud1 Strutture dati lineari
Prerequisiti
Conoscenza e competenza della struttura dati di tipo
record, array, puntatori
Modularità dei programmi
Obiettivi
Conoscenza:
Saper riconosce e saper argomentare il concetto
fondamentale di lista dinamica e di conseguenza riconoscere
particolari liste che vengono gestite con tecnica LIFO e
FIFO.
Competenze:
Saper utilizzare semplici liste in linguaggio c++ su cui si
possono svolgere operazioni fondamentali di: creazione lista,
inserimento e ricerca ed estrazione.
Capacità:
Saper applicare in modo autonomo a un problema di diversa
natura la metodologia proposta, con la possibilità di risolvere
anche problemi interdisciplinari.
Strumenti:
Lavagna luminosa, lezione frontale e
laboratorio.
2
ALBERI BINARI
MOTIVAZIONE: Per raccogliere e gestire dinamicamente
insiemi di dati mantenendo anche la loro struttura gerarchica
3
Alberi: definizione
A
B
H
C
I
D
E
F
G
Un Albero radicato è un’insieme non vuoto di elementi detti NODI collegati tra loro
attraverso ARCHI in modo tale che:
Qualunque coppia di NODI è congiunta da un solo ARCO
Un Albero di N NODI contiene esattamente N-1 ARCHI
Rimuovendo un ARCO qualsiasi dell’albero si ottengono 2 Alberi
N.B. L’utilità degli ALBERI sta nel fatto che ciascun nodo può essere
ETICHETTATO ovvero può contenere una informazione.
4
Alberi: proprietà
A
B
H
C
I
D
E
F
G
Gli Alberi sono strutture dati non lineari ovvero ogni elemento ha un solo
predecessore ma, può avere più successori.
Nelle strutture dati lineari invece ciascun elemento ha un solo successore ed un
solo predecessore.
5
Alberi: proprietà
A
B
H
C
I
D
E
F
G
E’ uso comune parlare di Alberi in termini “genealogici” e riferendoci alla figura
diremo che:
A è padre di B e C così come C è padre di D, E e F ecc.
B è fratello di C cosi come H lo è di I ecc.
D, E, F e G sono discendenti di C ma anche di A
6
Alberi: come sono fatti?
RADICE
NODO INTERMEDIO
A
B
H
FOGLIE
C
I
D
E
F
SOTTOALBERO
G
 Esiste ed è unico un NODO detto RADICE che non discende da nessun altro
NODO e che ha priorità massima rispetto agli altri nodi
 Esistono NODI detti FOGLIE senza discendenti
 In ciascun NODO arriva un solo arco (fatta eccezione per la radice)
 Preso un qualunque NODO esso è sempre raggiungibile a partire dalla
RADICE e il percorso che si fa è detto CAMMINO
 Da un NODO intermedio (nè RADICE nè FOGLIA) è possibile raggiungere
almeno una FOGLIA
 Ogni NODO può essere considerato un SOTTOALBERO
7
Dall’esigenza di classificare NODI ed ALBERI seguono le seguenti definizioni:
Livello 1
A
B
H
C
I
D
Livello 2
E
F
G
Livello 3
Livello 4
•Si dice grado di un NODO il numero dei suoi sottoalberi
ESEMPIO: il GRADO di A e B è 2, quello di C è 3
•Si dice grado di un ALBERO il maggiore tra tutti i gradi dei suoi NODI
ESEMPIO: il GRADO dell’albero è 3
•Si dice livello di un NODO il numero di NODI attraversati da un cammino che parte
dalla radice e arriva al NODO stesso
ESEMPIO: il LIVELLO di A è 1, di B e C è 2, di H, I, D, E, F è 3
•Si dice altezza di un ALBERO la lunghezza del cammino più lungo esistente tra
RADICE e FOGLIA (numero di ARCHI che separano la RADICE dalla FOGLIA più
lontana)
8
ESEMPIO: l’ ALTEZZA dell’albero è 3
Gli Alberi Binari
A
B
D
C
E
F
G
H
Def. Un Albero Binario può essere l’albero binario vuoto, cioè senza nodi,
oppure è una coppia ordinata di alberi binari detti sottoalbero destro e
sottoalbero sinistro ai quali è associato un nodo detto radice. In un albero binario
per ciascun NODO si hanno al massimo due figli. Per cui si ha:
Albero binario vuoto
Def. Ricorsiva: Un Albero si dice binario se
Non ha nodi (è vuoto)
La radice ha al più due sottoalberi binari
A
A
B
B
C
9
Come si fa a “creare” la struttura di Albero Binario?
L’elemento generico dell’albero è un record che ha tre campi uno
informativo e gli altri due di tipo puntatore al sottoalbero sinistro e destro.
In C++
…
struct nodo{
char info;
NODO
info
fs fd
struct nodo * fs;
struct nodo * fd;
RADICE
};
struct nodo * radice =NULL;
10
Come si fa a “creare” la struttura di Albero Binario?
Vista la struttura ricorsiva dell’albero, anche il caricamento
di quest’ultimo avverrà in modo ricorsivo.
In C++
...
Void memorizza_anticipato (struct nodo * & r)
X
{Char x;
A
RADICE
Cin>>x;
If (x!=‘*’)
{ r= new (struct nodo);
r->info=x;
memorizza_ anticipato(r->fs);
memorizza_anticipato(r->fd);
}
else
r=NULL;
11
}
Il problema della visita di un
albero binario
La visita di un albero binario consiste nell’andare ad analizzare tutti i suoi
nodi una e una sola volta.
Esistono tre modalità di visita e sono tutte ricorsive:
X
• Visita in ordine anticipato ( NODO FS FD)
• Visita in ordine simmetrico (FS NODO FD)
• Visita in ordine posticipato (FS FD NODO)
12
Alberi: Metodi di attraversamento
IN ORDINE
ANTICIPATO
A
B
D
C
E
F
G
void visita_anticipato (struct nodo * r)
{ If (r!=NULL)
{ cout<< r->info; /* stampa il nodo visitato */
visita_ anticipato(r->fs);
visita_anticipato(r->fd);
}
else cout<< “ * “;
}
H
Simulazione di visita in ordine
anticipato
NODO FS FD=
=A FS FD=
=A B FS * C FS FD =
=A B D * * * C E *FD F * FD=
=A B D * * * C E * G * * F * H 13
**
Alberi: Metodi di attraversamento
IN ORDINE SIMMETRICO
A
B
D
C
E
F
G
void visita_simmetrica (struct nodo * r)
{ If (r!=NULL)
{visita_ simmetrica(r->fs);
cout<< r->info; /* stampa il nodo visitato */
visita_simmetrica(r->fd);
}
else cout<< “ * “;
}
H
Simulazione dell’ordine di visita
in ordine simmetrico
FS NODO FD=
=FS A FD=
=FS B * A FS C FD =
=* D * B * A * E FD C * F FD=
=* D * B * A * E * G * C * F *14H *
Alberi: Metodi di attraversamento
IN ORDINE POSTICIPATO
A
B
D
C
E
F
G
void visita_posticipato (struct nodo * r)
{ If (r!=NULL)
{ visita_ anticipato(r->fs);
visita_posticipato(r->fd);
cout<< r->info; /* stampa il nodo visitato */
}
else cout<< “ * “;
}
H
Simulazione dell’ordine di visita
in ordine posticipato
FS FD NODO=
=FS FD A=
=FS * B FS FD C A=
=* * D * B * FD E * FD F C A=
=* * D * B * * * G E * * * H 15
FCA
Gli alberi binari di ricerca: ABR
X
ABR
ABR
chiavi<x
chiavi>x
Definizione: Un albero binario di ricerca (ABR) e un albero binario soggetto ai
seguenti vincoli:
1. Il sottoalbero sinistro contiene solo dati minori della radice ed è, a sua volta,
un ABR;
2. Il sottoalbero destro contiene solo chiavi maggiori della radice ed è, a sua
volta, un ABR.
Il tipo di dato per la chiave può essere qualsiasi purché su di esso sia definita una
relazione d’ordine totale
N.B. Dalla definizione di discende che ogni sottoalbero di un ABR è a sua
volta un ABR
16
Gli alberi binari di ricerca
Proprietà
E
C
B
G
D
F
H
A
1. La visita in ordine simmetrico di un ABR produce le chiavi in modo ordinato
2. Si può usare un algoritmo di ricerca su un ABR simile a quello di ricerca
binaria. Per poter applicare tale algoritmo è necessario che ad ogni passo
vengano escluse la metà delle chiavi, ciò corrisponde a richiedere che l’ABR sia
bilanciato in altezza. Intuitivamente si chiede che non esista uno squilibrio fra le
altezze dei sottoalberi destro e sinistro di ciascun sottoalbero. L’albero in figura
è perfettamente bilanciato
3. Per inserire un nuovo elemento in un ABR esiste un solo modo che consente di
mantenere la struttura di ABR
4. Per cancellare un elemento si usa sostanzialmente una ricerca. Tale algoritmo
17
non garantisce che il nuovo ABR sia bilanciato.