Tipi di dato e strutture dati
Specifica e realizzazione di strutture
informative come classi
Che cos’è un tipo di dato?
• Tutti i linguaggi di programmazione tipati forniscono tipi ed operatori predefiniti
• Linguaggi di programmazione come Pascal, C o Java consentono all’utente di definirne di nuovi
Cos’è un tipo?
Insieme di valori + operatori
+
0, 1, 2, …, n, … Interi
true, false Booleani
not
≤
I tipi di dato sono modelli
matematici
Specifica: la sintassi
Consiste nel definire nuovi identificatori:
• nome del tipo definito:
Es. Stack
• nomi e tipi degli operatori
Es.
NewStack: void → Stack
Push: TipoEl, Stack → Stack Top: Stack → TipoEl
Pop: Stack → Stack
Specifica: la semantica
Consiste nel definire il significato/
comportamento degli operatori
Equazionalmente:
IsEmpty(NewStack()) = true IsEmpty(Push(e, s)) = false Top(Push(e, s)) = e
Pop(Push(e, s)) = s
…
Specifica: la semantica
Consiste nel definire il significato/
comportamento degli operatori
Con pre e post-condizioni
NewStack(): Post: produce una pila vuota
IsEmtpty(s): Post: true se s = ∅, false altrimenti
Push(e, s): Post: ritorna la pila ottenuta aggiungendo e ad s come el. emergente
Top(s): Pre: s ≠ ∅; Post: ritorna l’emergente
Pop(s): Pre: s ≠ ∅; Post: ritorna s meno
Interfacce in Java
interface Stack {
boolean IsEmpty();
// Post: true se la pila è vuota, false altr.
void Push(Object newitem);
// Post: aggiunge newitem come emergente Object Top();
// Pre: la pila non è vuota
// Post: ritorna l’emergente senza rimuoverlo void Pop();
// Pre: la pila non è vuota
// Post: rimuove l’emergente dalla pila }
manca NewStack: sarà il costruttore
: non mai nato s: Stack è this
dunque
viene
menzio-
Il significato dell’astrazione
Posso conoscere allora il valore dell’emergente:
Top(s) = ?
Top(s) = e La pila s è vuota:
IsEmpty(s) = ? IsEmpty(s)
= false
Utente
Il significato dell’astrazione
Vorrei sapere come sono organizzati gli el.
Questi sono affari privati Posso inserire un valore in
fondo alla pila s?
Non senza aver prima rimosso tutti gli altri con
Pop
Utente
Il significato dell’astrazione
Utente
L’utente interagisce con i valori di tipo Stack
solo attraverso gli operatori: non può né deve conoscere i dettagli
della loro realizzazione
Il significato dell’astrazione
Implementazione dell’ADT
barriera
operatore Programma
applicativo
ADT = Abstract Data Type
Programma applicativo
Accesso diretto
ai dati
Che cos’è una struttura dati?
modo sistematico di rappresentare ed organizzare dati
Struttura dati =
a f k z q d i w
vettore
2 5 9 1 ∅
lista
0010011010010111
numero intero rappr. in binario
Primitive di accesso
Una struttura dati deve essere dotata di primitive che
consentano di costruire, distruggere, esplorare e modificare gli aggregati di dati:
a f k z q d i w
base = indirizzo del primo
elemento
V[i] = valore all’indirizzo
base + i ⋅ dim(valore)
V
Primitive di accesso
Una struttura dati deve essere dotata di primitive che
consentano di costruire, distruggere, esplorare e modificare gli aggregati di dati:
L = Puntatore al p
p.info 2
Cons(2, L)
p.next
5 9 1 ∅
Primitive di accesso
Una struttura dati deve essere dotata di primitive che
consentano di costruire, distruggere, esplorare e modificare gli aggregati di dati:
0010011010010111 not
1101100101101000
Invarianti di struttura
Una proprietà di una struttura dati che deve
essere mantenuta dopo qualunque accesso alla struttura è un invariante di struttura
2 5 9 1 ∅
lista
I puntatori di una lista devono concatenare tra
loro tutti i singoli elementi
Realizzazione mediante classi
• La struttura dati è il valore di alcuni campi privati
• Gli operatori dell’ADT sono realizzati con altrettanti metodi pubblici (in particolare l’operatore che genera una nuova istanza della struttura è un costruttore)
• Eventuali routines ausiliarie coinvolte nella realizzazione dei metodi pubblici, sono
realizzate con metodi privati
Cassi in Java
class StackAsArray implements Stack { private int nextfree;
private Object arrayofvalues[];
...
}
Struttura
dati
Cassi in Java
class StackAsArray implements Stack { ...
public StackAsArray (int size) {
arrayofvalues = new Object[size];
nextfree = 0;
}
public StackAsArray () { this(100);
} ...
} overloading
tori
costrut-
Cassi in Java
class StackAsArray implements Stack { ...
public boolean IsEmpty() { return nextfree == 0;
}
public Object Top() {
return arrayofvalues[nextfree - 1];
}
public void Pop() { nextfree--;
}
...
Cassi in Java
class StackAsArray implements Stack { ...
public void Push(Object newitem) {
if (nextfree == arrayofvalues.length) EnlargeOf (100);
arrayofvalues[nextfree++] = newitem;
}
private void EnlargeOf (int size) {
// alloca altri size elementi in arrayofvalues[]
Object temp[] =
new Object[arrayofvalues.length + size];
for (int i = 0; i < arrayofvalues.length; i++) temp[i] = arrayofvalues[i];
arrayofvalues = temp;
} Ha senso perché è un
vettore
Invariante di classe
• Quando un’ADT viene realizzato con una classe, che a sua volta implementa una o più strutture dati, l’invariante di struttura deve essere parte della post-condizione di tutti i metodi pubblici: prende allora il nome di invariante di classe.
• L’invariante di classe, essendo relativo
all’implementazione, non è pubblico: deve implicare le post-condizioni dei metodi
pubblici come dichiarate in interfaccia
Matrici sparse
Quando una matrice n×n ha O(n) entrate non nulle si dice sparsa.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 7 0 0 0 0 0 0 0 0 0 0 0 0
Matrici sparse
Conviene allora studiare una struttura dati col seguente invariante di struttura
sono rappresentate solo le entrate con valori non nulli; le altre sono
implicitamente considerate nulle sono rappresentate solo le entrate
con valori non nulli; le altre sono
implicitamente considerate nulle
Matrici sparse
Matrici sparse in Java
interface Matrix {
// Pre: i, j sono indici (da 1 in poi), // non spiazzamenti
void set(int i, int j, int v);
// Post: assegnazione M[i,j]:= v int get (int i, int j);
// Post: ritorna M[i,j]
}
Matrici sparse in Java
class SparseMatrix implements Matrix { private class Node {
int row, col; // coordinate dell'entrata int value; // valore dell'entrata
Node nextOnrow, nextOncol;
// riferimenti all'entrata effettiva successiva // sulla stessa riga/colonna
Node (int i, int j, int v) {
row = i; col = j; value = v;
nextOnrow = nextOncol = null;
} }
private Node[] arrayOfrows, arrayOfcols;
Matrici sparse in Java
class SparseMatrix implements Matrix { ...
SparseMatrix (int rowdim, int coldim) {
arrayOfrows = new Node[rowdim];
arrayOfcols = new Node[coldim];
} ...
}
Ugo de' Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 4
