Tipi di dato e strutture dati

(1)

Ugo de’ Liguoro - Algoritmi e Sperimentazioni 03/04 - Lez. 4

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, …, , …

Interi

,

Booleani

≤

I tipi di dato sono modelli matematici

(2)

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 IsEmpty: Stack → Boolean

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

l’emergente

(3)

Interfacce in Java

Stack {

IsEmpty();

// Post: true se la pila è vuota, false altr.

Push(Object newitem);

// Post: aggiunge newitem come emergente Object Top();

// Pre: la pila non è vuota

// Post: ritorna l’emergente senza rimuoverlo

Pop();

// Pre: la pila non è vuota

// Post: rimuove l’emergente dalla pila }

manca NewStack: sarà il costruttore

s: Stack è this:

dunque non viene mai menzio-

nato

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 ^!"$#^%&^# Posso inserire un valore in

fondo alla pila s?

Non senza aver prima rimosso tutti gli altri con

Pop

Utente

(4)

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

Programma

applicativo Accesso diretto

ai dati ADT = Abstract Data Type

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

(5)

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[^'] = valore all’ indirizzo base + ^'⋅ dim(valore)

V

Primitive di accesso

5 9 1 ∅

L = Puntatore al primo el.

p

p.next

p.info 2

Cons(2, L)

Primitive di accesso

0010011010010111 not

1101100101101000

(6)

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

((

StackAsArray *)+ ),(

Stack {

+,

-

nextfree;

+,

Object arrayofvalues[];

...

}

Struttura dati

(7)

Cassi in Java

((

Stack { ...

+.

StackAsArray ( size) { arrayofvalues = ^/ Object[size];

nextfree = 0;

}

+.

StackAsArray () {

0,(

(100);

} ...

} overloading

costrut- tori

Cassi in Java

((

Stack { ...

IsEmpty() {

.

nextfree == 0;

}

+.

Object Top() {

return arrayofvalues[nextfree];

}

+.

Pop() { nextfree--;

} ...

}

Cassi in Java

2$3 4 5 5

StackAsArray ^{6*7 8}^3$9⁷^{9 :; 5} Stack { ...

8<$=

36 2?>@

6$A Push(Object newitem) {

6 B (nextfree == arrayofvalues.length) EnlargeOf (100);

arrayofvalues[nextfree++] = newitem;

}

8C 6

>4;*9D>@

6A EnlargeOf (⁶^:; size) {

// alloca altri size elementi in arrayofvalues[]

Object temp[] =

: 9E

Object[arrayofvalues.length + size];

B@C (⁶^:; i = 0; i < arrayofvalues.length; i++) temp[i] = arrayofvalues[i];

arrayofvalues = temp;

} Ha senso perché è un

vettore

(8)

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.

Tipi di dato e strutture dati