STRUTTURE DATI
AVANZATE
Abstract Data Types
Presentazione realizzata da:
Mario Capurso – http://info.bazarinfo.info
Altamura Michele
Doronzo Aldo
Lamacchia Claudio Maria
A.D.T. : Cosa sono?
Sono un insieme d’informazioni e algoritmi
che riflettono la realtà nel nostro computer e
quindi la rappresentano.
 Gli oggetti reali diventano oggetti virtuali
 Gli algoritmi reali diventano algoritmi virtuali

Come si rappresentano
Le strutture dati sono formate da tre livelli:
- CONCETTUALE ovvero come appare nel mondo
reale;
- LOGICO si occupa dell’elenco di proprietà e delle
procedure;
- FISICO si occupa di come vengono allocate le
proprietà nella memoria di un computer e di come
vengono realizzate le procedure nel computer.
A.D.T. Avanzate
Le strutture dati avanzate sono strutture che, per
essere realizzate hanno bisogno di strutture più
semplici (vettori, matrici, stack, code, ecc..).
Esempi sono:
 Il
grafo
 L’albero
 L’albero binario
A.D.T. Grafo
LIVELLO CONCETTUALE -1Il grafo rappresenta situazioni del mondo reale
che individua nodi collegati da archi.
Il grafo è identificabile con un insieme I. Per
ottenere tutte le coppie possibili si applica I x I.
Inoltre esiste un sotto-insieme di I chiamato R che
contiene tutti i nodi in collegamento (archi).
A.D.T. Grafo
LIVELLO CONCETTUALE -2Un grafo è formato da nodi.
Il collegamento tra due nodi è un arco.
Un cammino è una successione di archi, a condizione che
il nodo finale di un arco coincide con il nodo iniziale
dell’arco successivo.
Un grafo può essere orientato o non orientato:
nel primo esistono le direzioni, nel secondo no.
Un grafo inoltre può essere completo se, ogni suo nodo è
collegato con tutti gli altri.
A.D.T. Grafo
LIVELLO LOGICO -1New( ) crea un grafo vuoto
Destroy ( ) distrugge un grafo
AddNode( etichetta ) aggiunge un nodo con nome
“etichetta” e ne restituisce l’ ID
DeleteNode ( ID ) elimina il nodo ID-esimo e i suoi
archi
AddArc(ID1, ID2, p) inserisce un arco tra il nodo ID1
e il nodo ID2 e gli assegna il peso “p”
A.D.T. Grafo
LIVELLO LOGICO -2DeleteArc ( ID1, ID2 ) elimina l’arco tra il nodo ID1 e il
nodo ID2
IsEmpty ( ) restituisce vero se il Grafo è vuoto e falso se non lo è
IsFull( ) restituisce vero se il Grafo è pieno e falso se non lo è
IsArc ( ID1,ID2 ) controlla se esiste l’arco e se c’è, ne restituisce
il peso p
Cerca ( etichetta, trovato, ID ) controlla se nel Grafo esiste
un nodo con nome “etichetta” e, se c’è, ne restituisce l’ ID
A.D.T. Grafo
LIVELLO FISICO -1Il modello fisico che analizzeremo sarà quello in modalità
consecutiva. Questa implementazione risulta essere la più comoda
e veloce ma ha qualche problema nell’eliminazione dei nodi infatti,
nel vettore quando viene lanciato il sottoprogramma DeleteNode
il nodo, viene cancellato logicamente e, lo spazio non potrà più
essere utilizzato.
L’implementazione consecutiva sfrutta un vettore per contenere i
nodi del grafo e una matrice per contenere i pesi degli archi.
0
Ruvo
1
Barletta
2
Trani
3
Andria
0
1
0
1
3
8
45
2
3
2
19
11
A.D.T. Grafo
LIVELLO FISICO -2New()
t=0
La new() costruisce il grafo mettendo il
puntatore del vettore t a 0.
t=0
La destroy() distrugge il grafo
mettendo il puntatore del vettore t a 0.
Destroy()
IsFull()
se t = m allora
ritorna Vero
altrimenti
ritorna Falso
fine se
IsEmpty()
se t = 0 allora
ritorna Vero
altrimenti
ritorna Falso
fine se
La IsFull() riporta un valore vero se
il grafo è pieno, mentre falso se non
lo è.
La IsEmpty() riporta un valore vero
se il grafo è pieno, mentre falso se
non lo è.
A.D.T. Grafo
LIVELLO FISICO -3t  AddNode(s)
se non IsFull() allora
t=t+1
v(t)=s
ritorna t
fine se
Se il grafo non è pieno l’ AddNode(s)
prima incrementa la posizione e poi
assegna al vettore l’etichetta s e riporta
l’ID
DeleteNode(id)
se 1<=id<=t allora
v(id)=""
per i da 1 a t
mat(id,i)=0
mat(i,id)=0
fine per i
fine se
La DeleteNode(id), dopo aver
controllato che l’ID si trova fra 1 e t,
cancella l’etichetta del nodo e i suoi
relativi archi.
p  IsArc(id1,id2)
se 1<=id1<=t e 1<=id2<=t allora
ritorna mat(id1,id2)
fine se
La IsArc(id1,id2), riporta indietro il
peso che c’è fra due nodi, dopo aver
controllato che gli ID sono compresi
fra 1 e t.
A.D.T. Grafo
LIVELLO FISICO -4AddArc(id1,id2,p)
se 1<=id1<=t e 1<=id2<=t allora
mat(id1,id2)=p
fine se
La AddArc(id1,id2,p) aggiunge il peso
p fra due nodi dopo aver controllato
che i due nodi sono compresi fra 1 e t
DeleteArc(id1,id2)
se 1<=id1<=t e 1<=id2<=t allora
mat(id1,id2)=0
fine se
La DeleteArc(id1,id2) cancella il peso
dell’arco che c’è fra due nodi dopo aver
controllato che l’ID si trova fra 1 e t
Cerca(s,trovato,id)
trovato=Falso
per i da 1 a t
se v(i)=s allora
trovato=Vero
id=i
ritorna
fine se
fine per i
ritorna
La Cerca(s,trovato,id) riporta indietro
l’ID del nodo. C’è un ciclo che
confronta l’ID da cercare con tutti gli
altri id del vettore, e se viene trovato ne
riporta l’ID.
A.D.T. Grafo
LIVELLO FISICO -5Algoritmo di Moore – Bellman - D'Esopo
Per i da 1 a n
dist( i ) = +infinito
prec( i ) = -1
Fine per i
Push( l )
dist( l ) = 0
Mentre non IsEmpty( )
Pop( u )
Per ogni Arco(u , v)
newdist = dist( u )+p( u , v )
Se newdist<dist( v ) allora
dist( v ) = newdist
prec( v )=u
Push( v )
Fine se
Fine per
Fine mentre
L’algoritmo di Moore – Bellman D'Esopo serve per calcolare il
percorso minimo da un nodo l a
tutti gli altri nodi del grafo.
Inizzialmente l’algoritmo pone il
vettore Dist( ) a infinito e il
vettore Prec ( ) a – 1. Subito dopo
mette nello stack l e pone Dist ( l
) a zero. A questo punto
incomincia un ciclo mentre lo
stack non è vuoto: viene fatto il
pop di u e per ogni arco ( u , v )
viene calcolata la nuova distanza
e se è minore di Dist (v) la nuova
distanza è Dist ( v ) u diveta Prec
( v ) e si inserisce nello stack v.
A.D.T. Albero
LIVELLO CONCETTUALE -1Un albero è un caso particolare di grafo in cui esiste un
nodo detto radice che, se eliminato divide il grafo in n
sottografi disgiunti, ognuno dei quali è un albero.
Un albero è un grafo connesso e senza cicli.
-Un grafo si dice connesso se e solo se per ogni x,y
elemento di I esiste almeno un cammino che incomincia da
x e finisce alla y.
-Si dice ciclo una successione di archi a1, a2,…,an dove, il
nodo iniziale e il nodo finale coincidono.
Un albero è un grafo in cui per ogni coppia x , y elemento
di I, esiste uno e un solo cammino che li unisce.
A.D.T. Albero
LIVELLO LOGICO -1New( ) crea un albero vuoto
Destroy ( ) distrugge un albero
p  AddNode( s ) aggiunge un nodo con nome
“etichetta” e ne restituisce l’ ID
DeleteNode ( p ) elimina il nodo che si trova
all’indirizzo si memoria p
AddSon(px, py) aggiunge un figlio concatenandolo in
coda ai fratelli
A.D.T. Albero
LIVELLO LOGICO -2AddBro(px, py) aggiunge un padre fra i nodi agli
indirizzi di memoria px e py
DeleteSon(px, py) elimina un figlio
DeleteBro(px, py) elimina il padre
DeepFirstSearch(chiave, r) effettua una ricerca per
profondità
BreadthFirstSearch(chiave, r) effettua una ricerca
per livelli
A.D.T. Albero
LIVELLO FISICO -1Il modello fisico che analizzeremo sarà quello in modalità non
consecutiva. Questa implementazione risulta essere la più comoda
perché i suoi algoritmi lavoreranno utlizzando non più vettori e
matrici ma i puntatori, quindi sugli indirizzi di memoria.
L’implementazione non consecutiva sfrutta la memoria RAM per
contenere i nodi allocati dell’albero.
Giuseppe
Giuseppe
Info
Laura
Michele
Luca
Michele
Luca
Marco
Luigi
Laura
Sergio
Luigi
Marco
SonLink
[albero nella realtà]
Sergio
[albero nel computer]
BroLink
A.D.T. Albero
LIVELLO FISICO -2p  AddNode(s)
p=allocanodo
p.info=s
p.son=p.bro=NULL
ritorna p
La AddNode(s) aggiunge un nodo
allocandolo, prima pone l’etichetta
uguale alla parte info dell nodo, e poi fa
puntare a terra i link SonLink e
BroLink perché non collegati.
DeleteNode(p)
se p=NULL allora ritorna
se p.son=NULL e p.bro=NULL allora
libera p
fine se
La DeleteNode(id), dopo aver
controllato che p non punti a terra
libera il nodo che c’è fra il padre e il
figlio.
AddSon(px,py)
se px=NULL o py=NULL allora
ritorna
py.bro=px.son
px.son=py
La AddSon(px,py), dopo aver
controllato che px e py non puntino a
terra, aggiunge un figlio
concatenandolo in coda ai fratelli.
AddBro(px,py)
se px=NULL o py=NULL allora
ritorna
La AddBro(px,py), dopo aver
controllato che px e py non puntino a
terra, aggiunge un padre al quale
A.D.T. Albero
LIVELLO FISICO -3DeleteSon(px,py)
se px=NULL o py=NULL allora ritorna
prec=px
p=px.son
se p=py allora
prec.son=p.bro
ritorna
fine se
mentre p<>NULL
se p=py allora
prec.bro=p.bro
ritorna
altrimenti
prec=p
p=p.bro
fine se
fine mentre
La DeleteSon(px, py) elimina un figlio. Nell
algoritmo possiamo notare un ciclo in cui
viene cercato il figlio da eliminare.
DeleteBro(px,py)
se px=NULL o py=NULL allora ritorna
prec=px
p=px.bro
mentre p<>NULL
se p=py allora
prec.bro=p.bro
ritorna
altrimenti
prec=p
p=p.bro
fine se
fine mentre
La DeleteBro(px,py) elimina il padre dall’
albero. Ovviamente il padre non potrà essere
eliminato se ha dei figli.
A.D.T. Albero
LIVELLO LOGICO -1New( ) crea un albero vuoto
Destroy ( ) distrugge un albero
AddNode( s ) aggiunge un nodo con nome
“etichetta” e ne restituisce l’ ID
DeleteNode ( ID ) elimina il nodo ID-esimo e i suoi
archi
AddArc(ID1, ID2, p) inserisce un arco tra il nodo ID1
e il nodo ID2 e gli assegna il peso “p”
A.D.T. Albero
ALGORITMI DI RICERCA NELL’ALBERO -1Algoritmo di ricerca per profondità
DeepFirstSearch(chiave,r)
se r=NULL allora ritorna NULL
se r.info=chiave allora ritorna r
cs=DeepFirstSearch(chiave,r.firstson)
se cs<>NULL allora
ritorna cs
altrimenti
ritorna DeepFirstSearch(chiave,r.nextbro)
fine se
Quest’algoritmo richiede in
input la chiave (quello che si
vuole trovare), e l’indirizzo
della radice (r). All’inizio
controlla l’esistenza
dell’indirizzo e in caso
affermativo continua. A
questo punto si controlla se
nella radice c’è la chiave e se
c’è ne riporta l’indirizzo
altrimenti chiama se stesso
ma questa volta passandogli
il figlio. Se non trova neanche
nei figli allora ripete la ricerca
nei fratelli.
A.D.T. Albero
ALGORITMI DI RICERCA NELL’ALBERO -2Algoritmo di ricerca per larghezza o livelli
BreadthFirstSearch(chiave,r)
se r=NULL allora ritorna NULL
Enq(r)
ripeti mentre non isempty()
Deq(r)
se r.info=chiave allora ritorna r
ScandisciFigli(r)
fine ripeti
ScandisciFigli(r)
p=r.firstson
mentrep<>NULL
Enq(p)
p=p.nextbro
fine mentre
Quest’algoritmo richiede in input la
chiave (quello che si vuole trovare), e
l’indirizzo della radice (r). All’inizio
controlla l’esistenza dell’indirizzo e in
caso affermativo continua mettendo in
coda r. A questo punto incomincia un
ciclo mentre la coda non è vuota: per
prima cosa si estrae il primo elemento
dalla coda e lo confronta con la chiave e,
in caso affermativo ne riporta l’indirizzo
altrimenti chiama la procedura
ScandisciFigli(r) che non fa altro che
mettere in coda tutti i figli. Una volta
messi in coda l’algoritmo principale li
ripesca e li confronta con la chiave e se
non li trova procede scendendo di livello
e ripetendo la stessa procedura descritta.
A.D.T. Albero Binario
LIVELLO CONCETTUALE -1-
Un albero binario è un albero che ha
una radice e massimo due figli.
a
b
d
c
e
f
A.D.T. Albero Binario
RAPPRESENTAZIONE MODALITA NON CONSECUTIVA
DELL' ALBERO BINARIO -1La rappresentazione più usata per l'albero binario in
modalità non consecutiva è la seguente:
L.Link
Link Sinistro
Info
R.Link
Link Destro
A.D.T. Albero Binario
LIVELLO LOGICO -1-
New( ) crea un albero binario vuoto
Destroy ( ) distrugge un albero binario
AddNode( s ) aggiunge un nodo all'albero binario
DeleteNode ( p ) elimina il nodo solo se si è certi
che non abbia figli
AddArcSx(Px,Py) inserisce un arco a sinistra tra
due nodi
A.D.T. Albero Binario
LIVELLO LOGICO -2-
AddArcDx(Px,Py) inserisce un arco a destra tra
due nodi
DeleteArcSx(Px,Py) cancella un arco a sinistra
tra due nodi
DeleteArcDx(Px,Py) cancella un arco a destra
tra due nodi
IsArc(Px,Py) controlla se esiste l'arco e se lo trova
riporta un valore vero altrimenti falso
A.D.T. Albero Binario
LIVELLO FISICO -1New()
p = NULL
La new() costruisce l'albero binario
mettendo il puntatore p a null.
Destroy()
p = NULL
La destroy() distrugge l''albero binario
mettendo il puntatore p a null.
IsFull()
La IsFull() ritorna sempre Falso
perchè si suppone che la RAM non
si riempia mai, ma non sarebbe una
cattiva idea realizzarne una che
funzioni davvero.
ritorna Falso
IsEmpty()
se p = NULL allora
ritorna Vero
altrimenti
ritorna Falso
fine se
La IsEmpty() riporta un valore vero
se il puntatore p è a terra, mentre
falso se non lo è.
A.D.T. Albero Binario
LIVELLO FISICO -2p <-- AddNode(s)
p=allocanodo
p.info=s
p.sx=p.dx=NULL
ritorna p
DeleteNode(p)
se p=NULL allora ritorna
se p.sx=NULL e p.dx=NULL allora
libera p
fine se
Vero o Falso <-- IsArc(px,py)
se px=NULL o py=NULL allora ritorna
se px.sx=py o px.dx=py allora
ritorna Vero
altrimenti
ritorna Falso
fine se
L’AddNode costruisce il nodo dove alla
radice assegna il valore s e al link
sinistro e destro il assegna il valore
NULL
Se il puntatore ha valore NULL allora
ritorna altrimenti se il puntatore sinistro
e quello destro hanno valore NULL, il
nodo può essere cancellato.
La IsArc(px,py) riporta un valore che
può essere vero o falso. Se px e Py
hanno valore NULL allora ritorna,
altrimenti se il link sinistro e destro
hanno valore Py, esiste l’arco e quindi
riporta un valore vero altrimenti falso.
A.D.T. Albero Binario
LIVELLO FISICO -3AddArcSx(px,py)
se px=NULL o py=NULL allora ritorna
se px.sx=NULL allora
px.sx=py
fine se
AddArcDx(px,py)
se px=NULL o py=NULL allora ritorna
se px.dx=NULL allora
px.dx=py
fine se
DeleteArcSx(px,py)
se px=NULL o py=NULL allora ritorna
se px.sx=py allora
px.sx=NULL
fine se
DeleteArcDx(px,py)
se px=NULL o py=NULL allora
ritorna
se px.dx=py allora
px.dx=NULL
fine se
L' AddArcSx(px,py) controlla se px o py
hanno valore NULL allora ritorna
altrimenti se il link sinistro ha valore
NULL assegna il valore py
L' AddArcDx(px,py) controlla se px o py
hanno valore NULL allora ritorna
altrimenti se il link destro ha valore NULL
assegna il valore py
L' DeleteArcSx(px,py) controlla se px o
py hanno valore NULL allora ritorna,
altrimenti se il link sinistro ha valore py
assegna il valore NULL al link sinistro
L' DeleteArcDx(px,py) controlla se px o
py hanno valore NULL allora ritorna,
altrimenti se il link destro ha valore py
assegna il valore NULL al link destro
A.D.T. Albero Binario
VISITE ALL’ALBERO BINARIO
Visitare un albero significa passare da ogni nodo uno e una sola volta.
Tutti gli algoritmi di visita sono ricorsivi, i principali sono:
VisitaAnt(p)
se p=NULL allora ritorna
stampa: p.info
VisitaAnt(p.sx)
VisitaAnt(p.dx)
VisitaPost(p)
se p=NULL allora ritorna
VisitaPost(p.sx)
VisitaPost(p.dx)
stampa: p.info
VisitaSimm(p)
se p=NULL allora ritorna
VisitaSimm(p.sx)
stampa: p.info
VisitaSimm(p.dx)
Visitando l’albero in
maniera Anticipata
avremmo: A, B, D, E, C.
Visitando l’albero in
maniera Posticipata
avremmo: D, E, B, C, A.
Visitando l’albero in
maniera Simmetrica
avremmo:D, B, E, A, C
A
B
D
C
E