realizzazione di tipi astratti di dato in java...
TRANSCRIPT
![Page 1: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/1.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Realizzazione di Tipi Astratti di Dato in JavaLaboratorio di Programmazione IICorso di Laurea in Bioinformatica
Dipartimento di Informatica - Università di Verona
![Page 2: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/2.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Realizzazione di Tipi Astratti di Dato
![Page 3: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/3.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Tipi Astratti di Dato
Tipo Astratto di DatoPermette di specificare dati in modo astrattoAstratto
Indipendentemente dal linguaggio (e.g., Java, C++, etc.)Indipendentemente dalla modalità di realizzazione (e.g.,List, ArrayList, LinkedList)
![Page 4: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/4.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Tipi Astratti di Dato
DefinizioneOggetto matematico costituito da:
1 dominio del tipo (o dominio di interesse): insieme deivalori validi per il tipo
2 funzioni: operazioni che possono essere effettutate suivalori del tipo
Example (Il tipo Boolean)
1 Dominio di interesse: true, false2 Funzioni: not, or, and, etc.
![Page 5: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/5.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Esempio: Lista
ADT Listadominio del tipo: L Liste di elementi di un certo tipo T
Operazioni:1 isEmpty(L): L ⇒ B vero se la lista L è vuota (B =
Boolean)2 get(L,k): L × N ⇒ T oggetto (di tipo T ) in posizione k
nella lista L (N = interi positivi)3 lenght(L): L ⇒ N il numero di oggetti contenuti in L4 remove(L,k): L × N ⇒ T × L oggetto in posizione k nella
lista L, ed una Lista L′ risultante da L in cui l’oggetto inposizione k viene rimosso.
5 insert(L,k,u): L × N × T ⇒ L Lista L′ risultante da L incui viene aggiunto l’oggetto u in posizione k .
![Page 6: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/6.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Realizzare ADT in Java
ADT in JavaElementi fondamentali della realizzazione di un ADT
Interfaccia che definisce le operazioni (e.g. Lista.java)Scelta della rappresentazione (i.e., come rappresentare leinformazioni)Schema Realizzativo
![Page 7: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/7.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Schema Realizzativo
Modalità principaliModalità di realizzazione delle operazioniDue schemi principali
1 side effect: i metodi della classe operano modifiche suoggetti di moduli cliente
2 funzionale: i metodi della classe calcolano valori senzamodificare gli oggetti della classe
![Page 8: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/8.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Realizzazione con Side Effect
Side EffectModifica gli oggettiSi discostano notevolmente dalla definizione matematice diADT (concetto di oggetto)Efficienti: metodi agiscono direttamente sugli oggettiDanno luogo ad oggetti mutabili
Example (Side Effect)
StringBuffer sba = new StringBuffer("Ciao");StringBuffer sbb = sba;sba.append("!");System.out.println("StringBuffer sba = "+sba);System.out.println("StringBuffer sbb = "+sbb);
![Page 9: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/9.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Realizzazione funzionale
FunzionaleNon modificano mai gli oggetti di invocazione marestituiscono un nuovo oggetto per ogni operazione dimodifica
Insert per Lista funzionaleLista insert(int k, Object o)...
Molto simili alla definizione matematica dell’ADTTipicamente meno efficienti, ma più sicuriDanno luogo ad oggetti immutabili
Example (Oggetti immutabili)
String sa = new String("Ciao");String sb = sa;sa = sa.concat("!");System.out.println("Stringa sa = "+sa);System.out.println("Stringa sb = "+sb);
![Page 10: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/10.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Uguaglianza per ADT
Uguaglianza profonda
promemoria ==⇒ uguaglianza tra riferimenti (uguaglianzasuperficiale)promemoria metodo equals(Object) della classe Objectpuo’ essere re-implementato da tutte le classi derivate(overriding)promemoria metodo equals di default controllal’uguaglianza superficialeuguaglianza profonda: uguaglianza basata sulleinformazioni contenute nell’oggettoPer ADT è consigliabile re-implementare equals perottenere l’uguaglianza profonda
![Page 11: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/11.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Utilizzo Java API per implementare ADT
![Page 12: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/12.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Utilizzo API per ADT
API per ADTADT più importanti sono implementati nelle API di JAVAUtilizzo librerie disponibili riduce notevolmente il tempo disviluppo (e soprattutto il debug)
![Page 13: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/13.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
ADT lineari: Lista
API per ListaInterfaccia ListMolte realizzazioni, in particolare:
ArrayList: basata su arrayLinkedList: basata su strutture collegate
![Page 14: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/14.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Utilizzo delle API per ADT Lista
Esempio: ArrayList
Creazione: List l = new ArrayList();Utilizzo:
aggiunta oggetto: l.add(new Integer(3))accesso oggetto: int pos= ...; l.get(pos)scansione:for (int i = 0; i < l.size(); i++) {
System.out.println(i+ " " + l.get(i));}
![Page 15: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/15.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Note su utilizzo API
NoteArrayList e LinkedList implementano l’interfaccia ListquindiUtilizzare ArrayList o LinkedList per istanziare un oggettodi tipo List è trasparente in fase di compilazione
Esempio: metodo fill() classe TestList.javaLa particolare realizzazione impatta sull’efficienza delcodice: tempo esecuzione e memoria
ArrayList: ri-allocazione del vettore se necessarioLinkedList: accesso sequenziale
![Page 16: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/16.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Liste e tipo degli elementi contenuti
Liste e tipo degli elementiADT lista: sequenza di elementi di un solo tipoIn java posso inserire in una lista elementi di tipi diversi,perchè tutto deriva da ObjectSi discosta dal ADT e crea problemi a tempo di esecuzione
Example (Esempio di lista con elementi eterogenei)
List lista = new ArrayList();lista.add(new Studente("001"));lista.add(new Studente("002"));lista.add(new Integer(3));
![Page 17: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/17.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Forzare liste di elementi omogenei
Il meccanismo della parametrizzazione del tipoGenerics o tipi parametrizzatiDichiaro al momento della creazione quali elementi sarannoinseriti nella lista
List<tipoElemento> listaT = newArrayList<tipoElemento>()
Il compilatore controlla che il vincolo sul tipo degli elementisia rispettato
listaT.add(elementoTipoNonCorretto) errore a tempo dicompilazione
Esempio: TestGenerics.java
![Page 18: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/18.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Leggere le API di java
Come leggere le API
informazioni principali per ciascuna classe:Classi e/o interfacce che vengono estese e/o realizzatedalla classe correnteClassi e/o interfacce che implementano e/o estendono laclasse correnteEventuale parametrizzazione dei tipiPackage da includere (e.g. import java.util.*);
![Page 19: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/19.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Esercizi
Esercizi API1 realizzare il metodo elimina doppi della classe UtilList.java
utilizzando ArrayList o LinkedList2 realizzare il metodo sottoSequenza della classe UtilList.java
utilizzando LinkedList o ArrayList3 realizzare il metodo stampa inversi della classe UtilList.java
utilizzando la classe Stack
![Page 20: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/20.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Nota sull’interfaccia Comparable
Utilizzo appropriato di Comparable<E>1 l’interfaccia comparable utilizza un tipo parametrizzato
Comparable<E>2 E e’ il tipo degli elementi con cui la classe che implementa
l’interfaccia puo’ essere comparata.3 Permette di evitare il downcast nel compareTo() ed evita
warning in compilazione4 Vedi UtilComparable.java e StudenteTypeSafe.java
![Page 21: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/21.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Collezioni di Oggetti
![Page 22: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/22.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Collezioni di oggetti
CollezioniLista è una particolare tipologia di collezione di oggettiNe esistono molte altre: Pila, Coda, Insieme etc.Le tipologie di collezioni principali sono realizzate nellelibrerie Java di baseL’interfaccia Collection rappresenta i metodi di base peruna qualsiasi collezione
![Page 23: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/23.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Collezioni in Java I
Interfaccia Collection
![Page 24: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/24.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Collezioni in Java II
Interfaccia Collection: metodi
![Page 25: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/25.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
ADT Insieme
InsiemeDominio di interesse: è formato da insiemi di elementi diun certo dominio EOperazioni:
1 emptySet(), che restituisce il valore corrispondenteall’insieme vuoto.
2 isEmpty(i), che restituisce true se l’insieme i è l’insiemevuoto, false altrimenti.
3 add(i,e), che restituisce l’insieme j ottenuto dall’insieme iaggiungendo l’elemento e; se e appartiene già a i allora jcoincide con i.
4 remove(i,e), che restituisce l’insieme j ottenuto dall’insiemei eliminando l’elemento e; se e non appartiene a i allora jcoincide con i.
5 contains(i,e), che restituisce true se l’elemento eappartiene all’insieme i, false altrimenti.
![Page 26: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/26.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
ADT Insieme in Java
Interfaccia Set
![Page 27: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/27.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
ADT Insieme in Java: caratteristiche
Interfaccia Set caratteristicheTipo parametrizzato: E rappresenta il tipo degli elementidell’insiemeMette a disposizione molti metodi oltre alle operazioni dibase (e.g. addAll(...), removeAll(...), retainAll(...))Insieme di Interi: Set<Integer> insiemeInteri = ...L’interfaccia Set viene realizzata da numerose classi
1 HashSet: operazioni di base in tempo costante (sottoopportune ipotesi)
2 TreeSet: operazioni di base in tempo O(log n)
Un insieme non puo’ avere occorrenze multiple di elementi,questo viene garantito dai metodi che gestiscono l’insieme(tutti i metodi add)
![Page 28: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/28.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Utilizzo Set
HashSetDichiarazione
Set<Integer> s1 = new HashSet<Integer>();
Aggiunta elementis1.add(new Integer(1));
Aggiunta di una collezione di elementis1.addAll(collezione);
![Page 29: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/29.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Set: Accesso agli elementi
IteratoriNon esiste il concetto di posizione di un elemento
non esiste il metodo s.get(i) dove i è la posizionedell’elemento
Si utilizzano gli iteratoriUn iteratore è un riferimento ad un oggetto contenuto inuna collezionePermettono di accedere in maniera sequenziale qualsiasicollezione (pile,liste,code,insiemi, etc.)
![Page 30: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/30.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Utilizzo iteratori
Creare un iteratoreData una collezione c
Collection<T> c = ...
iterator() metodo della collezione, restituisce un iteratore alprimo elemento della collezione
Iterator<T> it = c.iterator();
![Page 31: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/31.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Utilizzo degli iteratori
iteratoriDato un iteratore
Iterator<T> it = c.iterator();
metodo hasNext() restituisce true se la collezione su cuil’iteratore agisce ha almeno un altro elemento
for(Iterator<T> it = c.iterator(); it.hasNext();)
metodo next() restituisce l’elemento a cui l’iteratore siriferisce ed aggiorna l’iteratore al prossimo elemento dellacollezione.
for(Iterator<T> it = c.iterator(); it.hasNext();)T elemento = it.next()
esempio di scansione di tutti gli elementi di un insieme:calcolaMedia(Set<Integer>) della classe TestSet.java
![Page 32: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/32.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Esercizi
Esercizi su SetImplementare il metodomigliorMedia(Set<Set<Integer>>)
della classe TestSet.javaImplementare il metodointersezione(Set<Integer>, Set<Integer>)
della classe TestSet.java
![Page 33: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/33.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Sottoinsiemi di un insieme (insieme delle parti)
Insieme delle parti (power set)
dato un insieme S il power set P(S) è l’insieme di tutti isottoinsiemi di sS = {1, 2}, P(S) = {{}, {1}, {2}, {1, 2}}concetto molto importante per algoritmi a forza bruta
![Page 34: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/34.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Calcolo ricorsivo dell’ insieme delle parti
Insieme delle parti: calcolo ricorsivo
dato un insieme di elementi S ed un insieme (di insiemi) Tdetta F(e, T ) = {X ∪ {e}|X ∈ T }definizione ricorsiva:
P(S) = {∅} se S = ∅e primo elemento di S , T = S \ {e},P(S) = P(T ) ∪ F(e,P(T ))
![Page 35: Realizzazione di Tipi Astratti di Dato in Java ...profs.sci.univr.it/~farinelli/courses/algBio/slides/RealizzazioneADT.pdf · Realizzazione di Tipi Astratti di Dato in Java Realizzazione](https://reader034.vdocumenti.com/reader034/viewer/2022052000/6012a48ca14a680c475ad3d5/html5/thumbnails/35.jpg)
Realizzazionedi Tipi
Astratti diDato in Java
Realizzazionedi TipiAstratti diDato
Utilizzo JavaAPI per im-plementareADT
Collezioni dioggetti
Esercizi
Esercizi su SetImplementare il metodo sottoinsiemi(Set<Integer>) dellaclasse TestSet.java