Le Strutture Dati

M. Capurso con materiale di:G.Piccolo, A.Arcieri, LamacchiaF. Piccolo, B. Monterisihttp://info.bazarinfo.info

(Abstract Data Types)

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 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à.

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.

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

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

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

Uno stampo è composto da

Un nome

Un elenco di Proprietà

Un elenco di Ricette

Stampo o Template

Uno stampo è un meccanismo per costruire oggetti

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

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

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 oggetto

Nome =BianchinaNome =

Nerina

Beh

Beh

Muh

Muh

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

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

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

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

Get() Riporta *b

Put(s) *b=s

New() b=alloca()

Destroy() disalloca(b)

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 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)

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 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)

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)

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

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

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

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)

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

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

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

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)

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

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

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

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 i-mo

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

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

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

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

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

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

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

Continua…