STRUTTURE DATI AVANZATE Abstract Data Types Presentazione realizzata da: Mario Capurso – Altamura...

STRUTTURE STRUTTURE DATI AVANZATEDATI AVANZATE

Abstract Data TypesAbstract Data Types

Presentazione Presentazione realizzata da:realizzata da:

Mario Capurso – Mario Capurso – http://info.bazarinfo.infohttp://info.bazarinfo.info

Altamura Michele Altamura Michele Doronzo AldoDoronzo Aldo

Lamacchia Claudio MariaLamacchia Claudio Maria

A.D.T. : Cosa sono?A.D.T. : Cosa sono?

Sono un insieme d’informazioni e algoritmi Sono un insieme d’informazioni e algoritmi che riflettono la realtà nel nostro computer che riflettono la realtà nel nostro computer e quindi la rappresentano.e quindi la rappresentano.

Gli oggetti reali diventano oggetti virtualiGli oggetti reali diventano oggetti virtuali Gli algoritmi reali diventano algoritmi Gli algoritmi reali diventano algoritmi

virtualivirtuali

Come si rappresentanoCome si rappresentano

Le strutture dati sono formate da tre livelli:Le strutture dati sono formate da tre livelli:

- - CONCETTUALECONCETTUALE ovvero come appare ovvero come appare nel mondo nel mondo reale;reale;

- - LOGICOLOGICO si occupa dell’elenco di si occupa dell’elenco di proprietà e delle proprietà e delle procedure;procedure;

- - FISICOFISICO si occupa di come vengono si occupa di come vengono allocate le allocate le proprietà nella memoria di proprietà nella memoria di un computer e di come un computer e di come vengono vengono realizzate le procedure nel computer.realizzate le procedure nel computer.

A.D.T. AvanzateA.D.T. Avanzate

Le strutture dati avanzate sono Le strutture dati avanzate sono strutture che, per essere realizzate strutture che, per essere realizzate hanno bisogno di strutture più semplici hanno bisogno di strutture più semplici (vettori, matrici, stack, code, ecc..).(vettori, matrici, stack, code, ecc..).

Esempi sono:Esempi sono:Il grafoIl grafoL’alberoL’alberoL’albero binarioL’albero binario

A.D.T. GrafoA.D.T. Grafo

LIVELLO CONCETTUALE -1-LIVELLO CONCETTUALE -1-

Il Il grafografo rappresenta situazioni del mondo rappresenta situazioni del mondo reale che individua nodi collegati da archi.reale che individua nodi collegati da archi.

Il grafo è identificabile con un insieme Il grafo è identificabile con un insieme II. . Per ottenere tutte le coppie possibili si Per ottenere tutte le coppie possibili si

applica applica I x II x I..

Inoltre esiste un sotto-insieme di Inoltre esiste un sotto-insieme di II chiamato chiamato RR che contiene tutti i nodi in collegamento che contiene tutti i nodi in collegamento

((archiarchi). ).


LIVELLO CONCETTUALE -2-LIVELLO CONCETTUALE -2-Un grafo è formato da Un grafo è formato da nodinodi..

Il collegamento tra due nodi è un Il collegamento tra due nodi è un arcoarco..

Un Un camminocammino è una successione di archi, a è una successione di archi, a condizione che il nodo finale di un arco condizione che il nodo finale di un arco coincide con il nodo iniziale dell’arco coincide con il nodo iniziale dell’arco

successivo.successivo.

Un grafo può essere Un grafo può essere orientatoorientato o o non non orientatoorientato::

nel primo esistono le direzioni, nel secondo no.nel primo esistono le direzioni, nel secondo no.

Un grafo inoltre può essere Un grafo inoltre può essere completocompleto se, ogni se, ogni suo nodo è collegato con tutti gli altri.suo nodo è collegato con tutti gli altri.

A.D.T. GrafoA.D.T. GrafoLIVELLO LOGICO -1-LIVELLO LOGICO -1-

New( )New( ) crea un grafo vuoto crea un grafo vuotoDestroy ( )Destroy ( ) distrugge un grafo distrugge un grafoAddNode( etichetta )AddNode( etichetta ) aggiunge un nodo aggiunge un nodo

con nomecon nome““etichetta” e ne restituisce l’ ID etichetta” e ne restituisce l’ ID

DeleteNode ( ID )DeleteNode ( ID ) elimina il nodo ID-esimo elimina il nodo ID-esimo e i suoi archie i suoi archi

AddArc(ID1, ID2, p)AddArc(ID1, ID2, p) inserisce un arco tra il inserisce un arco tra il nodo ID1 e il nodo ID2 e gli assegna il peso nodo ID1 e il nodo ID2 e gli assegna il peso “p” “p”

A.D.T. GrafoA.D.T. GrafoLIVELLO LOGICO -2-LIVELLO LOGICO -2-

DeleteArc ( ID1, ID2 )DeleteArc ( ID1, ID2 ) elimina l’arco tra il elimina l’arco tra il nodo ID1 e il nodo ID2nodo ID1 e il nodo ID2

IsEmpty ( )IsEmpty ( ) restituisce vero se il Grafo è vuoto restituisce vero se il Grafo è vuoto e falso se non lo èe falso se non lo è

IsFull( )IsFull( ) restituisce vero se il Grafo è pieno e restituisce vero se il Grafo è pieno e falso se non lo èfalso se non lo è

IsArc ( ID1,ID2 )IsArc ( ID1,ID2 ) controlla se esiste l’arco e se controlla se esiste l’arco e se c’è, ne restituisce il peso p c’è, ne restituisce il peso p

Cerca ( etichetta, trovato, ID )Cerca ( etichetta, trovato, ID ) controlla se controlla se nel Grafo esiste un nodo con nome “etichetta” nel Grafo esiste un nodo con nome “etichetta” e, se c’è, ne restituisce l’ IDe, se c’è, ne restituisce l’ ID

A.D.T. GrafoA.D.T. GrafoLIVELLO FISICO -LIVELLO FISICO -

1-1-Il 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.

00 RuvoRuvo

11 BarlettBarlettaa

22 TraniTrani

33 AndriaAndria

00 11 22 33

00 88

11 4455

22 1199

33 1111


New()t = 0

La new() costruisce il grafo mettendo il puntatore del vettore t a 0.

Destroy()t = 0

La destroy() distrugge il grafo mettendo il puntatore del vettore t a 0.

IsFull()se t = m allora

ritorna Veroaltrimenti

ritorna Falsofine se

La IsFull() riporta un valore vero se il grafo è pieno, mentre falso se non lo è.

IsEmpty()se t = 0 allora

ritorna Veroaltrimenti

ritorna Falsofine se

La IsEmpty() riporta un valore vero se il grafo è pieno, mentre falso se non lo è.

LIVELLO FISICO -LIVELLO FISICO -2-2-


t AddNode(s)se non IsFull() allora

t=t+1v(t)=sritorna 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)=0fine 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 alloraritorna

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.



AddArc(id1,id2,p)se 1<=id1<=t e

1<=id2<=t alloramat(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 alloramat(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=Falsoper i da 1 a t

se v(i)=s allora

trovato=Veroid=iritorna

fine sefine per iritorna

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.



Algoritmo di Moore – Bellman - D'EsopoAlgoritmo di Moore – Bellman - D'Esopo

Per i da 1 a ndist( i ) = +infinitoprec( i ) = -1

Fine per iPush( l )dist( l ) = 0Mentre 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 )=uPush( v )

Fine seFine per

Fine mentre

L’algoritmo di 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 A.D.T. Albero LIVELLO CONCETTUALE -1-LIVELLO CONCETTUALE -1-

Un albero è un caso particolare di grafo in cui Un albero è un caso particolare di grafo in cui esiste un nodo detto radice che, se eliminato esiste un nodo detto radice che, se eliminato divide il grafo in n sottografi disgiunti, ognuno divide il grafo in n sottografi disgiunti, ognuno dei quali è un albero.dei quali è un albero.

Un albero è un grafo connesso e senza cicli.Un albero è un grafo connesso e senza cicli.-Un grafo si dice connesso se e solo se per ogni x,y -Un grafo si dice connesso se e solo se per ogni x,y elemento di I esiste almeno un cammino che elemento di I esiste almeno un cammino che incomincia da incomincia da x e finisce alla y.x e finisce alla y.-Si dice ciclo una successione di archi a1, a2,…,an -Si dice ciclo una successione di archi a1, a2,…,an dove, il dove, il nodo iniziale e il nodo finale coincidono.nodo iniziale e il nodo finale coincidono.

Un albero è un grafo in cui per ogni coppia x , y Un albero è un grafo in cui per ogni coppia x , y elemento di I, esiste uno e un solo cammino che elemento di I, esiste uno e un solo cammino che li unisce.li unisce.

A.D.T. Albero A.D.T. Albero LIVELLO LOGICO -1-LIVELLO LOGICO -1-

New( )New( ) crea un albero vuoto crea un albero vuotoDestroy ( )Destroy ( ) distrugge un albero distrugge un albero p p AddNode( s ) AddNode( s ) aggiunge un nodo aggiunge un nodo

con nomecon nome““etichetta” e ne restituisce l’ ID etichetta” e ne restituisce l’ ID

DeleteNode ( p )DeleteNode ( p ) elimina il nodo che si elimina il nodo che si trova all’indirizzo si memoria ptrova all’indirizzo si memoria p

AddSon(px, py)AddSon(px, py) aggiunge un figlio aggiunge un figlio concatenandolo in coda ai fratelliconcatenandolo in coda ai fratelli

A.D.T. Albero A.D.T. Albero

LIVELLO LOGICO -2-LIVELLO LOGICO -2-AddBro(px, py)AddBro(px, py) aggiunge un padre fra aggiunge un padre fra

i nodi agli indirizzi di memoria px e i nodi agli indirizzi di memoria px e py py

DeleteSon(px, py)DeleteSon(px, py) elimina un figlio elimina un figlio DeleteBro(px, py)DeleteBro(px, py) elimina il padre elimina il padre DeepFirstSearch(chiave, r) DeepFirstSearch(chiave, r) effettua effettua

una ricerca per profonditàuna ricerca per profonditàBreadthFirstSearch(chiave, r) BreadthFirstSearch(chiave, r)

effettua una ricerca per livellieffettua una ricerca per livelli

A.D.T. AlberoA.D.T. AlberoLIVELLO FISICO -LIVELLO FISICO -

1-1-Il 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

Michele Luca

Laura

MarcoLuigi

Giuseppe

Laura

Luca

Michele

Marco

Luigi

Sergio

Sergio[albero nella

realtà][albero nel computer]

SonLinSonLinkk

InfoInfo BroLinBroLinkk

A.D.T. AlberoA.D.T. Albero

p AddNode(s)p=allocanodop.info=sp.son=p.bro=NULLritorna 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 ritornase p.son=NULL e p.bro=NULL

alloralibera 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 ritornapy.bro=px.sonpx.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 ritornapx.bro=px.bropx.bro=py

La AddBro(px,py), dopo aver controllato che px e py non puntino a terra, aggiunge un padre al quale saranno concatenati i suoi figli.


A.D.T. AlberoA.D.T. Albero

DeleteSon(px,py)se px=NULL o py=NULL allora se px=NULL o py=NULL allora

ritornaritorna

prec=pxprec=px

p=px.sonp=px.son

se p=py allorase p=py allora

prec.son=p.broprec.son=p.bro

ritornaritorna

fine sefine se

mentre p<>NULLmentre p<>NULL


prec.bro=p.broprec.bro=p.bro

ritornaritorna

altrimentialtrimenti

prec=pprec=p

p=p.brop=p.bro

fine sefine se

fine mentrefine mentre

DeleteBro(px,py)se px=NULL o py=NULL allora se px=NULL o py=NULL allora

ritornaritorna

prec=pxprec=px

p=px.brop=px.bro

mentre p<>NULLmentre p<>NULL


prec.bro=p.broprec.bro=p.bro

ritornaritorna


prec=pprec=p

p=p.brop=p.bro

fine sefine se

fine mentrefine mentre

La DeleteSon(px, py) elimina un figlio. Nell algoritmo possiamo notare un ciclo in cui viene cercato il figlio da eliminare.

La DeleteBro(px,py) elimina il padre dall’ albero. Ovviamente il padre non potrà essere eliminato se ha dei figli.


A.D.T. Albero A.D.T. Albero LIVELLO LOGICO -1-LIVELLO LOGICO -1-

New( )New( ) crea un albero vuoto crea un albero vuotoDestroy ( )Destroy ( ) distrugge un albero distrugge un albero AddNode( s )AddNode( s ) aggiunge un nodo con nome aggiunge un nodo con nome

““etichetta” e ne restituisce l’ ID etichetta” e ne restituisce l’ ID DeleteNode ( ID )DeleteNode ( ID ) elimina il nodo ID- elimina il nodo ID-

esimo e i suoi archiesimo e i suoi archiAddArc(ID1, ID2, p)AddArc(ID1, ID2, p) inserisce un arco tra inserisce un arco tra

il nodo ID1 e il nodo ID2 e gli assegna il il nodo ID1 e il nodo ID2 e gli assegna il peso “p” peso “p”

A.D.T. Albero A.D.T. Albero ALGORITMI DI RICERCA NELL’ALBERO -1-ALGORITMI DI RICERCA NELL’ALBERO -1-

Algoritmo 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 Quest’algoritmo richiede in input la richiede in input la chiave (quello che si chiave (quello che si vuole trovare), e vuole trovare), e l’indirizzo della radice l’indirizzo della radice (r). All’inizio controlla (r). All’inizio controlla l’esistenza l’esistenza dell’indirizzo e in caso dell’indirizzo e in caso affermativo continua. affermativo continua. A questo punto si A questo punto si controlla se nella controlla se nella radice c’è la chiave e radice c’è la chiave e se c’è ne riporta se c’è ne riporta l’indirizzo altrimenti l’indirizzo altrimenti chiama se stesso ma chiama se stesso ma questa volta questa volta passandogli il figlio. passandogli il figlio. Se non trova neanche Se non trova neanche nei figli allora ripete nei figli allora ripete la ricerca nei fratelli. la ricerca nei fratelli.

A.D.T. Albero A.D.T. Albero ALGORITMI DI RICERCA NELL’ALBERO -2-ALGORITMI DI RICERCA NELL’ALBERO -2-

Algoritmo 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 Quest’algoritmo richiede in input la chiave (quello che si input la chiave (quello che si vuole trovare), e l’indirizzo vuole trovare), e l’indirizzo della radice (r). All’inizio della radice (r). All’inizio controlla l’esistenza controlla l’esistenza dell’indirizzo e in caso dell’indirizzo e in caso affermativo continua mettendo affermativo continua mettendo in coda r. A questo punto in coda r. A questo punto incomincia un ciclo mentre la incomincia un ciclo mentre la coda non è vuota: per prima coda non è vuota: per prima cosa si estrae il primo elemento cosa si estrae il primo elemento dalla coda e lo confronta con la dalla coda e lo confronta con la chiave e, in caso affermativo ne chiave e, in caso affermativo ne riporta l’indirizzo altrimenti riporta l’indirizzo altrimenti chiama la procedura chiama la procedura ScandisciFigli(r) che non fa ScandisciFigli(r) che non fa altro che mettere in coda tutti i altro che mettere in coda tutti i figli. Una volta messi in coda figli. Una volta messi in coda l’algoritmo principale li ripesca l’algoritmo principale li ripesca e li confronta con la chiave e se e li confronta con la chiave e se non li trova procede scendendo non li trova procede scendendo di livello e ripetendo la stessa di livello e ripetendo la stessa procedura descritta.procedura descritta.

A.D.T. Albero BinarioA.D.T. Albero BinarioLIVELLO CONCETTUALE -1-LIVELLO CONCETTUALE -1-

Un albero binario è un Un albero binario è un albero che ha una radice e albero che ha una radice e

massimo due figli.massimo due figli.a

cb

fed

A.D.T. Albero BinarioA.D.T. Albero BinarioRAPPRESENTAZIONE MODALITA NON RAPPRESENTAZIONE MODALITA NON

CONSECUTIVA DELL' ALBERO BINARIO -1-CONSECUTIVA DELL' ALBERO BINARIO -1-

La rappresentazione più usata per l'albero La rappresentazione più usata per l'albero binario in modalità non consecutiva è la binario in modalità non consecutiva è la seguente:seguente:

InfoL.Link R.Link

Link Sinistro Link Destro

A.D.T. Albero BinarioA.D.T. Albero Binario

LIVELLO LOGICO -1-LIVELLO LOGICO -1-

New( )New( ) crea un albero binario vuoto crea un albero binario vuotoDestroy ( )Destroy ( ) distrugge un albero binario distrugge un albero binarioAddNode( s )AddNode( s ) aggiunge un nodo aggiunge un nodo

all'albero binarioall'albero binarioDeleteNode ( p )DeleteNode ( p ) elimina il nodo solo elimina il nodo solo

se si è certi che non abbia figlise si è certi che non abbia figliAddArcSx(Px,Py)AddArcSx(Px,Py) inserisce un arco a inserisce un arco a

sinistra tra due nodi sinistra tra due nodi


LIVELLO LOGICO -2-LIVELLO LOGICO -2-

AddArcDx(Px,Py)AddArcDx(Px,Py) inserisce un arco a inserisce un arco a destra tra due nodi destra tra due nodi

DeleteArcSx(Px,Py)DeleteArcSx(Px,Py) cancella un arco cancella un arco a sinistra tra due nodi a sinistra tra due nodi

DeleteArcDx(Px,Py)DeleteArcDx(Px,Py) cancella un cancella un arco a destra tra due nodi arco a destra tra due nodi

IsArc(Px,Py)IsArc(Px,Py) controlla se esiste controlla se esiste l'arco e se lo trova riporta un valore l'arco e se lo trova riporta un valore vero altrimenti falso vero altrimenti falso

A.D.T. Albero BinarioA.D.T. Albero BinarioLIVELLO FISICO -LIVELLO FISICO -

1-1-

La IsEmpty() riporta un valore vero se il puntatore p è a terra, mentre falso se non lo è.

IsEmpty()

se p = NULL alloraritorna Vero

altrimentiritorna Falso

fine se

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.

IsFull()

ritorna Falso

La destroy() distrugge l''albero binario mettendo il puntatore p a null.

Destroy()

p = NULL

La new() costruisce l'albero binario mettendo il puntatore p a null.

New()

p = NULL

A.D.T. Albero BinarioA.D.T. Albero BinarioLIVELLO FISICO -LIVELLO FISICO -

2-2-p <-- AddNode(s)p <-- AddNode(s)

p=allocanodop=allocanodo

p.info=sp.info=s

p.sx=p.dx=NULLp.sx=p.dx=NULL

ritorna pritorna p

L’AddNode costruisce il nodo L’AddNode costruisce il nodo dove alla radice assegna il dove alla radice assegna il valore s e al link sinistro e valore s e al link sinistro e destro il assegna il valore destro il assegna il valore NULLNULL

DeleteNode(p)DeleteNode(p)

se p=NULL allora ritornase p=NULL allora ritorna

se p.sx=NULL e p.dx=NULL se p.sx=NULL e p.dx=NULL alloraallora

libera plibera p

fine sefine se

Se il puntatore ha valore Se il puntatore ha valore NULL allora ritorna altrimenti NULL allora ritorna altrimenti se il puntatore sinistro e se il puntatore sinistro e quello destro hanno valore quello destro hanno valore NULL, il nodo può essere NULL, il nodo può essere cancellato.cancellato.

Vero o Falso <-- IsArc(px,py)Vero o Falso <-- IsArc(px,py)

se px=NULL o py=NULL allora se px=NULL o py=NULL allora ritornaritorna

se px.sx=py o px.dx=py allorase px.sx=py o px.dx=py allora

ritorna Veroritorna Vero


ritorna Falsoritorna Falso

fine sefine se

La IsArc(px,py) riporta un La IsArc(px,py) riporta un valore che può essere vero o valore che può essere vero o falso. Se px e Py hanno valore falso. Se px e Py hanno valore NULL allora ritorna, NULL allora ritorna, altrimenti se il link sinistro e altrimenti se il link sinistro e destro hanno valore Py, esiste destro hanno valore Py, esiste l’arco e quindi riporta un l’arco e quindi riporta un valore vero altrimenti falso.valore vero altrimenti falso.


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

DeleteArcSx(px,py) se px=NULL o py=NULL allora ritorna se px.sx=py allora px.sx=NULL fine seDeleteArcDx(px,py) se px=NULL o py=NULL allora ritorna se px.dx=py allora

px.dx=NULL fine se

LIVELLO FISICO -LIVELLO FISICO -3-3-AddArcSx(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

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 sinistroL' 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 A.D.T. Albero Binario VISITE ALL’ALBERO BINARIOVISITE ALL’ALBERO BINARIO

Visitare un albero significa passare da ogni nodo Visitare un albero significa passare da ogni nodo uno e una sola volta.uno e una sola volta.

Tutti gli algoritmi di visita sono ricorsivi, i Tutti gli algoritmi di visita sono ricorsivi, i principali sono:principali sono:

A

B C

D E

VisitaAnt(p)VisitaAnt(p)se p=NULL allora se p=NULL allora

ritornaritorna

stampa: p.infostampa: p.info

VisitaAnt(p.sx)VisitaAnt(p.sx)

VisitaAnt(p.dx)VisitaAnt(p.dx)

Visitando l’albero in Visitando l’albero in maniera Anticipata maniera Anticipata avremmo: A, B, D, avremmo: A, B, D,

E, C.E, C.

VisitaPost(p)VisitaPost(p)se p=NULL allora se p=NULL allora

ritornaritorna

VisitaPost(p.sx)VisitaPost(p.sx)

VisitaPost(p.dx)VisitaPost(p.dx)


Visitando l’albero in Visitando l’albero in maniera Posticipata maniera Posticipata avremmo: D, E, B, avremmo: D, E, B,

C, A.C, A.

VisitaSimm(p)VisitaSimm(p)se p=NULL allora se p=NULL allora

ritornaritorna

VisitaSimm(p.sx)VisitaSimm(p.sx)


VisitaSimm(p.dx)VisitaSimm(p.dx)

Visitando l’albero in Visitando l’albero in maniera maniera

Simmetrica Simmetrica avremmo:D, B, E, A, avremmo:D, B, E, A,

C C

STRUTTURE DATI AVANZATE Abstract Data Types Presentazione realizzata da: Mario Capurso – Altamura...

Documents

Transcript of STRUTTURE DATI AVANZATE Abstract Data Types Presentazione realizzata da: Mario Capurso – Altamura...