Tipi di dato e strutture dati

(1)

Ugo de'Liguoro - Informatica 2 ADT e classi

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

(2)

I numeri razionali

Le rappresentazioni più usate sono quella decimale

(imprecisa), oppure le frazioni

, L 3 , 5 2 1

bd cb ad d c b

a + = +

Specifica: la sintassi

Consiste nel definire nuovi identificatori:

• nome del tipo definito:

Es. Ratio

• nomi e tipi degli operatori

Es.

NewRatio: void → Ratio Assign: Int, Int→ Ratio Sum: Ratio, Ratio → Ratio Invert: Ratio → Ratio

LessOrEqual: Ratio, Ratio → Bool

Specifica: la semantica

Consiste nel definire il significato/

comportamento degli operatori

Equazionalmente:

LessOrEqual(Assign(a, b), Assign(c, d)) = (ad ≤ bc) Bene per le proprietà del campo dei

razionali, ma problematico per esprimere side effects

(3)

Specifica: la semantica

Consiste nel definire il significato/

comportamento degli operatori

Con pre e post-condizioni

NewRatio(): Post: produce la frazione 0/1 Assign(n, m): Post: ritorna n/m

Sum(r, s): Post: ritorna r + s

…

Il significato dell’astrazione

Quanto fa 2/3 + r ?

Sum(Assign(2,3), r) Il razionale r è

maggiore o eguale a 0 ?

LessOrEqual(Assign(0,1), r)

Utente

Il significato dell’astrazione

Vorrei sapere se le frazioni sono ridotte ai

minimi termini

Questi sono affari privati Posso conoscere il

denumeratore di r?

La specifica non prevede questo operatore

Utente

(4)

Il significato dell’astrazione

Utente

L’utente interagisce con i valori di tipo Ratio 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[i] = valore all’indirizzo base + i⋅ 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

Invarianti di struttura

Una proprietà di una struttura dati che deve essere mantenuta dopo qualunque accesso alla struttura è un invariante di struttura

numeratore denumeratore

denumeratore≠ 0

Se così abbiamo deciso, possiamo chiedere che num. e den. siano primi tra loro

I numeri razionali: realizzazione

numeratore denumeratore Struttura dati:

un record typedef struct ratio {

int num, den;

} Ratio;

Ratio Sum (Ratio a, Ratio b)

{ Ratio c;

c.num = a.num*b.den + b.num*a.den;

c.den = a.den*b.den;

return c;

}

(7)

Una rivoluzione copernicana

Universo centrato sulle funzioni:

i nomi dei dati sono passati alle funzioni che così vi accedono Universo centrato sulle funzioni:

i nomi dei dati sono passati alle funzioni che così vi accedono

Universo centrato sui dati:

i nomi delle funzioni sono passati ai dati, che li interpretano e usano

per modificare sé stessi Universo centrato sui dati:

i nomi delle funzioni sono passati ai dati, che li interpretano e usano

per modificare sé stessi

Oggetti

Un oggetto consiste di:

• una collezione di dati nascosti (stato)

• un insieme M di metodi pubblici in grado di manipolare lo stato e di comunicare all’esterno informazioni sullo stato Un oggetto consiste di:

• una collezione di dati nascosti (stato)

• un insieme M di metodi pubblici in grado di manipolare lo stato e di comunicare all’esterno informazioni sullo stato

Programmazione orientata agli oggetti:

• le unità di base di un programma sono gli oggetti

• l’esecuzione di un programma consiste nell’inviare messaggi agli oggetti, i quali attivano in risposta i loro metodi

Oggetti: esempio

value 0

get (codice di get) set (codice di set) riferimento

oggetto

mycell.set(0); … mycell.get() = 0 …

(8)

Una realizzazione più efficiente

value 0

value 1

get (codice di get) set (codice di set)

Il processo che identifica i metodi che appartengono ad un oggetto realizzato in questo modo prende il nome di method lookup.

Classi

Una classe è una descrizione (un prototipo) di una collezione di oggetti, consistente in:

1. un elenco di campi e dei loro tipi (che realizzano lo stato)

2. un elenco di metodi, incluse le loro definizioni (corpo)

Una classe è una descrizione (un prototipo) di una collezione di oggetti, consistente in:

1. un elenco di campi e dei loro tipi (che realizzano lo stato)

2. un elenco di metodi, incluse le loro definizioni (corpo)

Classi: esempio

class cell is

var value: Integer := 0;

method get(): Integer is return this.value;

method set(n: Integer) is this.value := n;

this è un riferimento all’oggetto che esegue il metodo

(9)

Istanziazione

In un linguaggio “class based” gli oggetti sono istanze di classi

var myCell: TypeOf(cell) := new cell;

In alcuni linguaggi (C++, Java) il tipo di una classe coincide con la classe stessa

L’operatore new è un allocatore (in C++ è una evoluzione di malloc)

Dichiarazione e definizione

class nome della classe {

private: lista di variabili e metodi privati public: lista di variabili e metodi pubblici };

Una classe si dichiara utilizzando la sintassi:

Per definire un metodo si usa invece la sintassi:

tipo del valore nome della classe::nome del metodo (lista argomenti) {corpo del metodo }

operatore di risoluzione

Esempio: numeri complessi

class Complex { private:

float real, imag;

public:

void assign_real(float);

void assign_imag(float);

float get_real();

float get_imag();

Complex add(Complex);

Complex multitly(Complex);

// ecc.

};

void Complex::assign_real(float re) {real = re;}

float Complex::get_real() {return real;}

(10)

Oggetti

Gli oggetti sono istanze delle classi; condividono i metodi e le variabili della classe (precedute dal qualificatore static), mentre posseggono propri campi per le variabili oggetto.

Es.

Complex a, b, c; // crea tre oggetti della classe Una volta definiti, gli oggetti possono invocare metodi per notificare o modificare il proprio stato:

a.assign_real(7.2);

float x = a.get_real() ; // x vale 7.2 Inoltre un oggetto può essere definito attraverso un’assegnamento:

a = b.add(c); // significa a = b + c;

Il puntatore this

Un metodo appartenente ad una classe può accedere direttamente ai campi privati; per sottolineare che questi campi sono quelli dell’oggetto cui appartiene il metodo si usa il puntatore this (in altri linguaggi self):

Es. Un modo più esplicito di scrivere il metodo assign_real della classe Complex è

void Complex::assign_real(float re) {this->real = re;}

Dalla stessa sintassi usata risulta che il tipo di this in un metodo appartenente alla classe X ha tipo X* (puntatore a oggetti di tipo/classe X).

Funzioni inline

Quando il corpo di un metodo si riduce ad un’assegnazione ovvero a ritornare il valore di una variabile di campo privato, allora può essere inserito direttamente nella dichiarazione della classe (il metodo allora si dice inline):

class Complex { private:

float real, imag;

public:

void assign_real(float re) {real = re;}

void assign_imag(float im) {imag = im;}

float get_real() {return real;}

float get_imag() {return imag;}

Complex add(Complex);

Complex multitly(Complex);

// ecc.

};

Nota: le funzioni inline possono essere precedute dalla parola inline.

inline functions

(11)

Costruttori

Ciascuna classe dispone di uno o più costruttori. Un costruttore è un metodo con lo stesso nome della classe, il cui compito è di allocare gli oggetti della classe, eventualmente inizializzandone i campi.

class Complex {

private: float real, imag;

public:

Complex(float re=0, float im=0) {real=re,imag=im;}

// ecc.

};

Complex a; // a.real = 0.0, a.imag = 0.0 Complex b(7.3); // b.real = 7.3, b.imag = 0.0 Complex c(7.3,5.1); // c.real = 7.3, c.imag = 5.1 valori di default

Razionali in C++

class Ratio { public:

Ratio (int n=0, int d=0);

void Assign (int n, int d);

Ratio Sum (Ratio r);

bool LessOrEqual (Ratio r);

void print ();

private:

int num, den;

};

Interfaccia:

corrisponde alla specifica sintattica

Razionali in C++

Ratio::Ratio(int n, int d) { num = n;

den = d;

}

void Ratio::Assign (int n, int d) { num = n, den = d;

}

costruttore

:: operatore di risoluzione

(12)

Razionali in C++

Ratio Ratio::Sum (Ratio r)

{ Ratio q (num*r.den+den*r.num,den*r.den);

return q;

}

Si usa come:

Ratio a (2, 3);

Ratio b (5, 4);

Ratio c = a.Sum(b); // c = a + b;