• Non ci sono risultati.

Che cos’è un tipo di dato?

N/A
N/A
Protected

Academic year: 2022

Condividi "Che cos’è un tipo di dato?"

Copied!
32
0
0

Testo completo

(1)

Tipi di dato e strutture dati

Specifica e realizzazione di strutture

informative come classi

(2)

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?

(3)

Insieme di valori + operatori

+

0, 1, 2, …, n, … Interi

true, false Booleani

not

I tipi di dato sono modelli

matematici

(4)

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

(5)

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

(6)

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

(7)

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-

(8)

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

(9)

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

(10)

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

(11)

Il significato dell’astrazione

Implementazione dell’ADT

barriera

operatore Programma

applicativo

ADT = Abstract Data Type

Programma applicativo

Accesso diretto

ai dati

(12)

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

(13)

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

(14)

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 ∅

(15)

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

(16)

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

(17)

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

(18)

Cassi in Java

class StackAsArray implements Stack { private int nextfree;

private Object arrayofvalues[];

...

}

Struttura

dati

(19)

Cassi in Java

class StackAsArray implements Stack { ...

public StackAsArray (int size) {

arrayofvalues = new Object[size];

nextfree = 0;

}

public StackAsArray () { this(100);

} ...

} overloading

tori

costrut-

(20)

Cassi in Java

class StackAsArray implements Stack { ...

public boolean IsEmpty() { return nextfree == 0;

}

public Object Top() {

return arrayofvalues[nextfree - 1];

}

public void Pop() { nextfree--;

}

...

(21)

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

(22)

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

(23)

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

(24)

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

(25)

Matrici sparse

(26)

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]

}

(27)

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;

(28)

Matrici sparse in Java

class SparseMatrix implements Matrix { ...

SparseMatrix (int rowdim, int coldim) {

arrayOfrows = new Node[rowdim];

arrayOfcols = new Node[coldim];

} ...

}

(29)

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

Matrici sparse in Java

class SparseMatrix implements Matrix { ...

public int get (int i, int j)

// Pre: i in [1..arrayOfrows.length], // j in [1..arrayOfcols.length]

{ Node n;

if (i < j) // conviene cercare sulla colonna j

for(n = arrayOfcols[j-1]; n != null && n.row < i;

n = n.nextOncol);

else // conviene cercare sulla riga i

for(n = arrayOfrows[i-1]; n != null && n.col < j;

n = n.nextOnrow);

if (n != null && n.row == i && n.col == j) return n.value;

return 0;

} ...

(30)

Matrici sparse in Java

class SparseMatrix implements Matrix { ...

public void set(int i, int j, int v) // Pre: i in [1..arrayOfrows.length], // j in [1..arrayOfcols.length]

{ if (v != 0) // occorre inserire un nuovo nodo [i,j] oppure // sovrascrivere il campo value di quello esistente { Node newnode = new Node(i,j,v);

arrayOfrows[i-1] = insertOnrow(newnode, arrayOfrows[i-1]);

arrayOfcols[j-1] = insertOncol(newnode, arrayOfcols[j-1]);

} else // v == 0: occorre eliminare l'eventuale nodo [i,j]

{ arrayOfrows[i-1] = delOnrow(i, arrayOfrows[i-1]);

arrayOfcols[j-1] = delOncol(j, arrayOfcols[j-1]);

}

(31)

Matrici sparse in Java

class SparseMatrix implements Matrix { ...

private Node insertOnrow(Node n, Node l) // Pre: n != null

{ if (l == null || l.row > n.row) { n.nextOnrow = l;

return n;

} if (l.row == n.row){

l.value = n.value;

// sovrascrive, anzicche' inserire return l;

} // l.row < n.row

l.nextOnrow = insertOnrow(n, l.nextOnrow);

return l;

}

(32)

Matrici sparse in Java

class SparseMatrix implements Matrix { ...

private Node delOnrow (int row, Node l) // Post: ritorna la lista-riga l senza l’

// eventuale entrata sulla colonna row {

if (l == null || l.row > row) return l;

if (l.row == row) return l.nextOnrow;

l.nextOnrow = delOnrow(row, l.nextOnrow);

return l;

}

}

Riferimenti

Documenti correlati

Immagini di qualità e strumenti avanzati contribuiscono alla sicurezza diagnostica in una vgrande varietà di applicazioni e di esami clinici Le personalizzazioni del.

• CHAARTED mature results &amp; robust benefit by 6 cycles DOC; only in high-volume patients. • STAMPEDE benefit in M1 patients, tumor volume unknown; benefit

upfront treatment with either abiraterone or docetaxel is the new standard of care of patients with mHSPC... Scher HI,

Come evidenziato dalla definizione induttiva di sequenza, per costruire una qualsiasi lista, ` e sufficiente la costante lista vuota h i (rappresentata in C semplicemente dal

Per gestire gli activation records della funzione, definiamo un apposito tipo, attraverso una struct adeguata a memorizzare tutte le informazioni necessarie: parametri, variabili

La richiesta fatta dal client viene fatta all'indirizzo broadcast, poichè l'indirizzo IP del server è sconosciuto, la richiesta avrà quindi come mittente 0.0.0.0 (poichè l'IP non

Nei seguenti poligoni, indica con il pennarello rosso i vertici, con il pennarello blu gli angoli7. Osserva i due poligoni: nel primo colora il perimetro, nel

Anche in questo caso (come già per i sistemi TN, sistema in cui si trasforma il sistema IT con le masse collegate allo stesso impianto di terra in caso di secondo guasto a