Le Strutture
Dati
(Abstract Data
Types)
M. Capurso con materiale di:
G.Piccolo, A.Arcieri, Lamacchia
F. Piccolo, B. Monterisi
http://info.bazarinfo.info
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
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.
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
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
Definizione
Una Struttura Dati (o
Abstract Data Type) è un
insieme di Informazioni ed
Algoritmi cha rappresentano
nel computer ( quindi in un
universo virtuale) situazioni
ed oggetti presenti nella
realtà.
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.
Tipo
Si 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
Esempio
Giotto
Pittore(Dante)=Falso
Pittore(Leopardi)=Falso
Pittore(Raffaello)=Vero
Pittore(Giotto)=Vero
Raffaello
Classe dei Pittori
Leopardi
Pittore è un tipo
Esso descrive la
Classe dei Pittori
Dante
Universo del discorso
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
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
Stampo o Template
Uno stampo è un meccanismo
per costruire oggetti
Uno stampo è composto da
Un nome
Un elenco di Proprietà
Un elenco di Ricette
Esempio di stampo
1. Stampo di: Pecorella (nome)
2.  Zampe
Testa
Coda
Nome
3. Per_Belare: Ricetta per far sì
che alla pressione del pancino la
pecorella emetta un belato
Proprietà
Proprietà nello stampo
Le proprietà nello stampo hanno un
valore Definizionale ( sono dei
segnaposto) mentre nell’oggetto
creato dallo stampo le proprietà
Nome =
Bianchina
hanno un valore Fattuale
(assumono dei valori reali in un
oggetto specifico)
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
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 Nome =
Nome =
Bianchina
oggetto
Nerina
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
Giotto
Numero Pittori
Raffaello
Età media alla morte
Classe dei Pittori
Stampo, tipo e classe sono
collegati
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
Tre punti di vista
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.
Le strutture dati più semplici





Tipi elementari
Strutture ripetitive (vettori e matrici)
Stack
Coda
Lista
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
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
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
New()


b=alloca()
Destroy()


disalloca(b)
Get()


Riporta *b
Put(s)

*b=s
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
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
Vettore: modello fisico


New(min,max)


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
b=alloca(max-min+1)
Destroy()


disalloca(b)
Getat(i)


Riporta *(b+i-min)
Putat(i,s)

*(b+i-min)=s
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
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
Matrice: modello fisico



New(minr, maxr,
minc, maxc)


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)

b=alloca(D1 * D2)
Destroy()


disalloca(b)

Riporta *(b+ (r-minr)*D2+(cminc))
Putat(r,c,s)

*(b+ (r-minr)*D2+(c-minc))=s
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à
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
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)
New()
Alloca V(da 1 a m)
m massima coordinata
T=0

Destroy()
disalloca(V)
M=T=0

IsEmpty()
Se T=0 Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
Stack: modello fisico - 2

IsFull()
Se T=m Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese

Push(s)
Se non IsFull() Allora
T=T + 1
V(T) = s
Finese

Pop()
Se non IsEmpty() Allora
s = V(T)
T=T–1
Ritorna s
Finese
Stack: modello fisico – un
esempio
V
T
M
55
22
14
1
2
3
4
5
3
Top: Contiene il numero dell’ultima componente piena
5
Massimo: contiene il numero dell’ultima componente
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
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
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)
New()
Alloca V(da 1 a m)
m massima coordinata
R=0 ; F=1

Destroy()
disalloca(V)
M=R=0

IsEmpty()
Se R=0 Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
Coda: modello fisico lineare - 2

IsFull()
Se R=m Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese

Enq(s)
Se non IsFull() Allora
R=R + 1
V(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
Coda: modello fisico lineare – un
esempio
V
1
22
14
55
2
3
4
5
R
4
Retro: Contiene il numero dell’ultima componente entrata
F
2
Fronte: Contiene il numero della componente che deve uscire
M
5
Massimo: contiene il numero dell’ultima componente
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
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)
New()
Alloca V(da 1 a m)
m massima coordinata
R=0 ; F=1

Destroy()
disalloca(V)
M=R=0

IsEmpty()
Se R=0 Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
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
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
Coda: modello fisico circolare –
un esempio
3
14
22
2
4
55
V
1
5
R
4
Retro: Contiene il numero dell’ultima componente entrata
F
2
Fronte: Contiene il numero della componente che deve uscire
M
5
Massimo: contiene il numero dell’ultima componente
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
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
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 imo


RemoveLast()
estrae l’ultimo
oggetto s e lo
riporta
AddLast(s)
inserisce l’oggetto
s come ultimo
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
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
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
Stack: modello fisico non
consecutivo



T
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
Stack: modello fisico non
consecutivo - 1

New()

Mentre NON Isempty()
s=Pop()
Fine Mentre
T=NULL

Destroy()
IsFull()
Prova ad allocare spazio
Se hai un errore
Ritorna Vero
Altrimenti
Ritorna Falso
Finese

IsEmpty()
Se T=NULL Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
Stack: modello fisico non
consecutivo - 2

Push(s)
Se non IsFull() Allora
P=alloca()
P.Info = s
P.Next = T
T=P
Finese

Pop()
Se non IsEmpty() Allora
P=T
s = T.Info
T = T.Next
libera (P)
Ritorna s
Finese
Coda: modello fisico non
consecutivo




F
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
R
115
53
32
Coda: modello fisico non
consecutivo - 1

New()

Mentre NON Isempty()
s=Deq()
Fine Mentre
F=NULL
R=NULL

Destroy()
IsFull()
Prova ad allocare spazio
Se hai un errore
Ritorna Vero
Altrimenti
Ritorna Falso
Finese

IsEmpty()
Se F=NULL Allora
Ritorna Vero
Altrimenti
Ritorna Falso
Finese
Coda: modello fisico non
consecutivo - 2

Enq(s)
Se non IsFull() Allora
P=alloca() ; P.Info = s
P.Next = NULL
Se R != NULL Allora
R.Next = P
R=P
Altrimenti
R=P;F=P
Finese
Finese

Deq()
Se non IsEmpty() Allora
P=F
s = F.Info
F = F.Next
libera (P)
Se F = NULL Allora
R = NULL
Finese
Ritorna s
Finese
Continua…