Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B....
-
Upload
alba-ferrara -
Category
Documents
-
view
213 -
download
0
Transcript of Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B....
![Page 1: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/1.jpg)
Le Strutture Dati
M. Capurso con materiale di:G.Piccolo, A.Arcieri, LamacchiaF. Piccolo, B. Monterisihttp://info.bazarinfo.info
(Abstract Data Types)
![Page 2: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/2.jpg)
Ogni professione ha oggetti e operazioni di base
In qualsiasi professione, l’apprendista impara a riconoscere e manipolare gli oggetti fondamentali del mestiere.
L’apprendista idraulico impara a riconoscere e collegare rubinetti e tubi
L’apprendista architetto riconosce muri, archi e porte e ne impara caratteristiche fondamentali ed operazioni di base
Questo accade anche per l’informatico
![Page 3: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/3.jpg)
I tipi di dati astratti e la professione di informatico
Le strutture dati (o tipi di dati astratti) costituiscono patrimonio fondamentale della professione di informatico
Padroneggiarle equivale per l’informatico alla conoscenza di tubi e rubinetti per l’idraulico: non se ne può fare a meno.
![Page 4: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/4.jpg)
Una struttura dati è …
… un insieme di dati raggruppati e organizzati secondo uno schema ben definito.
In tali strutture nel computer c’è un barlume del mondo reale: sono informazioni e algoritmi che modellano ciò che avviene nella realtà.
Sono fotografie di oggetti del mondo reale, nel nostro computer
![Page 5: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/5.jpg)
Un esempio…
Una pila di libri può essere rappresentata con una struttura dati stack
Una fila di persone può essere rappresentata con una struttura dati coda
![Page 6: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/6.jpg)
Definizione Una Struttura Dati (o Abstract Data Type) è un un insieme di Informazioni ed insieme di Informazioni ed
Algoritmi cha rappresentano Algoritmi cha rappresentano nel computernel computer ( quindi in un universo virtuale) situazioni situazioni
ed oggetti presenti nella ed oggetti presenti nella realtà.realtà.
![Page 7: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/7.jpg)
Universo del Discorso e Tipi Prendiamo un universo che contiene tutti gli
oggetti del contesto(ciò di cui si parla). L’universo può essere suddiviso in
sottoinsiemi da un oracolo (detto tipo) che prende un elemento del discorso e porta un valore che può essere vero o falso.
L’insieme degli elementi dell’ universo per cui il predicato è vero si chiama classe.
![Page 8: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/8.jpg)
TipoSi definisce tipo un predicato che può essere Vero o Falso quando è applicato ad un elemento x dell’Universo del discorso.
Il tipo divide l’universo del discorso in due sottoinsiemi distinti : un sottoinsieme per cui il predicato (tipo) è vero, l’altro per cui il predicato è falso
![Page 9: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/9.jpg)
Esempio
Raffaello
Giotto
LeopardiDante
Pittore(Dante)=FalsoPittore(Leopardi)=FalsoPittore(Raffaello)=VeroPittore(Giotto)=Vero
Pittore è un tipo
Esso descrive la Classe dei Pittori
Classe dei Pittori
Universo del discorso
![Page 10: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/10.jpg)
Classi, Sottoclassi e Superclassi
Se A e B sono classi di U e … A è contenuto in B allora A si dice Sottoclasse di B… …e B si dice Superclasse di A
![Page 11: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/11.jpg)
Tipi, Oracoli e Stampi
Un tipo è un oracolo: non spiega il suo funzionamento né caratterizza gli oggetti prescelti
E se volessi invece caratterizzare gli oggetti con delle proprietà specifiche? Se volessi costruirli come dico io ?
Posso usare uno stampo
![Page 12: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/12.jpg)
Uno stampo è composto da
Un nome
Un elenco di Proprietà
Un elenco di Ricette
Stampo o Template
Uno stampo è un meccanismo per costruire oggetti
![Page 13: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/13.jpg)
Esempio di stampo
1. Stampo di: Pecorella (nome) Zampe
Testa
Coda
Nome
Proprietà
2.
3. Per_Belare: Ricetta per far sì che alla pressione del pancino la pecorella emetta un belato
![Page 14: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/14.jpg)
Le proprietà nello stampo hanno un valore Definizionale ( sono dei segnaposto) mentre nell’oggetto creato dallo stampo le proprietà hanno un valore Fattuale (assumono dei valori reali in un oggetto specifico)
Proprietà nello stampo
Nome =Bianchina
![Page 15: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/15.jpg)
Costruttore e distruttore
Devo assumere sempre presenti almeno due ricette: il costruttore ed il distruttore
Il costruttore costruisce un oggetto, mentre il distruttore lo distrugge
![Page 16: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/16.jpg)
Proprietà e ricette di oggetto
Le proprietà e le ricette di cui abbiamo parlato finora sono caratteristiche di ciascun oggetto e assumono valori che possono cambiare da oggetto ad oggetto
Nome =BianchinaNome =
Nerina
Beh
Beh
Muh
Muh
![Page 17: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/17.jpg)
Proprietà e ricette di classe
Posso però immaginare che esistano proprietà e ricette di classe, che cioè esistano una sola volta per tutta la classe
Raffaello
Giotto
Classe dei Pittori
Numero Pittori
Età media alla morte
![Page 18: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/18.jpg)
Se uso uno stampo come costruttore, posso produrre oggetti
La domanda “L’oggetto x è generato dallo stampo ?” può dare un valore vero o falso ed è quindi un predicato, cioè un tipo
Il tipo delimita la classe di tutti gli oggetti prodotti dallo stampo
Stampo, tipo e classe sono collegati
![Page 19: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/19.jpg)
Le strutture dati possono essere viste da tre punti di vista:
Modello concettuale: si parla delle situazioni reali modellate dalla struttura dati
Modello logico: si descrive l’ elenco della proprietà e delle ricette (metodi)
Modello fisico: ci si occupa dell’ allocazione delle proprietà nella memoria di un computer e della realizzazione delle ricette in un computer.
Tre punti di vista
![Page 20: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/20.jpg)
Le strutture dati più semplici
Tipi elementari Strutture ripetitive (vettori e matrici) Stack Coda Lista
![Page 21: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/21.jpg)
Tipi elementari
Sono presenti in tutti i linguaggi di programmazione in maniera nativa
Esempio: valori interi, reali, caratteri, logici, date
Sono i mattoni di base con cui costruire tutto il resto
![Page 22: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/22.jpg)
Tipi elementari: modello concettuale e logico
Modello concettuale: rappresentano oggetti del mondo reale caratterizzati da un solo valore
Esempio: una resistore, che sia caratterizzato solo con il valore intero della sua resistenza in Ohm
Modello logico New() Costruttore Destroy() Distruttore Get() Riporta il valore s Put(s) Assegna il valore s
![Page 23: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/23.jpg)
Tipi elementari: modello fisico Si assume che l’oggetto creato abbia una
proprietà nascosta b chiamata indirizzo base, che individui l’indirizzo del valore in memoria centrale
L’operatore di indirezione * accede al valore il cui indirizzo segue l’operatore
Get() Riporta *b
Put(s) *b=s
New() b=alloca()
Destroy() disalloca(b)
![Page 24: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/24.jpg)
Vettore: modello concettuale
Rappresenta oggetti del mondo reale caratterizzati da una successione lineare di valori tutti dello stesso tipo, in corrispondenza biunivoca con gli interi da un min ad un max
Esempio: un elenco di studenti, dal numero uno al numero ventiquattro
![Page 25: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/25.jpg)
Vettore: modello logico
New(min,max) costruttore
Destroy() distruttore
Getat(i) riporta il valore s alla posizione i
Putat(i,s) assegna il valore s alla posizione i
![Page 26: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/26.jpg)
Vettore: modello fisico Si assume che l’oggetto creato abbia una
proprietà nascosta b chiamata indirizzo base, che individui l’indirizzo di inizio del vettore in memoria centrale
Getat(i) Riporta *(b+i-min)
Putat(i,s) *(b+i-min)=s
New(min,max) b=alloca(max-min+1)
Destroy() disalloca(b)
![Page 27: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/27.jpg)
Matrice: modello concettuale
Rappresenta oggetti del mondo reale caratterizzati da un insieme di valori tutti dello stesso tipo organizzati per righe e colonne, con righe da minr a maxr e colonne da minc a maxc.
Esempio: i pezzi su una scacchiera
![Page 28: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/28.jpg)
Matrice: modello logico
New(minr, maxr, minc, maxc) costruttore Destroy() distruttore
Getat(r,c) riporta il valore s alla posizione r,c
Putat(r,c,s) assegna il valore s alla posizione r,c
![Page 29: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/29.jpg)
Matrice: modello fisico Si assume che l’oggetto creato abbia una
proprietà nascosta b chiamata indirizzo base, che individui l’indirizzo di inizio della matrice in memoria centrale
Chiamiamo dimensioni D1 e D2 D1=maxr – minr + 1 e D2=maxc – minc + 1
Getat(r,c) Riporta *(b+ (r-minr)*D2+(c-
minc)) Putat(r,c,s)
*(b+ (r-minr)*D2+(c-minc))=s
New(minr, maxr, minc, maxc) b=alloca(D1 * D2)
Destroy() disalloca(b)
![Page 30: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/30.jpg)
Stack o Pila: modello concettuale
Rappresenta oggetti del mondo reale caratterizzati da un insieme di valori in cui l’inserimento e l’estrazione siano secondo la disciplina LIFO (Last In First Out)
Esempio: una pila di libri, in cui l’inserimento e l’estrazione avvengono solo alla sommità
![Page 31: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/31.jpg)
Stack: modello logico
New() costruttore IsEmpty() riporta
vero se vuoto, falso altrimenti
IsFull() riporta vero se pieno, falso altrimenti
Destroy() distruttore
Pop() estrae un oggetto s e lo riporta
Push(s) inserisce l’oggetto s
![Page 32: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/32.jpg)
Stack: modello fisico - 1 Modalità consecutiva: si usa un vettore
V di componenti da 1 a m ed una variabile intera T (top dello stack)
IsEmpty()Se T=0 Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
New()Alloca V(da 1 a m)
m massima coordinata
T=0 Destroy()
disalloca(V)
M=T=0
![Page 33: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/33.jpg)
Stack: modello fisico - 2
IsFull()Se T=m Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
Push(s)Se non IsFull() Allora
T=T + 1V(T) = s
Finese Pop()
Se non IsEmpty() Alloras = V(T)T = T – 1Ritorna s
Finese
![Page 34: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/34.jpg)
Stack: modello fisico – un esempio
V
1 2 3 4 5
55 22 14
T 3 Top: Contiene il numero dell’ultima componente piena
M 5 Massimo: contiene il numero dell’ultima componente
![Page 35: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/35.jpg)
Coda: modello concettuale
Rappresenta oggetti del mondo reale caratterizzati da un insieme di valori in cui l’inserimento e l’estrazione siano secondo la disciplina FIFO (First In First Out)
Esempio: una fila in banca, in cui l’inserimento avviene sul retro e l’estrazione avviene alla fronte
![Page 36: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/36.jpg)
Coda: modello logico
New() costruttore IsEmpty() riporta
vero se vuoto, falso altrimenti
IsFull() riporta vero se pieno, falso altrimenti
Destroy() distruttore
Deq() estrae un oggetto s e lo riporta
Enq(s) inserisce l’oggetto s
![Page 37: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/37.jpg)
Coda: modello fisico lineare - 1 Modalità consecutiva: si usa un vettore
V di componenti da 1 a m e due variabili intere R (Retro) e F (Fronte)
IsEmpty()Se R=0 Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
New()Alloca V(da 1 a m)
m massima coordinata
R=0 ; F=1 Destroy()
disalloca(V)
M=R=0
![Page 38: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/38.jpg)
Coda: modello fisico lineare - 2 IsFull()
Se R=m AlloraRitorna Vero
AltrimentiRitorna Falso
Finese Enq(s)
Se non IsFull() AlloraR=R + 1V(R) = s
Finese
Deq()Se non IsEmpty() Allora
s = V(F)
Se F=R Allora
F=1 ; R=0
Altrimenti
F = F + 1
Finese
Ritorna s
Finese
![Page 39: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/39.jpg)
Coda: modello fisico lineare – un esempio
V
1 2 3 4 5
5522 14
R 4 Retro: Contiene il numero dell’ultima componente entrata
M 5 Massimo: contiene il numero dell’ultima componente
F 2 Fronte: Contiene il numero della componente che deve uscire
![Page 40: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/40.jpg)
Coda: modello fisico circolare
Il modello fisico consecutivo lineare della coda ha il difetto di creare una “bolla vuota” in testa al vettore
Tale “bolla vuota” può fare apparire piena una coda che invece ha spazio vuoto ma inutilizzabile in testa
La soluzione è usare un modello fisico circolare, con F e R che arrivati a M ripartono da 1
![Page 41: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/41.jpg)
Coda: modello fisico circolare - 1 Modalità consecutiva: si usa un vettore
V di componenti da 1 a m e due variabili intere R (Retro) e F (Fronte)
IsEmpty()Se R=0 Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
New()Alloca V(da 1 a m)
m massima coordinata
R=0 ; F=1 Destroy()
disalloca(V)
M=R=0
![Page 42: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/42.jpg)
Coda: modello fisico circolare - 2
IsFull()Nextr=(R=m) ? 1 : R+1
Se Nextr=F e R!=0 Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
Enq(s)Se non IsFull() Allora
R=(R=m) ? 1 : R+1
V(R) = s
Finese
![Page 43: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/43.jpg)
Coda: modello fisico circolare - 3 Deq()
Se non IsEmpty() Allora
s = V(F)
Se F=R Allora
F=1 ; R=0
Altrimenti
F = (F=m) ? 1 : F + 1
Finese
Ritorna s
Finese
![Page 44: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/44.jpg)
Coda: modello fisico circolare – un esempio
V
1
2
3
4
5
5522
14
R 4 Retro: Contiene il numero dell’ultima componente entrata
M 5 Massimo: contiene il numero dell’ultima componente
F 2 Fronte: Contiene il numero della componente che deve uscire
![Page 45: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/45.jpg)
Lista: modello concettuale
Rappresenta oggetti del mondo reale caratterizzati da un insieme di valori in cui l’inserimento e l’estrazione siano possibili dalla testa, dalla coda ed in qualsiasi posizione
Esempio: inventatevelo voi
![Page 46: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/46.jpg)
Lista: modello logico - 1
New() costruttore IsEmpty() riporta
vero se vuoto, falso altrimenti
IsFull() riporta vero se pieno, falso altrimenti
Destroy() distruttore
RemoveFirst() estrae il primo oggetto s e lo riporta
AddFirst(s) inserisce l’oggetto s come primo
![Page 47: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/47.jpg)
Lista: modello logico - 2
Length() riporta il numero di elementi in lista
RemoveAt(i) estrae oggetto i-mo s e lo riporta
AddAt(i,s) inserisce l’oggetto s come i-mo
RemoveLast() estrae l’ultimo oggetto s e lo riporta
AddLast(s) inserisce l’oggetto s come ultimo
![Page 48: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/48.jpg)
Allocazione consecutiva e non consecutiva
Le strutture dati, pur mantenendo lo stesso modello concettuale e logico, possono avere un modello fisico in allocazione consecutiva o non consecutiva
In allocazione consecutiva, vengono realizzate usando vettori, in cui le componenti sono consecutive in memoria centrale
![Page 49: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/49.jpg)
Allocazione consecutiva: pregi e difetti
L’allocazione consecutiva usa ricette relativamente semplici ed è possibile con tutti i linguaggi di programmazione
Ma prealloca i vettori, e quindi spreca spazio quando la struttura è vuota mentre impedisce di continuare quando la struttura si riempie
![Page 50: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/50.jpg)
Allocazione non consecutiva
In allocazione non consecutiva, le strutture vengono realizzate collegando grumi di informazione (detti Nodi) come perle in una collana
Le perle vengono allocate e disallocate al bisogno, collegandole tra di loro
Questo richiede ricette più complesse, ma permette strutture che si contraggono ed espandono al bisogno
![Page 51: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/51.jpg)
Stack: modello fisico non consecutivo
Ogni nodo è costituito da due campi: Info contiene il valore dell’elemento Next contiene l’indirizzo del
prossimo nodo T contiene l’indirizzo del primo nodo T contiene il valore NULL se lo stack
è vuoto
115
53
32
T
![Page 52: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/52.jpg)
Stack: modello fisico non consecutivo - 1
Destroy()Mentre NON Isempty()
s=Pop()
Fine Mentre
IsEmpty()Se T=NULL Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
New()T=NULL
IsFull()Prova ad allocare spazio
Se hai un errore
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
![Page 53: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/53.jpg)
Stack: modello fisico non consecutivo - 2
Push(s)Se non IsFull() Allora
P=alloca()P.Info = sP.Next = TT = P
Finese
Pop()Se non IsEmpty() Allora
P = T
s = T.Info
T = T.Next
libera (P)
Ritorna s
Finese
![Page 54: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/54.jpg)
Coda: modello fisico non consecutivo
Ogni nodo è costituito da due campi: Info contiene il valore dell’elemento Next contiene l’indirizzo del
prossimo nodo F contiene l’indirizzo del nodo fronte R contiene l’indirizzo del nodo retro F e R contengono il valore NULL se
la coda è vuota
115
53
32
F
R
![Page 55: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/55.jpg)
Coda: modello fisico non consecutivo - 1
Destroy()Mentre NON Isempty()
s=Deq()
Fine Mentre
IsEmpty()Se F=NULL Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
New()F=NULL
R=NULL IsFull()
Prova ad allocare spazio
Se hai un errore
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
![Page 56: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/56.jpg)
Coda: modello fisico non consecutivo - 2
Enq(s)Se non IsFull() Allora
P=alloca() ; P.Info = sP.Next = NULLSe R != NULL Allora
R.Next = P R = P
Altrimenti R = P ; F = P
FineseFinese
Deq()Se non IsEmpty() Allora
P = Fs = F.InfoF = F.Nextlibera (P)Se F = NULL Allora R = NULLFineseRitorna s
Finese
![Page 57: Le Strutture Dati M. Capurso con materiale di: G.Piccolo, A.Arcieri, Lamacchia F. Piccolo, B. Monterisi (Abstract Data Types)](https://reader033.fdocumenti.com/reader033/viewer/2022051820/5542eb4c497959361e8b955d/html5/thumbnails/57.jpg)
Continua…