Conversioni di tipo fra sottoclasse e superclasselaurap/didattica/Informatica... · 2010. 5....

1

Conversioni di tipo fra sottoclasse e

superclasse

Conversioni di tipo fra sottoclasse e superclasse

• Può esserci la necessità di memorizzare un riferimento di una sottoclasse in un riferimento a superclasse.

• È possibile?• Abbiamo visto l’invocazione del metodo push

di uno Stack di Object a cui era passata come parametro una stringa:

s.push("Pippo");

• È possibile perché String è sottoclasse di Object.


• Analogamente è possibile memorizzare un riferimento ad un oggetto di tipo ContoRisparmio in un riferimento di tipo ContoBancario, che è una superclasse.

• In generale è possibile memorizzare un qualsiasi riferimento a oggetto in un riferimento di tipo Object che è la superclasse universale.

• La conversione di tipo è automatica.(par. 10.5)


• Consideriamo questi riferimenti:

ContoRisparmio cr =

new ContoRisparmio(2);

ContoBancario cb = cr;

Object ogg = cr;

• Abbiamo tre riferimenti diversi che vedono la stessa area di memoria.


saldo 0

tassoInteresse 2

cr

cbogg


• Attenzione. Ogni riferimento può usare solo i metodi della sua classe:

cb.deposito(500);

cb può modificare il saldo, però non può usare aggiungiInteresse.

• Con il riferimento ogg (di Object) si possono usare solo i metodi di Object (come toString, equals, e pochi altri).

• Ciò nonostante può essere utile usare un riferimento della superclasse Object.

2


• Aggiungiamo a ContoBancario il seguente metodo che permette di trasferire denaro da un conto ad un altro: (par. 10.5)public class ContoBancario{

. . .

public void trasferisciA

(ContoBancario altro, double denaro)

{ this.prelievo(denaro);

altro.deposito(denaro); }

}//fine CB


• Esempio.ContoBancario padre =

new ContoBancario(5000);

ContoBancario figlio =

new ContoBancario();

padre.trasferisciA(figlio, 300);

• Controlliamo con una stampa il saldo di entrambi:


System.out.println

(padre.rendiSaldo());//4700

System.out.println

(figlio.rendiSaldo());//300

• Con l’invocazione del metodopadre.trasferisciA(figlio, 300);

• abbiamo:this.prelievo(300); //this=padre

altro.deposito(300); //altro=figlio


• Supponiamo ora che padre debba trasferire denaro ad un conto di tipo ContoRisparmio:

ContoRisparmio cliente =


• Possiamo fare:padre.trasferisciA(cliente,200);


• L’istruzione

padre.trasferisciA(cliente,200);

è corretta perché il metodo trasferisciAsi aspetta di ricevere come parametro un riferimento a CB e invece riceve un riferimento (cliente) a CR che è una sottoclasse: viene eseguita una conversione automatica.


• Il compilatore controlla solo che il riferimento di trasfersiciA, se non è di tipo CB, sia di tipo classe derivata da CB.

• Avviene quindi la conversione di un tipo ad un tipo superiore:ContoBancario altro ←←←← cliente

3


• Ciò è analogo a quanto avviene quando si assegna ad una variabile reale un valore intero:

double a = 25;

• In realtà nei tipi base avviene una cosa diversa perché il valore 25 (32 bit in complemento a 2) viene memorizzato in una sequenza di 64 bit con mantissa, esponente.


• Attenzione.• Il metodo trasferisciA invoca il metodo deposito:

public void trasferisciA

(ContoBancario altro, double denaro)

{

this.prelievo(denaro);

altro.deposito(denaro);

}


• Ma quale deposito?

• Il parametro altro contiene un riferimento di tipo ContoRisparmio.

• Quindi sarà deposito di ContoRisparmio: il metodo con cui si paga una tassa ad ogni versamento.

Polimorfismo

Polimorfismo

• Il termine polimorfismo (deriva dal greco πολιµορφίσµος) significa “molte forme”.

• Nel trasferimento di denaro viene attivato:• il metodo deposito di CB, quando il parametro èfiglio

• il metodo deposito di CR, quando il parametro ècliente.

• La stessa operazione “versare denaro” viene eseguita in modi diversi che dipendono dal tipo dell’oggetto che viene effettivamente usato come parametro implicito.

Polimorfismo

• Quando trasferisciA viene invocato, il riferimento passato ad altro “vede” un oggetto di tipo CR.

CB: altro CR: cliente

4

Polimorfismo

• L’interprete Java sa che in altro c’è un riferimento a CR e quindi invoca depositodi CR.

• Il compilatore può solo verificare la possibilità che ciò possa avvenire.

• La scelta di quale sia effettivamente il riferimento viene fatta durante l’esecuzionedel programma, vale a dire, solo quando il metodo viene invocato. (par. 10.6)

Polimorfismo

• La scelta pertanto non è fatta in base al tipo del riferimento, altro è definito di tipo CB, ma in base al tipo dell’oggetto che èrealmente memorizzato in altro e che è di tipo CR.

• Il metodo ha lo stesso nome ma ha “forme diverse”.

• Il metodo deposito di CR, infatti, sovrascrive il metodo deposito di CB.

Sovraccarico e polimorfismo

• Sovraccarico.• Si parla di sovraccarico quando in una classe

un metodo o un costruttore ha diverse scritture e possiede quindi parametri diversi.

• Esempio:• in ContoBancario abbiamo due costruttori, uno

senza parametro e uno con parametro• il metodo println possiede parametri diversi a

seconda del tipo base.


• È il compilatore che sceglie quale metodo invocare, prima che il programma venga eseguito.

• Si parla di selezione anticipata (early binding

o anche binding statico).


• Polimorfismo.• Si parla di polimorfismo quando un metodo

ha comportamenti diversi in relazione al tipo realmente memorizzato nel parametro implicito.

• Esempio:• nel metodo trasferisciA l’utilizzo del

metodo deposito di CB oppure di CR.


• È l’interprete JVM che decide durante l’esecuzione del programma quale metodo deve essere scelto.

• Si parla di selezione posticipata (late binding

o anche binding dinamico).

• Il compilatore controlla solo che il riferimento sia di tipo classe o sottoclasse.

5

Conversione inversa

Conversione inversa

• Si può fare la conversione inversa, vale a dire memorizzare un riferimento a superclasse in un riferimento a sottoclasse?

• È possibile fare una forzatura, cast, analogamente a quanto avviene per i tipi base.

• La conversione però ha senso solo se nel riferimento a superclasse è effettivamente memorizzato un riferimento a sottoclasse; in caso contrario si ha un errore.

Conversione inversa

• Esempio.ContoRisparmio cr =


ContoBancario cb = cr;

ContoRisparmio cr2 =

(ContoRisparmio)cb; //cast

• Senza cast il compilatore segnala errore: i tipi sono incompatibili.

Conversione inversa

• Se però cb (sul quale si fa il cast) non contiene un riferimento a cr, durante l’esecuzione la JVM lancia l’eccezione ClassCastException.

• Come fare per essere sicuri che un riferimento contenga un riferimento valido per l’oggetto e non commettere un errore?

Conversione inversa

• Per essere sicuri che un riferimento contenga un riferimento valido per quell’oggetto, si può usare l’operatore instanceof.

• Sintassi.variabileoggetto instanceof Nomeclasse

• L’operatore instanceof è booleano: restituisce true, se la variabile è del tipo NomeClasse, false altrimenti.

Conversione inversa

• Esempio.Vogliamo essere sicuri che il riferimento cbcontiene un riferimento a cr prima di eseguire l’assegnazione a cr2, possiamo scrivere:

if(cb instanceof ContoRisparmio)

cr2 = (ContoRisparmio)cb;

6

Interfacce e riutilizzo del codice


• La classe OperasuNumeri contiene metodi per eseguire il calcolo della somma, del massimo e del numero di un elenco di dati inseriti (reale).

(classe DataSet par. 6.4 e par. 9.1)

public class OperasuNumeri{

private double s;

private double max;

private int cont;


/* costruttore: inizializza la somma a zero, il massimo con l'estremo inferiore, il contatore dei numeri a zero */

public OperasuNumeri(){

s = 0;

max = - Double.MAX_VALUE;

cont = 0;

}//fine costruttore


/* metodo aggiungi : aggiunge un valore alla volta aggiornando il valore della somma, del massimo e del contatore dei valori inseriti */

public void aggiungi(double x){

s = s + x;

if(max < x)

max = x;

cont++;

}//fine aggiungi

Interfacce e riutilizzo del codice/* metodo somma : restituisce la somma dei valori inseriti */

public double somma(){

return s;

}

/* metodo massimo : restituisce il massimo dei valori inseriti */

public double massimo(){

return max;

}

Interfacce e riutilizzo del codice/** metodo quanti : restituisce il numero di valori inseriti */

public int quanti(){

return cont;

}

}//fine classe OperasuNumeri

• Consideriamo la classe ContoBancario e supponiamo di avere voler gestire una banca rappresentata da un certo numero di conti bancari e di voler calcolare quanti soldi ci sono in totale nella banca (somma).

7


• Supponiamo anche di voler sapere quanti sono i conti gestiti dalla banca (contatore) e quale èil conto bancario che ha il saldo maggiore(massimo).

• Avendo a disposizione la classe OperasuNumeri, possiamo riscriverla adattandola agli oggetti di tipo ContoBancario.

• Dovremo però fare qualche modifica.


public class OperasuContoBancario{

private double s;

private ContoBancario max;

private int cont;

/* non mettiamo alcun costruttore, quindi si attivera' quello di default

*/

/* Il massimo che cerchiamo e' il conto corrente che possiede il saldo maggiore */


public void aggiungi (ContoBancario x){

s = s + x.rendiSaldo();

if(cont==0 ||

max.rendiSaldo() < x.rendiSaldo())

max = x; //fine if

/* quando cont = 0 si inizializza max

con il primo conto bancario:

valutazione pigra dei predicati */

cont++;

}


public ContoBancario massimo(){

return max;

}

. . .

// altri metodi: quanti, somma

. . .

}//fine OperasuContoBancario


• In maniera analoga potremo dover risolvere un altro problema in cui si vuole trovare quale oggetto, in un elenco di oggetti, ha il valore massimo in uno dei suoi dati.

• Esempio. Dato un borsellino contenente delle monete vogliamo sapere quale è la somma totale e quale è la moneta con il valore piùelevato.

• Dovremo scrivere una classe OperasuMonete? Vediamo di risolvere il problema in altro modo.


• Dato un insieme di oggetti possiamo stabilirecosa si intende per “misura” di quell’oggetto; vogliamo poi risolvere il problema di trovare l’oggetto che ha la misura più grande.

• Esempi.

• Dato un insieme di Pile trovare la Pila che contiene più elementi (quantità di elementi).

• Dati dei numeri complessi trovare quello il cui modulo è maggiore (valore del modulo).

• Abbiamo bisogno di definire una proprietàastratta: “essere misurabile”.

8


• Abbiamo visto che in Java per definire una proprietà astratta si usa una interfaccia con la quale si esprimono funzionalità comuni alle classi che la realizzano.

• Nell’interfaccia si dichiarano le firme dei metodi che rappresentano le funzionalità.

• Le classi che realizzano l’interfaccia dovranno costruire il codice per tutti i metodi dell’interfaccia.


• Definiamo pertanto l’interfaccia Misurabile per definire la proprietà di:

avere una misura

public interface Misurabile{

// metodo che rappresenta una misura

double estraiMisura();

// Object altriDati();

}


• Possiamo voler aggiungere un metodo altriDati per poter rappresentare altre informazioni sugli oggetti misurabili.

• Esempio:• il nome del correntista il cui conto bancario è il

massimo;• una caratteristica (figura) della moneta che ha

il valore più grande• il numero della Pila con maggior elementi.


• Lo scopo è quello di non aver più bisogno di scrivere la classe OperasuContoBancario (e classi analoghe per risolvere problemi analoghi).

• Per prima cosa dovremo dichiarare che ContoBancario realizza l’interfaccia Misurabile e stabilire cosa intendiamo per “misura” di un conto bancario.

• Stabiliamo che la misura per CB è il valore del saldo.


public class ContoBancario

implements Misurabile{

. . .

public double estraiMisura(){

return saldo;

}

public Object altriDati(){

return nome;

}

}//fine ContoBancario


• Però dobbiamo ancora fare delle modifiche sulla classe che esegue la somma e trova il massimo, in modo da poterla riutilizzare nella soluzione di problemi analoghi.

• La classe OperasuContoBancario eseguiva le operazioni per il calcolo della somma, del numero di elementi inseriti e trovava l’elemento max: il conto bancario con il saldo maggiore.

9


• Un’altra classe avrebbe trovato come max la moneta con il valore più grande, oppure la Pila con il maggior numero di elementi.

• Dobbiamo allora di costruire una classe per gestire questi oggetti misurabili.

• Costruiamo una classe OperasuOggetti che gestisca le operazioni su oggetti le cui classi realizzano l’interfaccia Misurabile.


public class OperasuOggetti{

private double s;

private Misurabile max;

private int cont;

. . .//costruttore

public void aggiungi(Misurabile x){

s = s + x.estraiMisura();

if(cont==0 || max.estraiMisura()<

x.estraiMisura())


max = x; //fine if

cont++;

}//fine aggiungi

public Misurabile massimo(){

return max;

}

. . .//metodi quanti, somma

}//fine OperasuOggetti


• Questa classe potrà essere utilizzata dagli oggetti la cui classe che realizza Misurabile.

• Questo è un esempio di polimorfismo.

• Il metodo estraiMisura è polimorfo.

• Con l’invocazione del metodox.estraiMisura()

otteniamo diversi comportamenti.


• La classe ContoBancario realizza estraiMisura restituendo il saldo.

• Un’altra classe realizerà estraiMisura

restituendo un valore double con il significato di “misura” in quella classe.

• In realtà x non ha un suo tipo di dato: x è di “tipo interfaccia”.


• Sarà l’interprete Java che, durante l’esecuzione, vede quale riferimento èmemorizzato in x ed attiva il metodo della classe corrispondente.

10


• Con l’interfaccia Misurabile abbiamo trasferito agli oggetti una caratteristica dei numeri: avere un valore; con i numeri possiamo eseguire somme, trovare un massimo, rappresentare una misura.

• I numeri possono anche essere messi in ordine.

• Possiamo anche ordinare oggetti?


• Prima di tutto ci dobbiamo chiedere se ha senso confrontare oggetti. Lo abbiamo appena fatto cercando il massimo, quindi i confronti possono avere significato.

• Esempio. • Vogliamo mettere in fila dei conti bancari in

modo che siano in ordine da quello con saldo minimo a quello con saldo massimo.

• Vogliamo mettere in fila dei numeri complessi in modo che siano secondo l’ordine crescente del loro modulo (reale).


• Cosa significa per oggetti il dire:

l’oggetto1 è minore (maggiore o uguale) dell’oggetto2?

• Abbiamo già visto con le stringhe che nonpossiamo confrontare i riferimenti.

• Dobbiamo pensare ad una proprietà: “essere confrontabile”.

• Esempio. Per la classe Complex può essere il modulo: è un valore reale, esiste un ordine.


• Nella classe ContoBancario potrebbe essere il saldo, un numero reale, e pensare un ordine dal più povero al più ricco; oppure potrebbe essere il numero di conto, numero intero: dal cliente che per primo ha aperto un conto all’ultimo che lo ha attivato.

• Per la classe Studente potrebbe essere la matricola, numero intero, oppure il nome, una stringa e sappiamo che le stringhe hanno un ordine.


• Nel pacchetto java.lang c’è un’interfaccia che rappresenta la proprietà astratta “essere confrontabile”: l’interfaccia Comparable:

(par. 13.8)public interface Comparable{

int compareTo(Object other);

}

• Il metodo compareTo restituisce un valore intero. La classe String realizza Comparable:

s1.compareTo(s2)

con s1, s2 di tipo String.

Interfaccia Comparable

• Siano a e b due oggetti di una classe che realizza Comparable, si ha:

< 0 a ”precede” b

a.compareTo(b) = 0 a “è uguale a” b

> 0 a “segue” b

• Che cosa significano i termini precede, segue, uguale, dipende dalle scelte che facciamo nelle classi.

11


• Esempio. • Consideriamo la classe Studente con i campi

nome e matricola; stabiliamo un confronto in base alla matricola.

• Nella classe Studente, che realizza Comparable, dobbiamo costruire il metodo compareTo con il codice per esprimere il significato di “confronto tra studenti”.


public int compareTo(Object altrostud)

{Studente altro = (Studente)altrostud;

int valore;

if(this.matricola < altro.matricola)

valore = -1;

else if(matricola > altro.matricola)

valore = 1;

else valore = 0;

return valore;

} //fine CompareTo


• Abbiamo dovuto fare il cast:

Studente altro = (Studente)altrostud;

perché altrostud non possiede il campo matricola, dato che è Object.Possiamo fare altro.matricola perchésiamo nella classe Studente.

• Vediamo la classe ContoBancario che implementa due interfacce.


public class ContoBancario implements

Misurabile, Comparable{

. . .

// metodi: estraiMisura, altriDati

public int compareTo(Object altro){

ContoBancario cb =(ContoBancario)altro;

if(this.saldo < cb. saldo) return -1;

if(this. saldo > cb. saldo) return 1;

return 0;

} //fine compareTo

}//fine CB

/* non e’ strutturato: tre return, ma e’chiaro */


• Possiamo anche confrontare stringhe, ad esempio ordinare gli studenti per nome (purché diversi):

public int compareTo(Object altro){

Studente altrostud = (Studente)altro;

return nome.compareTo(altrostud.nome);

}

dove nome è this.nome e compareTo èquello delle stringhe.


• Ora che sappiamo cosa significa “confrontare oggetti”, possiamo metterli in ordine:

public static void ordlineare (

ContoBancario a[]){

ContoBancario sc;

//ciclo su i

//ciclo su k

if(a[i].compareTo(a[k]) > 0)

//scambiare a[i] con a[k]

}

12


• Se dobbiamo ordinare elementi di tipo Complex o Studente dobbiamo riscrivere l’ordinamento. Possiamo fare meglio?

• All’ordinamento basta avere degli oggetti che siano confrontabili, vale a dire oggetti la cui classe realizzi Comparable.

• In maniera analoga a quanto fatto con Misurabile, andiamo a definire una variabile di “tipo” Comparable e scriviamo un ordinamento per oggetti qualunque.


public static void ordlineare(

Comparable a[]){

//ordinamento per oggetti "confrontabili"

Comparable sc;

for(int i=0; i<a.length-1; i++)

for(int k=i+1; k<a.length; k++)

if(a[i].compareTo(a[k])> 0){

sc = a[i];

a[i] = a[k];

a[k] = sc;

}//fine if

}

Sovrascrivere il metodo equals


• Consideriamo un array di numeri, ci interessa sapere se ci sono oppure no degli elementi ripetuti nella sequenza; esempioa = (1, 3, 2, 7, 3, 4) il 3 è ripetutoa = (1, 2, 4, 7, -5, 0) sono tutti diversiavremo un algoritmo del tipo:

algoritmo boolean distinti (array a)def. variabili diversi logico

i, k intero


diversi ← veroi ← 0

mentre i < a.length -1 e diversi eseguire

per k = i+1 fino a a.length-1 eseguire

se a[i] == a[k]allora diversi ← falso

//fineif//fineperi ← i+1

//finementrerestituire diversi

// fine algoritmo


• Possiamo fare una cosa simile con gli oggetti? La superclasse Object possiede un metodo per verificare se due oggetti sono uguali:public boolean equals(Object ob){

return (this == ob);

}

Il confronto this==ob restituisce vero o falso.

• Il confronto precedente è fatto tra riferimenti, quindi per gestire “oggetti uguali” andiamo a sovrascrivere il metodo equals (come nella classe String). (par. 10.8.2)

13

Sovrascrivere il metodo equalsConfrontiamo in base al numero di conto bancario:public class ContoBancario{

. . .

public boolean equals(Object ob){

ContoBancario ac =(ContoBancario)ob;

if(this.numeroConto ==

ac.numeroConto)

return true;

else

return false;

}//fine equals

}//fine CB


• In CB possiamo anche scegliere di usare compareTo invece di equals:

a.compareTo(b) == 0

corrisponde a a.equals(b) vero

Non per tutti gli oggetti può aver senso cercare l’ordine, mentre l’uguaglianza è una caratteristica degli oggetti.

• Esercizio. Costruire un metodo per verificare se in un array di oggetti ci sono elementi ripetuti.

Struttura di dati lista concatenata

Lista concatenata

• La struttura di dati array memorizza i dati in maniera consecutiva in memoria e l’accesso ai dati viene fatto tramite un indice.

• L’attribuzione dello spazio viene fatta a livello di compilazione e quindi la dimensione dei dati è fissa (anche se poi si usa il raddoppio).

• Per poter costruire una sequenza di informazioni con una dimensione non fissataa priori è necessario agire in maniera diversa: durante l’esecuzione del programma e con locazioni non necessariamente consecutive.

Lista concatenata

• Per poter costruire una sequenza di informazioni non consecutive è necessario che ogni dato della struttura memorizzi un’informazione per collegarsi all’elemento successivo

• Consideriamo una nuova modalità di memorizzare i dati in cui l’accesso non avviene più tramite un indice, ma tramite un indirizzo di memoria.

• Si costruisce una struttura di dati “collegata”, chiamata lista concatenata o catena.

Lista concatenata

• Ogni nodo (anello) di una lista concatenata oltre all’informazione memorizza il riferimento dell’elemento successivo: avremo bisogno di un nodo con le caratteristiche del record per poter rappresentare due (o più) campi di tipo diverso:

dato: inforiferimento: next

14

Lista concatenata

• Il nodo sarà composto da :• l’informazione: un elemento di tipo base o

un oggetto (l’informazione che possiamo memorizzare anche nell’array);

• il riferimento sarà un riferimento ad un nodo (un riferimento ad un elemento dello stesso tipo del nodo).

• Si intuisce che le definizione del nodo sarà un po’ particolare: dobbiamo definire il tipo del nodo, ma al suo interno dobbiamo usare quel tipo per definire il campo riferimento.

Lista concatenata

• Poiché vi si accede tramite un riferimento le informazioni memorizzate non sono piùnecessariamente contigue in memoria, come nell’array.

Lista concatenata

• Supponiamo di voler costruire una struttura di dati lista concatenata per rappresentare una sequenza di interi.

• Sintassi.• Definizione del nodo:

class ElemIntero{int info; //datoElemIntero next; //riferimento

}

Lista concatenata

• Come possiamo gestire l’accesso per la classeElemIntero?

• 1) classe public, elementi private: si devono costruire i metodi per accesso e modifica dei campi;

• 2) controllo di pacchetto (nessuna specifica) sia per la classe che per i campi: l’accesso ai campi è tramite il nome;

• 3) classe interna privata e nessuna specifica sui campi. Adottiamo questa scelta. (par. 14.2)

Lista concatenata• Rappresentiamo un TDA su lista concatenatapublic class TDAsuListaConc{

. . .

//metodi per gestire il TDA

. . .

//classe interna

private class ElemIntero{

int info;

ElemIntero next;

}//fine classe ElemIntero

}

Lista concatenata

• Quale vantaggio e quale sicurezza comporta questa scelta?

• Essendo privata la classe non è visibile dall’esterno: quindi si rispettano per i suoi campi le direttive dell’incapsulamento.

• Essendo interna e non specificando l’accesso i suoi campi sono visibili internamente alla classe che realizza il TDA e si possono utilizzare direttamente, senza dover scrivere in ElemIntero i metodi di accesso e di modifica per i campi.

15

Confronto tra array e lista concatenata

Confronto tra array e lista concatenata

• Mettiamo a confronto le due strutture di dati per ciò che riguarda:

• accesso

• elemento successivo

• inserimento e cancellazione

• dimensione

• spazio di memoria

Accesso: lista concatenata

• L’accesso è sequenziale: per accedere ad un dato si deve scorrere la lista facendo una scansione lineare.

• Di fatto si esegue una “ricerca” nella struttura esaminando i nodi fino a trovare il valore cercato: sia a di tipo ElemIntero, cerchiamo se a.info è uguale ad un valore x, iniziando “dal primo” elemento della struttura “fino all’ultimo” elemento della struttura.

• Non si può ritornare indietro: si può solovedere in avanti.

Accesso: lista concatenata

• L’accesso al campo informazione si ottiene con: a.info

• La struttura è accessibile da un riferimento inizio che “vede” il primo nodo. Si può anche gestire la struttura con un primo elemento privo di informazione: “nodo vuoto”.

x

inizio

Accesso: array

• L’accesso è diretto: per accedere ad un dato si utilizza l’indice dell’array

• Se v è il nome dell’array, v[i] rappresenta l’accesso all’i-esimo elemento: nel nostro esempio x coincide con v[3].

• Con l’accesso diretto non c’è un ordine da rispettare: v[3], v[0], v[5], …: si può tornare indietro.

x

Successivo: lista concatenata

• Ogni nodo, tranne l’ultimo, contiene nel campo next la referenza (indirizzo di memoria) al nodo successivo. Se a è di tipo ElemIntero e a“vede” un nodo della lista, per passare al nodo successivo si memorizza in a il riferimento al nodo successivo:

a = a.next; //riferimento a.next

a

16

Successivo: array

• Dato un elemento nella posizione i , v[i], il successivo (se i ≠ v.length-1) si trova nella posizione i+1; per passare al successivo si fa:

v[++i] oppure i = i+1; uso di v[i]

v[i] v[i+1]

Inserimento e cancellazione: lista concatenata

• Per inserire un nuovo nodo si deve:1) costruire il nuovo nodo2) agganciarlo nella posizione voluta con

assegnazioni sui riferimenti1) costruzione del nuovo nodo:ElemIntero nuovo = new ElemIntero();

nuovo.info = x;

2) per poterlo agganciare bisogna sapere dove.


• Bisogna trovare una “posizione” nella lista, dopo la quale effettuare l’inserimento del nuovo nodo: questa posizione si ottiene facendo la scansione lineare alla ricerca di un valore z (campo info) che dovrà essere presente nella lista.

z

xnuovo.next=a.nexta.next=nuovoa


• Per cancellare un nodo (successivo) bisogna assegnare ad un riferimento next il valore del riferimento successivo:

a.next = a.next.next;

a

Inserimento e cancellazione: array

• Per inserire un nuovo dato nella i-esima posizione si deve:

• 1) aumentare la lunghezza dell’array, se l’array è pieno: costruire un nuovo array w

• 2) copiare i valori fino alla posizione i nel nuovo array, inserire il nuovo elemento, copiare i rimanenti valori (copiare dall’ultimo fino all’i-esimo sul successivo e poi inserire).

• 2 bis) se non serve la posizione intermedia, si può aggiungere il nuovo dato alla fine.

Inserimento e cancellazione: array

• Per cancellare un dato dalla i-esima posizione si deve:

• 1) ricopiare gli elementi a partire dalla posizione i+1 sul precedente

• 1 bis) se l’elemento da togliere è unico e non interessa l’ordine, si può copiare l’ultimo sull’i-esimo posto.

17

Dimensione: lista concatenata

• La dimensione non è fissata: non c’è un limite sulla dimensione massima, l’unico limite è lo spazio di memoria: non bisogna mai ridimensionare una lista concatenata.

• Si può gestire male la memoria e occuparla tutta: se viene esaurita la memoria disponibile la JVM interrompe l’esecuzione segnalando:

OutOfMemoryError

Dimensione: array

• L’array è a dimensione fissa.• Possiamo risolvere il problema con la tecnica

del raddoppio, riassegnando il riferimento della nuova area di memoria al vecchio riferimento.

• Anche in questo caso il limite è lo spazio di memoria complessivo (OutOfMemoryError).

Spazio di memoria: lista concatenata

• La lista concatenata occupa più spazio: ogni nodo è composto da due campi:• l’informazione

• il riferimento

• Se anche l’informazione è un oggetto, il nodo è composto da due riferimenti, uno dei quali vede l’elemento successivo e l’altro l’oggetto.

Spazio di memoria: array

• L’array occupa meno spazio:• c’è solo l’informazione che deve essere

memorizzata• Conclusione.• L’array richiede “spostamento” di dati (O(n))

nel caso di inserimento e cancellazione, che per la lista sono O(1); possiede invece accesso diretto, che è O(1), mentre la lista accesso sequenziale, che è O(n). Pertanto il tipo di problema suggerirà quale struttura di dati sia piùidonea: molti accessi e poche modifiche oppure pochi accessi e molte modifiche.

Lista concatenata

• Se la lista concatenata non ha una dimensione massima dobbiamo però individuarne la fine: un valore di riferimento dal quale non si acceda ad alcun nodo. Tale valore è null.

••••

inizio

Pila su lista concatenata

• Vogliamo ora realizzare il TDA Pila di interi su una lista concatenata: dovremo realizzare gli assiomi: • verifica se la Pila è vuota

• guarda la testa• inserisci in testa• estrai la testa

18


• Dobbiamo avere un riferimento al primo nodo per poter accedere alla struttura di dati:

ElemIntero primo;

• Dobbiamo rappresentare la situazione: Pila vuota. Se la Pila è vuota, non c’è alcun elemento nella Pila, quindi primo non contiene “nulla”:

primo = null;


• Dobbiamo inserire un elemento in testa:• 1) costruiamo un elemento:

ElemIntero nuovo =

new ElemIntero();

nuovo.info = valore;

• 2) agganciamo nuovo in testa: nuovo deve diventare la nuova testa:

nuovo.next = primo; //aggancio alla Pila

primo = nuovo; //nuovo diventa la testa


• Queste assegnazioni valgono anche quando si inserisce il primo elemento, partendo da lista vuota:

nuovo.next = primo; //aggancio alla Pila

primo = nuovo; //nuovo diventa la testa

• Quando la lista è vuota, primo = null; quindi la prima assegnazione memorizza null nel campo nuovo.next: il primo elemento è anche l’ultimo.

• La seconda assegnazione lo fa diventare il primo elemento della lista.


• Dobbiamo estrarre la testa:se la Pila non è vuota:

primo = primo.next;

se la Pila è vuota: lanciamo l’eccezioneEmptyStackException

• Se nella Pila c’è un solo elemento, con l’istruzione precedente si vuota la Pila: infatti, primo.next=null (l’unico è anche l’ultimo), pertanto primo diventa null e quindi la Pila èvuota.


• Dobbiamo guardare la testa:se la Pila non è vuota:

primo.info;

se la Pila è vuota: lanciamo l’eccezioneEmptyStackException

• Vediamo pertanto la classe che realizza una Pila di interi su una lista concatenata.


public class PilaListaConc {

// Pila di interi realizzata con

// lista concatenata

private ElemIntero primo = null;

public boolean vuota() {// isEmpty()

if(primo == null)

return true;

else return false;

}

19


public void inserisci (int elem) {

// push

ElemIntero nuovo =

new ElemIntero();

nuovo.next= primo;

nuovo.info=elem;

primo = nuovo;

}


public void estrai() {// pop

if ( !vuota() )

primo = primo.next;

else

throw new EmptyStackException();

}

public int testa () {// top

if ( !vuota() )

return primo.info;

else

throw new EmptyStackException();

}


/** Classe interna: la classe e'

privata ma le sue variabili

d'istanza sono visibili ai metodi

della classe PilaListaConc */

private class ElemIntero {

int info;

ElemIntero next;

}

}//fine PilaListaConc

Complessità delle operazioni della Pila

• Vogliamo calcolare la complessità delle operazioni che riguardano la realizzazionedegli assiomi della Pila.

• Le prestazioni dipendono dalla struttura di dati e non dal TDA.

• Caso1. Il tempo di esecuzione di ogni operazione su una Pila realizzata con array di dimensioni fisse è costante: abbiamo solo un numero costante di assegnazioni, confronti e ritorno di valore. Il tempo non dipende dalla dimensione n della struttura dati: quindi O(1).


• Caso2. Nella realizzazione con arrayridimensionabile, l’unica cosa che cambia èl’operazione inserisci (push).

• La realizzazione con array ridimensionabile alcune volte richiede un tempo O(n):• tale tempo è necessario per copiare tutti gli

elementi nel nuovo array, all’interno del metodo raddoppio.

• il ridimensionamento viene fatto ogni n operazioni


• Cerchiamo di valutare il costo medio: questo metodo di stima si chiama analisi ammortizzata delle prestazioni asintotiche.

• Per ogni elemento inserito il costo è O(1)• Quando l’array è pieno il ridimensionamento

comporta un ciclo con costo O(n):n inserimenti a costo O(1)

1 inserimento a costo O(n)

20


• Con la notazione O-grande valgono le seguenti relazioni:

O(1) = cO(n) = c · n ⇒⇒⇒⇒ n·O(1) = c · n = O(n) O(n) + O(n) = 2 · c · n = O(n)O(n)/O(n) = c · n/c · n = 1 = O(1)


• Pertanto:costomedio = (n · O(1) + 1 · O(n)) / (n+1) =

= (O(n) + O(n)) / (n+1) == O(1)

• Distribuendo il tempo, speso per il ridimensionamento, in parti uguali su tutte le operazioni push si ottiene ancora O(1).

• Le operazioni sono tutte O(1), tranne pushche è O(1) in media.

Complessità degli assiomi della Pila sulle due strutture di dati

lista concatenata array

1) isEmpty: if(…) O(1) O(1)

2) pop: primo=primo.next O(1) sp — O(1)

3) top: restituisce un valore O(1) O(1)

4) push: nuovo + O(1) raddoppio O(1) 2 assegnazioni in media

Strutture di dati per numeri e oggetti


• Come abbiamo portato agli oggetti le proprietàdei numeri (Misurabile, Comparable) cosìutilizziamo le strutture di dati per memorizzare sia numeri che oggetti: array di numeri e array di oggetti, lista concatenata di numeri e lista concatenata di oggetti.

• In realtà dovremmo dire: array e lista concatenata di riferimenti a oggetti.

• Infatti la struttura di dati gestisce i riferimenti per le operazioni di inserimento, cancellazione, ecc.

Numeri e oggetti

• Array

numeri

oggetti

campi

21

Numeri e oggetti

• Lista concatenata

numeri

oggetti

••••

•


• Quando vogliamo capire come funziona una struttura di dati o cosa fa un TDA, ci basta trattare numeri.

• Quando vogliamo gestire un problema piùgenerale ed utilizzare gli oggetti, aggiungiamo al TDA e alla struttura di dati le caratteristiche dell’oggetto.


• Quando abbiamo introdotto la struttura dati array, l’abbiamo vista per gestire interi (reali).

• Siamo poi passati a considerare array su oggetti.• Per memorizzare informazioni che riguardavano

degli studenti abbiamo introdotto la classe Stud, per accedere al campo matricola dell’i-esimo studente dobbiamo individuare la posizione e poi il campo, tramite un metodo di accesso:

corso23[i].matricola()


• Se vogliamo costruire una lista concatenata per informazioni di tipo Stud dovremo definire il nodo:

class ElemStud{

Stud info;

ElemStud next;

}

e per accedere al campo matricola da un riferimento a che vede il nodo:

a.info.matricola()

Conversioni di tipo fra sottoclasse e superclasselaurap/didattica/Informatica... · 2010. 5....

Documents

Transcript of Conversioni di tipo fra sottoclasse e superclasselaurap/didattica/Informatica... · 2010. 5....