Roadmap - tritone.ing.unibs.ittritone.ing.unibs.it/fp/Slides/VersionePDF/13-StruttureDati...Modulo...

Modulo di Fondamenti di Programmazione P. Baroni - P.Martinelli - M. Rossi - A. Viola

Strutture dati + Generics 1

Fondamenti di Programmazione

RoadmapRoadmap

•• 0. Primi passi con Java0. Primi passi con Java

•• 1. Buone abitudini1. Buone abitudini

•• 2. Tipi di dati primitivi2. Tipi di dati primitivi

•• 3. Uso di classi3. Uso di classi

•• 4. Leggere e scrivere4. Leggere e scrivere

•• 5. Definire metodi5. Definire metodi

•• 6. Strutture di controllo6. Strutture di controllo

•• 7. 7. Array Array e e CollectionCollection

•• 8. Progetto di classi8. Progetto di classi

•• 9. Ereditarietà9. Ereditarietà

•• 10. Eccezioni10. Eccezioni

•• 11. 11. StreamStream

•• 12. 12. RicorsioneRicorsione

•• 13. Strutture dati + 13. Strutture dati + GenericsGenerics


Strutture dati "classiche"Strutture dati "classiche"

•• Tipi di dati astratti, di uso generale, per i quali Tipi di dati astratti, di uso generale, per i quali sono definiti alcuni metodi standardsono definiti alcuni metodi standard

•• Data la loro struttura generale e la loro utilità Data la loro struttura generale e la loro utilità universale, possono venire realizzate in universale, possono venire realizzate in qualunque linguaggio di programmazionequalunque linguaggio di programmazione

•• Spesso hanno natura Spesso hanno natura ricorsivaricorsiva

•• Esamineremo dapprima le strutture fornite Esamineremo dapprima le strutture fornite dalla libreria Java, quindi dalla libreria Java, quindi vedemovedemo come come scriverne noiscriverne noi




Java Java Collection FrameworkCollection Framework

•• A partire da Java 2, il package java.A partire da Java 2, il package java.util util contiene il Java contiene il Java CollectionCollection FrameworkFramework (JCF) (JCF) un insieme di interface, classi e classi astratte un insieme di interface, classi e classi astratte progettate organicamente per facilitare la progettate organicamente per facilitare la creazione e l’utilizzo di vari tipi di strutture creazione e l’utilizzo di vari tipi di strutture dati collettivedati collettive

•• Alcune classi esistenti nelle versioni Alcune classi esistenti nelle versioni precedenti (p.e. precedenti (p.e. VectorVector) sono state riadattate ) sono state riadattate in modo da far parte del JCFin modo da far parte del JCF


Un Un framework framework complessocomplesso

•• Il JCF ha subito costanti evoluzioni (e ingrandimenti) in Il JCF ha subito costanti evoluzioni (e ingrandimenti) in tutte le versioni di Java seguite alla 1.2tutte le versioni di Java seguite alla 1.2

•• Nella versione 6 esso comprende: 19 interface (5 di Nella versione 6 esso comprende: 19 interface (5 di supporto), 6 classi astratte, 12 classi supporto), 6 classi astratte, 12 classi istanziabiliistanziabili di uso di uso generale, 2 classi contenenti solo metodi generale, 2 classi contenenti solo metodi static static di di utilità, 16 classi per usi speciali, 2 classi di eccezioniutilità, 16 classi per usi speciali, 2 classi di eccezioni

•• Vedremo alcune nozioni generali, per un’analisi Vedremo alcune nozioni generali, per un’analisi dettagliata è più produttivo consultare la dettagliata è più produttivo consultare la documentazionedocumentazione




RoadmapRoadmap

•• 13. Strutture dati + 13. Strutture dati + GenericsGenericsTipi di dati parametriciTipi di dati parametrici


Tipi di dati parametriciTipi di dati parametrici(da Java 1.5 in poi)(da Java 1.5 in poi)

•• Come già visto implicitamente per i Come già visto implicitamente per i VectorVector, le , le definizioni di interface e classi nel JCF sono definizioni di interface e classi nel JCF sono parametriche rispetto ad altri tipi di datiparametriche rispetto ad altri tipi di dati

•• Ad esempio, la nozione di Ad esempio, la nozione di Vector Vector è quella di un è quella di un contenitore di qualunque tipo di dato al suo interno, contenitore di qualunque tipo di dato al suo interno, pertanto essa è parametrica rispetto al tipo di dato pertanto essa è parametrica rispetto al tipo di dato contenutocontenuto

•• Sintatticamente questo è espresso dalle parentesi Sintatticamente questo è espresso dalle parentesi angolari <> che racchiudono il tipo di dato angolari <> che racchiudono il tipo di dato parametricoparametrico




Tipi di dati parametriciTipi di dati parametrici

public class public class VectorVector<E><E>

. . .. . .

Vector Vector <<StringString> elenco = new > elenco = new VectorVector<<StringString>();>();

La documentazione riporta la definizione che è parametrica rispetto ad un tipo di dato generico E

Quando si utilizza concretamente la classe, il tipo generico viene sostituito con un tipo specifico (in questo caso String)


RoadmapRoadmap


Le interface Le interface CollectionCollection, , IterableIterable, , IteratorIterator




L’interface L’interface CollectionCollection

public interface public interface CollectionCollection<E> <E> extends Iterableextends Iterable

•• E’ l’interface basilare del JCF e rappresenta una E’ l’interface basilare del JCF e rappresenta una raccolta generica di oggetti di tipo raccolta generica di oggetti di tipo EE

•• E’ implementata dalla maggior parte delle classi E’ implementata dalla maggior parte delle classi (anche astratte) del JCF(anche astratte) del JCF

•• Specifica 15 metodi di cui 6 opzionaliSpecifica 15 metodi di cui 6 opzionali

•• Uno dei metodi più significativi è Uno dei metodi più significativi è iteratoriterator(), ereditato (), ereditato a sua volta dall’interface a sua volta dall’interface IterableIterable



boolean addboolean add(E e) (E e) Ensures that this collection containsEnsures that this collection contains the the specified element specified element (optional (optional operationoperation).).

boolean addAllboolean addAll((CollectionCollection<? <? extendsextends E> c) E> c) Adds allAdds all of the of the elementselements in the in the specified collection to this specified collection to this collectioncollection (optional (optional operationoperation). ).

void clearvoid clear() () Removes allRemoves all of the of the elements from this collectionelements from this collection (optional (optional operationoperation). ).

boolean containsboolean contains((ObjectObject o) o) Returns true if this collection containsReturns true if this collection contains the the specified elementspecified element..

boolean containsAllboolean containsAll((CollectionCollection<?> c) <?> c) Returns true if this collection contains allReturns true if this collection contains all of the of the elementselements in in the the specified collectionspecified collection. .

boolean equalsboolean equals((ObjectObject o) o) ComparesCompares the the specified object with this collection for equalityspecified object with this collection for equality. .

Sorvoliamo su alcuni dettagli da approfondire in seguito




L’interface L’interface CollectionCollectionint hashCodeint hashCode() ()

ReturnsReturns the the hashhash code code value for this collectionvalue for this collection. .

boolean isEmptyboolean isEmpty() () Returns true if this collection containsReturns true if this collection contains no no elementselements..

IteratorIterator<E> <E> iteratoriterator() () Returns an iteratorReturns an iterator over the over the elementselements in in this collectionthis collection..

boolean removeboolean remove((ObjectObject o) o) RemovesRemoves a single a single instanceinstance of the of the specified element from this specified element from this collectioncollection, , if it is presentif it is present (optional (optional operationoperation).).

boolean removeAllboolean removeAll((CollectionCollection<?> c) <?> c) Removes allRemoves all of of this collection's elements thatthis collection's elements that are are also also containedcontained in the in the specified collectionspecified collection (optional (optional operationoperation).).

boolean retainAllboolean retainAll((CollectionCollection<?> c) <?> c) Retains onlyRetains only the the elementselements in in this collection that this collection that are are containedcontainedin the in the specified collectionspecified collection (optional (optional operationoperation). ).




int sizeint size() () ReturnsReturns the the numbernumber of of elementselements in in this collectionthis collection. .

ObjectObject[] [] toArraytoArray() () Returns an array containing allReturns an array containing all of the of the elementselements in in this this collectioncollection. .

<T> T[] <T> T[] toArraytoArray(T[] a) (T[] a) Returns an array containing allReturns an array containing all of the of the elementselements in in this this collectioncollection; the ; the runtime typeruntime type of the of the returned array is thatreturned array is that of of the the specified arrayspecified array. .





L’interface L’interface IterableIterable

public interface public interface IterableIterable<T><T>

•• L’interface L’interface IterableIterable specifica un solo metodo:specifica un solo metodo:

IteratorIterator<T> <T> iteratoriterator()()

•• Il metodo Il metodo iteratoriterator() restituisce un riferimento () restituisce un riferimento a un a un IteratorIterator<T> ovvero a un <T> ovvero a un iteratore iteratore sul sul tipo di oggetti contenuti nella tipo di oggetti contenuti nella CollectionCollection

•• Iterator Iterator è a sua volta un’interfaceè a sua volta un’interface


L’interface L’interface IteratorIterator

public interface public interface IteratorIterator<E><E>

•• L’interface L’interface IteratorIterator specifica i metodi che deve specifica i metodi che deve fornire un “fornire un “iteratoreiteratore” ovvero un oggetto capace di ” ovvero un oggetto capace di scorrere uno a uno gli elementi di una raccoltascorrere uno a uno gli elementi di una raccolta

boolean hasNextboolean hasNext() () Returns true ifReturns true if the the iteration hasiteration has more more elementselements. .

E E nextnext() () ReturnsReturns the the next elementnext element in the in the iterationiteration. .

void removevoid remove() () Removes fromRemoves from the the underlying collectionunderlying collection the the last last element returned byelement returned by the the iteratoriterator (optional (optional operationoperation). ).




Uso di Uso di iteratoriiteratori

•• Gli Gli iteratori iteratori offrono un modo alternativo (e offrono un modo alternativo (e tecnicamente più efficiente) di eseguire un tecnicamente più efficiente) di eseguire un operazione su tutti gli elementi di una operazione su tutti gli elementi di una CollectionCollection

VectorVector <<StringString> elenco = new > elenco = new VectorVector<<StringString>();>();. . .. . .IteratorIterator<<StringString> lancetta = elenco.> lancetta = elenco.iteratoriterator();();while while (lancetta.(lancetta.hasNexthasNext())())System.out.System.out.printlnprintln(lancetta.(lancetta.nextnext());());


RoadmapRoadmap



Famiglie di Famiglie di CollectionCollection: Set, List, : Set, List, QueueQueue, , DequeDeque




Famiglie di Famiglie di CollectionCollection

•• La documentazione di JCF indica 3 principali La documentazione di JCF indica 3 principali famiglie di famiglie di CollectionCollection, corrispondenti alle , corrispondenti alle seguenti interface che ereditano da seguenti interface che ereditano da CollectionCollection::–– Set<E>Set<E>

–– List <E>List <E>

–– QueueQueue<E> e <E> e DequeDeque <E><E>


L’interface SetL’interface Set

•• Un Set è una Un Set è una Collection Collection con il vincolo con il vincolo aggiuntivo di non contenere elementi duplicati aggiuntivo di non contenere elementi duplicati (come gli insiemi della teoria degli insiemi)(come gli insiemi della teoria degli insiemi)

•• Di fatto non aggiunge la specifica di nuovi Di fatto non aggiunge la specifica di nuovi metodi a quelli ereditati da metodi a quelli ereditati da Collection Collection ma ma aumenta i requisiti di alcuni metodi (p.e. aumenta i requisiti di alcuni metodi (p.e. addadd) ) in modo che sia garantita la non duplicazionein modo che sia garantita la non duplicazione




Le interface Le interface SortedSetSortedSet

•• L’interface L’interface SortedSet SortedSet estende Set con il requisito che estende Set con il requisito che esista una relazione di ordine totale tra gli elementi esista una relazione di ordine totale tra gli elementi (siano tutti confrontabili)(siano tutti confrontabili)

•• Questo rende possibile la specifica di metodi Questo rende possibile la specifica di metodi aggiuntivi: aggiuntivi: –– la selezione del primo o ultimo elemento nell’ordinela selezione del primo o ultimo elemento nell’ordine

–– la selezione di tutti gli elementi prima o dopo un certo la selezione di tutti gli elementi prima o dopo un certo elemento elemento

–– la selezione degli elementi in un certo la selezione degli elementi in un certo range range


Le interface Le interface NavigableSetNavigableSet

•• L’interface L’interface NavigableSetNavigableSet estende estende SortedSetSortedSetcon svariati metodi di utilità aggiuntiva tra i con svariati metodi di utilità aggiuntiva tra i quali: quali: –– la selezione dell’elemento più vicino (prima o dopo la selezione dell’elemento più vicino (prima o dopo

nell’ordine, con o senza uguaglianza) rispetto a un nell’ordine, con o senza uguaglianza) rispetto a un elemento specificato elemento specificato

–– la possibilità di enumerare il Set in ordine inversola possibilità di enumerare il Set in ordine inverso

–– . . .. . .




L’interface ListL’interface List

•• Una List è una Una List è una Collection Collection nella quale gli nella quale gli elementi sono ordinati elementi sono ordinati posizionalmente posizionalmente e e sono disponibili operazioni (accesso, sono disponibili operazioni (accesso, inserimento, eliminazione, ricerca, estrazione, inserimento, eliminazione, ricerca, estrazione, sostituzione) riferite ad indici posizionalisostituzione) riferite ad indici posizionali

•• Oltre Oltre all’Iterator all’Iterator “modello base” è possibile “modello base” è possibile creare un creare un ListIterator ListIterator che permette che permette “movimenti” “movimenti” bidirezionali bidirezionali sulla List ed sulla List ed operazioni di modifica del operazioni di modifica del contenuocontenuo


Operazioni posizionali su ListOperazioni posizionali su List

void addvoid add((int indexint index, E , E elementelement) ) InsertsInserts the the specified elementspecified element at the at the specifiedspecified position in position in thisthislist (optional list (optional operationoperation).).

boolean addAllboolean addAll((int indexint index, , CollectionCollection<? <? extendsextends E> c) E> c) Inserts allInserts all of the of the elementselements in the in the specified collection into thisspecified collection into thislist at the list at the specifiedspecified position (optional position (optional operationoperation).).

E E getget((int indexint index) ) ReturnsReturns the the elementelement at the at the specifiedspecified position in position in thisthis list. list.

int indexOfint indexOf((ObjectObject o) o) ReturnsReturns the the indexindex of the first of the first occurrenceoccurrence of the of the specified elementspecified elementin in thisthis list, or list, or --1 1 if thisif this list list does not containdoes not contain the the elementelement..

int lastIndexOfint lastIndexOf((ObjectObject o) o) ReturnsReturns the the indexindex of the of the last occurrence last occurrence of the of the specified elementspecified elementin in thisthis list, or list, or --1 1 if thisif this list list does not containdoes not contain the the elementelement..

Inserimento

Accesso

Ricerca: si cerca un elemento tale che o.equals(elemento) sia true




Operazioni posizionali su ListOperazioni posizionali su List

E E removeremove((int indexint index) ) RemovesRemoves the the elementelement at the at the specifiedspecified position in position in thisthis list list (optional (optional operationoperation).).

E set(E set(int indexint index, E , E elementelement) ) ReplacesReplaces the the elementelement at the at the specifiedspecified position in position in thisthis list list withwiththe the specified elementspecified element (optional (optional operationoperation).).

List<E> List<E> subListsubList((int fromIndexint fromIndex, , int toIndexint toIndex) ) ReturnsReturns a a viewview of the of the portionportion of of thisthis list list betweenbetween the the specified specified fromIndexfromIndex, inclusive, and , inclusive, and toIndextoIndex, , exclusiveexclusive. .

Eliminazione

Sostituzione

Estrazione di una sottolista tra due posizioni (la prima inclusa, la seconda no)


L’interface L’interface ListIteratorListIterator

•• Si può creare un Si può creare un ListIterator ListIterator in due modi (a in due modi (a partire dall’inizio della lista o da una posizione partire dall’inizio della lista o da una posizione specificata)specificata)

ListIteratorListIterator<E> <E> listIteratorlistIterator() () ReturnsReturns a list a list iteratoriterator over the over the elementselements in in thisthislist (in list (in proper sequenceproper sequence). ).

ListIteratorListIterator<E> <E> listIteratorlistIterator((int indexint index) ) ReturnsReturns a list a list iteratoriterator of the of the elementselements in in thisthislist (in list (in proper sequenceproper sequence), ), startingstarting at the at the specifiedspecified position in position in thisthis list. list.





•• Oltre ai due metodi per “scorrere avanti” ed al Oltre ai due metodi per “scorrere avanti” ed al removeremove disponibili in disponibili in IteratorIterator, offre:, offre:–– due metodi duali per “scorrere indietro” due metodi duali per “scorrere indietro”

–– due metodi per sapere in che posizione è due metodi per sapere in che posizione è l’iteratorel’iteratore

–– aggiunta e sostituzione di un elementoaggiunta e sostituzione di un elemento



boolean hasPreviousboolean hasPrevious() () Returns true if thisReturns true if this list list iterator hasiterator has more more elements elements when traversingwhen traversing the list in the the list in the reversereverse direction.direction.

E E previousprevious() () ReturnsReturns the the previous elementprevious element in the list.in the list.

int nextIndexint nextIndex() () ReturnsReturns the the indexindex of the of the element that would be returned element that would be returned byby a a subsequent call to nextsubsequent call to next..

int previousIndexint previousIndex() () ReturnsReturns the the indexindex of the of the element that would be returned element that would be returned byby a a subsequent call to previoussubsequent call to previous..

Scorrimento “all’indietro”

Posizione dell’iteratore




L’interface L’interface ListIteratorListIteratorvoid addvoid add(E e) (E e)

InsertsInserts the the specified element intospecified element into the list the list (optional (optional operationoperation).).

voidvoid set(E e) set(E e) ReplacesReplaces the the last element returned by nextlast element returned by next or or previous withprevious with the the specified elementspecified element (optional (optional operationoperation).).

void removevoid remove() () Removes fromRemoves from the list the the list the last element that was last element that was returned by nextreturned by next or or previousprevious (optional (optional operationoperation). ).

L’operazione di aggiunta è riferita alla posizione dell’iteratore

Le operazioni set e remove sono riferite all’ultimo elemento acceduto con next o previous (se non esiste o è stato già eliminato, si ha un’eccezione)


Prima di Prima di addadd

nextprevious

0 1 2 size()-1

. . .




Dopo Dopo addadd

0 1nextprevious

2 3

. . .


L’interface L’interface QueueQueue

•• Rappresenta una coda ovvero una struttura Rappresenta una coda ovvero una struttura dove si inseriscono elementi (ingresso in dove si inseriscono elementi (ingresso in coda) e solo un elemento (la testa della coda) coda) e solo un elemento (la testa della coda) è disponibile per l’accesso o per l’estrazione è disponibile per l’accesso o per l’estrazione (uscita dalla coda)(uscita dalla coda)

•• La politica di selezione dell’elemento in testa La politica di selezione dell’elemento in testa è tipicamente FIFO ma sono possibili anche è tipicamente FIFO ma sono possibili anche code con “scavalcamento” basato su qualche code con “scavalcamento” basato su qualche criterio di ordinamento o prioritàcriterio di ordinamento o priorità





•• Esistono tre operazioni base su una Esistono tre operazioni base su una QueueQueue::–– inserimento di un elemento in codainserimento di un elemento in coda

–– accesso all’elemento in testa (senza toglierlo dalla accesso all’elemento in testa (senza toglierlo dalla coda)coda)

–– estrazione dell’elemento in testa (eliminandolo estrazione dell’elemento in testa (eliminandolo dalla coda)dalla coda)

•• Di ognuna esistono due versioni a seconda Di ognuna esistono due versioni a seconda del comportamento quando l’operazione non del comportamento quando l’operazione non è possibile: una lancia un’eccezione, l’altra è possibile: una lancia un’eccezione, l’altra ritorna false o ritorna false o nullnull



•• Lanciano eccezioneLanciano eccezione

boolean add(E e) Aggiunta elemento

E element() Accesso elemento in testa

E remove() Estrazione elemento in testa

•• Non lanciano eccezioneNon lanciano eccezione

boolean offer(E e) Aggiunta elemento

E peek() Accesso elemento in testa

E poll() Estrazione elemento in testa




L’interface L’interface DequeDeque

•• Il nome Il nome Deque Deque sta per “sta per “double ended queuedouble ended queue” è ” è un’interface che estende un’interface che estende Queue Queue poiché rappresenta poiché rappresenta una struttura con due estremi (testa e coda, head e una struttura con due estremi (testa e coda, head e tailtail) ed operazioni di inserimento, accesso ed ) ed operazioni di inserimento, accesso ed estrazione su entrambi gli estremiestrazione su entrambi gli estremi

•• Come nel caso precedente, per ogni operazione Come nel caso precedente, per ogni operazione esistono due versioni (una lancia eccezioni, una no)esistono due versioni (una lancia eccezioni, una no)

•• I metodi ereditati da I metodi ereditati da Queue Queue sono “affiancati” da sono “affiancati” da metodi equivalenti con nomi più specificimetodi equivalenti con nomi più specifici


DequeDeque: operazioni in testa: operazioni in testa


boolean addFirst(E e) Aggiunta elemento in testa

E getFirst () Accesso elemento in testa

E removeFirst () Estrazione elemento in testa


boolean offerFirst (E e) Aggiunta elemento in testa

E peekFirst () Accesso elemento in testa

E pollFirst () Estrazione elemento in testa




DequeDeque: operazioni in coda: operazioni in coda


boolean addLast(E e) Aggiunta elemento in coda

E getLast () Accesso elemento in coda

E removeLast () Estrazione elemento in coda


boolean offerLast (E e) Aggiunta elemento in coda

E peekLast () Accesso elemento in coda

E pollLast () Estrazione elemento in coda


DequeDeque: metodi aggiuntivi: metodi aggiuntivi

IteratorIterator<E> <E> descendingIteratordescendingIterator() () Returns an iteratorReturns an iterator over the over the elementselements in in this dequethis deque in in reverse reverse sequential ordersequential order..

boolean removeFirstOccurrenceboolean removeFirstOccurrence((ObjectObject o) o) RemovesRemoves the first the first occurrenceoccurrence of the of the specified element from this specified element from this dequedeque. .

boolean removeLastOccurrenceboolean removeLastOccurrence((ObjectObject o) o) RemovesRemoves the the last occurrencelast occurrence of the of the specified element from this specified element from this dequedeque. .




RoadmapRoadmap




La nozione di La nozione di StackStack


La nozione di La nozione di stackstack (pila)(pila)

Operazioni solo sulla cima della pila:push (aggiunta),pop (estrazione),peek (accesso)




La nozione di La nozione di stackstack

•• Uno Uno stack stack è una forma limitata di è una forma limitata di Deque Deque nella nella quale si opera sempre in testa e mai in codaquale si opera sempre in testa e mai in coda

•• L’interface L’interface Deque Deque specifica tre metodi con i specifica tre metodi con i nomi “tipici” della nozione di nomi “tipici” della nozione di stack stack (essi (essi “affiancano” tre metodi equivalenti della “affiancano” tre metodi equivalenti della specifica generale)specifica generale)


DequeDeque: metodi per uso a : metodi per uso a stackstack

•• Nomi metodi Nomi metodi stackstack

void push(E e) Aggiunta elemento in cima

E peek () Accesso elemento in cima

E pop () Estrazione elemento in cima

•• Metodi “equivalenti”Metodi “equivalenti”

boolean addFirst(E e) Aggiunta elemento in testa

E peekFirst () Accesso elemento in testa

E removeFirst () Estrazione elemento in testa




RipensamentiRipensamenti

•• Il package java.Il package java.util util contiene (da sempre) contiene (da sempre) anche una classe anche una classe StackStack, derivata da , derivata da VectorVector, , con i tre metodi push, pop e con i tre metodi push, pop e peekpeek

•• Il suo uso è tuttavia “sconsigliato” e si Il suo uso è tuttavia “sconsigliato” e si suggerisce di usare un’implementazione di suggerisce di usare un’implementazione di Deque Deque nel modo sopra indicatonel modo sopra indicato

•• La classe La classe Stack Stack non fa parte del JCFnon fa parte del JCF


RoadmapRoadmap





L’interface L’interface MapMap





•• Il JCF non si basa solo sull’interface Il JCF non si basa solo sull’interface Collection Collection ma ma anche sull’interface “parallela” anche sull’interface “parallela” MapMap<K,V><K,V>

•• Mentre la Mentre la Collection Collection è una raccolta “semplice” di è una raccolta “semplice” di elementi, la elementi, la Map Map è una raccolta indicizzata di è una raccolta indicizzata di elementi: ogni elemento viene inserito elementi: ogni elemento viene inserito accompagnato da un altro elemento detto chiave accompagnato da un altro elemento detto chiave ((keykey) che lo identifica univocamente) che lo identifica univocamente

•• Questo permette di accedere agli elementi di una Questo permette di accedere agli elementi di una Map Map non solo tramite iterazione o accesso non solo tramite iterazione o accesso posizionale, ma anche tramite accesso diretto basato posizionale, ma anche tramite accesso diretto basato su chiave su chiave


Uso di chiaviUso di chiavi

•• L’uso di chiavi univoche è molto diffuso per L’uso di chiavi univoche è molto diffuso per l’identificazione di elementi:l’identificazione di elementi:–– codice fiscale per le personecodice fiscale per le persone

–– matricola per studenti universitarimatricola per studenti universitari

–– targhe per autoveicolitarghe per autoveicoli

–– codice a tre lettere per aeroporti (e alfanumerico codice a tre lettere per aeroporti (e alfanumerico per ciascun volo)per ciascun volo)

–– codici di prenotazionecodici di prenotazione





•• L’interfaccia L’interfaccia MapMap<K, V> è parametrica <K, V> è parametrica rispetto a due tipi di dati:rispetto a due tipi di dati:–– K rappresenta il tipo usato come chiaveK rappresenta il tipo usato come chiave

–– V rappresenta il tipo degli elementi contenuti nella V rappresenta il tipo degli elementi contenuti nella Map Map e indicizzati dalle chiavie indicizzati dalle chiavi


L’interface L’interface MapMap: relazioni : relazioni con con CollectionCollection

•• Anche se non è formalmente derivata Anche se non è formalmente derivata dall’interface dall’interface CollectionCollection, l’interface , l’interface Map Map ha ha alcune “parentele” con essa:alcune “parentele” con essa:–– alcuni metodi, (alcuni metodi, (clearclear, , isEmptyisEmpty, , sizesize) con lo stesso ) con lo stesso

nome e lo stesso ruolo che hanno in nome e lo stesso ruolo che hanno in Collection Collection

–– tre possibilità di accedere al contenuto di una tre possibilità di accedere al contenuto di una Map Map sotto forma di sotto forma di CollectionCollection




L’interface L’interface MapMap: aggiunta: aggiuntacon metodo con metodo putput

V V putput(K (K keykey, V , V valuevalue) )

Se la key passata come argomento non è presente nella map, viene aggiunta la nuova coppia key-valueSe invece la key è già presente, il nuovo value sostituisce quello precedentemente associato alla key


L’interface L’interface MapMap: metodo : metodo putput

Milano Malpensa……

Bergamo……

Roma Fiumicino……

“BGY”“MXP”“FCO”

putput("VRN", new ("VRN", new AirportAirport("Verona", . . .)) ("Verona", . . .))






Bergamo……



putput("VRN", new ("VRN", new AirportAirport("Verona", . . .)) ("Verona", . . .))

Verona……

“VRN”




Bergamo……



putput("BGY", new ("BGY", new AirportAirport("Milano Orio", . . .)) ("Milano Orio", . . .))

Verona……

“VRN”






Milano Orio……



putput("BGY", new ("BGY", new AirportAirport("Milano Orio", . . .)) ("Milano Orio", . . .))

Verona……

“VRN”


L’interface L’interface MapMap: accesso: accesso(con o senza eliminazione)(con o senza eliminazione)

V V removeremove ((Object keyObject key) )

V V getget((Object keyObject key) )

Se la key passata come argomento è presente nella map, viene restituito un riferimento al value corrispondente e la coppia key-value viene eliminata dalla map, altrimenti viene restituito null

Se la key passata come argomento è presente nella map, viene restituito un riferimento al value corrispondente, altrimenti viene restituito null. Il contenuto della Map rimane immutato.




L’interface L’interface MapMap: : verifiche di presenzaverifiche di presenza

boolean containsKey(Object key) Returns true if this map contains a mapping for the specified key.

boolean containsValue(Object value) Returns true if this map maps one or more keys to the specified value.


L’interface L’interface MapMap: : vista come vista come CollectionCollection

•• Sono specificati metodi per:Sono specificati metodi per:–– ottenere una ottenere una Collection Collection contenente tutti i contenente tutti i values values

presenti nella presenti nella MapMapCollectionCollection<V> <V> valuesvalues() () ReturnsReturns a a Collection viewCollection view of the of the values containedvalues contained in in this mapthis map. .

–– ottenere un Set contenente tutte le ottenere un Set contenente tutte le keyskeys presenti presenti nella nella MapMapSet<K> Set<K> keySetkeySet()()ReturnsReturns a Set a Set viewview of the of the keys containedkeys contained in in this mapthis map. .

Per definizione non ci possono essere chiavi duplicate




L’interface L’interface MapMap: : vista come vista come CollectionCollection

–– ottenere un Set contenente tutte le coppie ottenere un Set contenente tutte le coppie keykey--valuevalue presenti nella presenti nella MapMapSet<Set<MapMap.Entry<K,V>> .Entry<K,V>> entrySetentrySet()()ReturnsReturns a Set a Set viewview of the of the mappings containedmappings contained in in this this mapmap. .

Poiché non ci possono essere chiavi duplicate nemmeno le coppie possono essere duplicate

Gli elementi del Set implementano un’apposita interface dedicata alla rappresentazione di coppie key-value


Le interface Le interface SortedMap SortedMap e e NavigableMapNavigableMap

•• In modo analogo a quanto visto per Set, In modo analogo a quanto visto per Set, l’interface l’interface SortedMap SortedMap estende estende MapMapaggiungendo un requisito di ordinamento aggiungendo un requisito di ordinamento totale sulle chiavi (e relativi metodi di utilità)totale sulle chiavi (e relativi metodi di utilità)

•• L’interface L’interface NavigableMap NavigableMap estende estende SortedMap SortedMap con altri metodi di utilità (concettualmente con altri metodi di utilità (concettualmente analoghi a quelli di analoghi a quelli di NavigableSetNavigableSet))




RoadmapRoadmap






Dalle interface alle classiDalle interface alle classi


Le classi Le classi ArrayList ArrayList e e VectorVector

•• La classi La classi ArrayList ArrayList e e VectorVector forniscono entrambe forniscono entrambe un’implementazione dell’interface List un’implementazione dell’interface List

•• La classe La classe ArrayListArrayList fornisce in aggiunta 3 metodi di fornisce in aggiunta 3 metodi di natura accessorianatura accessoria

•• La classe La classe Vector Vector ha svariati metodi ulteriori che ha svariati metodi ulteriori che riflettono il suo progetto precedente (metodi riflettono il suo progetto precedente (metodi “affiancati” con nomi diversi ma funzionalità “affiancati” con nomi diversi ma funzionalità identiche, operazioni sulla struttura interna di uso identiche, operazioni sulla struttura interna di uso piuttosto raro, …)piuttosto raro, …)




Le classi Le classi ArrayList ArrayList e e VectorVector

•• La classe La classe ArrayList ArrayList è leggermente più efficiente di è leggermente più efficiente di VectorVector, in compenso , in compenso ArrayList ArrayList non è predisposta per non è predisposta per la programmazione multila programmazione multi--threadthread (argomento trattato (argomento trattato in corsi successivi) mentre in corsi successivi) mentre Vector Vector sìsì

•• Negli usi più comuni Negli usi più comuni ArrayList ArrayList e e Vector Vector possono possono essere considerate all’incirca equivalentiessere considerate all’incirca equivalenti

•• Alcuni libri di testo suggeriscono di usare Alcuni libri di testo suggeriscono di usare ArrayList ArrayList anziché anziché Vector Vector in quanto in quanto ArrayList ArrayList è stata progettata è stata progettata nel contesto di JCF, ma non ci sono forti motivi per nel contesto di JCF, ma non ci sono forti motivi per preferire l’una o l’altra a livello didattico inizialepreferire l’una o l’altra a livello didattico iniziale


La classe La classe ArrayDequeArrayDeque

•• La classe La classe ArrayDeque ArrayDeque offre offre un’implementazione dell’interface un’implementazione dell’interface Deque Deque senza alcun metodo aggiuntivosenza alcun metodo aggiuntivo

•• Non è predisposta per la programmazione Non è predisposta per la programmazione multimulti--threadthread




La classe La classe LinkedListLinkedList

•• La classe La classe LinkedList LinkedList ha una natura ha una natura “multiforme” in quanto implementa sia “multiforme” in quanto implementa sia l’interface List sia l’interface l’interface List sia l’interface Deque Deque (può (può quindi essere usata in alternativa ad quindi essere usata in alternativa ad entrambe)entrambe)

•• Non è predisposta per la programmazione Non è predisposta per la programmazione multimulti--threadthread


Le classi Le classi HashSet HashSet e e LinkedHashSetLinkedHashSet

•• La classe La classe HashSet HashSet fornisce una semplice fornisce una semplice implementazione dell’interface Set (il nome implementazione dell’interface Set (il nome della classe deriva dalla struttura dati interna della classe deriva dalla struttura dati interna utilizzata per l’implementazione e non visibile)utilizzata per l’implementazione e non visibile)

•• La classe La classe LinkedHashSet LinkedHashSet è figlia di è figlia di HashSet HashSet e e aggiunge la caratteristica di mantenere aggiunge la caratteristica di mantenere sempre lo stesso ordine quando si effettua sempre lo stesso ordine quando si effettua l’enumerazione degli elementi (non garantito l’enumerazione degli elementi (non garantito da da HashSetHashSet))




La classe La classe TreeSetTreeSet

•• La classe La classe TreeSet TreeSet fornisce fornisce un’implementazione dell’interface un’implementazione dell’interface NavigableSet NavigableSet (il nome della classe deriva dalla (il nome della classe deriva dalla struttura dati interna utilizzata per struttura dati interna utilizzata per l’implementazione e non visibile)l’implementazione e non visibile)

•• Le tre classi Le tre classi HashSetHashSet, , LinkedHashSet LinkedHashSet e e TreeSet TreeSet non sono predisposte per la non sono predisposte per la programmazione multiprogrammazione multi--threadthread


Le classi Le classi HashMap HashMap e e HashtableHashtable

•• Entrambe le classi Entrambe le classi HashMap HashMap e e Hashtable Hashtable forniscono forniscono un’implementazione dell’interface un’implementazione dell’interface MapMap

•• La classe La classe Hashtable Hashtable ha alcuni metodi aggiuntivi che ha alcuni metodi aggiuntivi che riflettono il suo progetto preesistente, inoltre non riflettono il suo progetto preesistente, inoltre non ammette elementi o chiavi ammette elementi o chiavi null null (mentre (mentre HashMap HashMap sì) sì) ed è predisposta per la programmazione multied è predisposta per la programmazione multi--thread thread (mentre (mentre HashMapHashMap no)no)

•• Il rapporto tra Il rapporto tra HashMap HashMap e e Hashtable Hashtable è simile a quello è simile a quello tra tra ArrayList ArrayList e e VectorVector




La classe La classe LinkedHashMapLinkedHashMap

•• La classe La classe LinkedHashMapLinkedHashMap è figlia di è figlia di HashMapHashMape aggiunge la caratteristica di mantenere e aggiunge la caratteristica di mantenere sempre lo stesso ordine quando si effettua sempre lo stesso ordine quando si effettua l’enumerazione degli elementi (non garantito l’enumerazione degli elementi (non garantito da da HashMapHashMap))

•• Il rapporto tra Il rapporto tra LinkedHashMapLinkedHashMap ed ed HashMap HashMap è è del tutto analogo a quello tra del tutto analogo a quello tra LinkedHashSetLinkedHashSeted ed HashSetHashSet


La classe La classe TreeMapTreeMap

•• La classe La classe TreeMap TreeMap fornisce fornisce un’implementazione dell’interface un’implementazione dell’interface NavigableMap NavigableMap (il nome della classe deriva (il nome della classe deriva dalla struttura dati interna utilizzata per dalla struttura dati interna utilizzata per l’implementazione e non visibile)l’implementazione e non visibile)

•• Le tre classi Le tre classi HashMapHashMap, , LinkedHashMapLinkedHashMap e e TreeMap TreeMap non sono predisposte per la non sono predisposte per la programmazione multiprogrammazione multi--threadthread




Classi “solo Classi “solo staticstatic”: ”: ArraysArrays•• La classe La classe Arrays Arrays contiene 105 metodi (molti in contiene 105 metodi (molti in

overloadingoverloading) per svolgere comuni operazioni utili su ) per svolgere comuni operazioni utili su array array (di tipi semplici o di (di tipi semplici o di ObjectObject) tra le quali:) tra le quali:–– asListasList: restituzione di una List con il contenuto : restituzione di una List con il contenuto dell’arraydell’array

–– binarySearchbinarySearch (18 versioni): ricerca efficiente di un elemento (18 versioni): ricerca efficiente di un elemento (richiede che (richiede che l’arrayl’array sia ordinato)sia ordinato)

–– copyOfcopyOf (10 versioni): crea una copia (10 versioni): crea una copia dell’arraydell’array in un nuovo in un nuovo arrayarray

–– copyOfRangecopyOfRange (10 versioni): crea una copia di un (10 versioni): crea una copia di un rangerange dell’arraydell’arrayin un nuovo in un nuovo arrayarray

–– equalsequals (9 versioni): confronta il contenuto di due (9 versioni): confronta il contenuto di due arrayarray

–– fillfill (18 versioni): riempimento con un certo valore(18 versioni): riempimento con un certo valore

–– sort sort (18 versioni): ordinamento(18 versioni): ordinamento

–– toString toString (9 versioni)(9 versioni)


Classi “solo Classi “solo staticstatic”: ”: CollectionsCollections

•• La classe La classe CollectionsCollections contiene 52 metodi per svolgere contiene 52 metodi per svolgere svariate operazioni (anche non molto comuni) su svariate operazioni (anche non molto comuni) su CollectionCollection tra le quali:tra le quali:–– binarySearch binarySearch (2 versioni)(2 versioni)

–– copycopy

–– fill fill

–– max max e e min min (2 versioni ciascuno)(2 versioni ciascuno)

–– replaceAllreplaceAll

–– reversereverse

–– rotaterotate

–– shuffleshuffle (2 versioni) (2 versioni)

–– sortsort (2 versioni)(2 versioni)

–– swapswap




RoadmapRoadmap







Guardando dentro: classi e interface genericheGuardando dentro: classi e interface generiche


Classi e interface genericheClassi e interface generiche

•• Le interface e le classi appartenenti al JCF sono Le interface e le classi appartenenti al JCF sono definite “genericamente” rispetto al tipo di oggetto definite “genericamente” rispetto al tipo di oggetto contenuto in ciascuna specifica istanza di contenuto in ciascuna specifica istanza di Collection Collection

•• Tale tipo generico è specificato tra <> e viene detto Tale tipo generico è specificato tra <> e viene detto parametro di tipo o variabile di tipoparametro di tipo o variabile di tipo

•• La definizione di classi generiche (ossia con uno o La definizione di classi generiche (ossia con uno o più parametri di tipo) è una delle principali più parametri di tipo) è una delle principali innovazioni introdotte nella versione 1.5innovazioni introdotte nella versione 1.5

•• Essa è particolarmente adatta alle strutture dati ma Essa è particolarmente adatta alle strutture dati ma può essere utilizzata ovunque lo si ritenga utilepuò essere utilizzata ovunque lo si ritenga utile




Confronto di stringhe Confronto di stringhe descrittivedescrittive

•• Si supponga di voler confrontare le stringhe Si supponga di voler confrontare le stringhe descrittive di oggetti descrittive di oggetti dello stesso tipodello stesso tipo in in questo modo: questo modo: –– se hanno una parte iniziale uguale (non vuota) se hanno una parte iniziale uguale (non vuota)

questa viene restituita in uscita questa viene restituita in uscita

–– in caso contrario viene restituito in caso contrario viene restituito null null


Prima della 1.5 …Prima della 1.5 …

•• Poiché il metodo Poiché il metodo toString toString è definito nella classe è definito nella classe Object Object e il tipo e il tipo ObjectObject è compatibile con è compatibile con qualunque altro tipo, si potrebbe definire un qualunque altro tipo, si potrebbe definire un metodo di confronto che riceve in ingresso due metodo di confronto che riceve in ingresso due ObjectObject

String confrontaDescrizioniString confrontaDescrizioni((Object Object obj1,obj1,ObjectObject obj2)obj2)

•• . . . così però potrei finire per confrontare le . . . così però potrei finire per confrontare le pere con le mele (oggetti di tipo diverso) pere con le mele (oggetti di tipo diverso)




La classe La classe Object Object come jollycome jolly

•• Prima della versione 1.5 la classe Prima della versione 1.5 la classe Object Object veniva veniva spesso usata come “jolly” per indicare “qualunque spesso usata come “jolly” per indicare “qualunque classe”classe”

•• Ad esempio tutte le strutture dati del JCF erano Ad esempio tutte le strutture dati del JCF erano definiti come contenitori di definiti come contenitori di ObjectObject, cosa che , cosa che permetteva di “mescolare” oggetti diversi nella permetteva di “mescolare” oggetti diversi nella stessa struttura . . .stessa struttura . . .

•• . . . ma obbligava a fare il cast esplicito per accedere . . . ma obbligava a fare il cast esplicito per accedere agli elementi contenuti secondo il loro “vero” tipo agli elementi contenuti secondo il loro “vero” tipo


Due requisiti in conflitto ?Due requisiti in conflitto ?

•• Nella maggior parte dei casi non si desiderano Nella maggior parte dei casi non si desiderano strutture con contenuto eterogeneo, anzi la presenza strutture con contenuto eterogeneo, anzi la presenza di elementi eterogenei è indice di un errore e di elementi eterogenei è indice di un errore e potrebbe causare eccezioni al momento del castpotrebbe causare eccezioni al momento del cast

•• Tuttavia si desidera la definizione di strutture dati e Tuttavia si desidera la definizione di strutture dati e metodi generici, cioè in grado di operare su metodi generici, cioè in grado di operare su qualunque classe (altrimenti dovremmo definire una qualunque classe (altrimenti dovremmo definire una nuova classe contenitore per ogni nuova classe di nuova classe contenitore per ogni nuova classe di oggetto contenuto)oggetto contenuto)





•• Genericità: deve essere possibile definire Genericità: deve essere possibile definire classi generiche con capacità “universali” o classi generiche con capacità “universali” o comunque riferite ad un ampio insieme di comunque riferite ad un ampio insieme di classiclassi

•• Type safetyType safety: nell’ambito di classi generiche si : nell’ambito di classi generiche si vogliono evitare mescolanze indesiderate di vogliono evitare mescolanze indesiderate di tipi. Eventuali errori sui tipi devono essere tipi. Eventuali errori sui tipi devono essere rilevati al momento della compilazione rilevati al momento della compilazione anziché generare eccezioni in esecuzione.anziché generare eccezioni in esecuzione.



•• Nelle versioni precedenti alla 1.5 i due Nelle versioni precedenti alla 1.5 i due requisiti erano effettivamente in conflitto: per requisiti erano effettivamente in conflitto: per ottenere la genericità si usava ottenere la genericità si usava Object Object come come jolly, rinunciando così alla jolly, rinunciando così alla type safetytype safety

•• A partire dalla versione 1.5 si possono A partire dalla versione 1.5 si possono soddisfare entrambi i requisiti usando il soddisfare entrambi i requisiti usando il meccanismo delle classi generichemeccanismo delle classi generiche




Una classe genericaUna classe generica

public class public class ComparatoreDescrizioni ComparatoreDescrizioni <T><T>{{private T obj1;private T obj1;private T obj2;private T obj2;

public public ComparatoreDescrizioniComparatoreDescrizioni(T _obj1, T _obj2)(T _obj1, T _obj2){{obj1 = _obj1;obj1 = _obj1;obj2 = _obj2;obj2 = _obj2;}}

public public void inizioComunevoid inizioComune()(){// DETTAGLI RIPORTATI IN SEGUITO MA NON RILEVANTI{// DETTAGLI RIPORTATI IN SEGUITO MA NON RILEVANTI}}

}}

La definizione della classe è parametrica rispetto ad un tipo T

La classe ha due attributi del tipo T

Il costruttore riceve due argomenti formali di tipo T


Una classe genericaUna classe genericapublic public StringString inizioComuneinizioComune()(){ { StringString descr1 = obj1.descr1 = obj1.toStringtoString();();StringString descr2 = obj2.descr2 = obj2.toStringtoString();();int int i = 0;i = 0;StringBuffer parteUguale StringBuffer parteUguale = new = new StringBufferStringBuffer();();whilewhile (i < descr1.(i < descr1.lengthlength() && i < descr2.() && i < descr2.lengthlength() && () &&

descr1.descr1.charAtcharAt(i) == descr2.(i) == descr2.charAtcharAt(i))(i)){ { parteUgualeparteUguale..appendappend(descr1.(descr1.charAtcharAt(i));(i));i++;i++;}}

StringString inizio = inizio = parteUgualeparteUguale..toStringtoString();();ifif (inizio.(inizio.lengthlength() == 0)() == 0)return return nullnull;;

elseelsereturn inizio;return inizio;

}}




Un Un main main che la utilizzache la utilizza

public class public class MainComparatoreString MainComparatoreString {{

public public static void mainstatic void main ((StringString[] [] argsargs)){{StringString s1 = s1 = MyUtilMyUtil..leggiStringleggiString("Inserire il primo termine");("Inserire il primo termine");StringString s2 = s2 = MyUtilMyUtil..leggiStringleggiString("Inserire il secondo termine");("Inserire il secondo termine");

ComparatoreDescrizioniComparatoreDescrizioni<<StringString> prova = > prova = new new ComparatoreDescrizioniComparatoreDescrizioni<<StringString>(s1,s2);>(s1,s2);

StringString risultato= prova.risultato= prova.inizioComuneinizioComune();();System.out.System.out.printlnprintln(risultato);(risultato);

}}

}}

Il tipo generico T viene sostituito da String in questo utilizzo

Se s1 ed s2 non fossero di tipo String si avrebbe errore in compilazione


Un altro Un altro main main che la utilizzache la utilizza

public class public class MainComparatoreDatiPersonaliMainComparatoreDatiPersonali{{. . .. . .public public static void mainstatic void main ((StringString [] [] argsargs)){ { DatiPersonaliDatiPersonali dati1 = dati1 = creaDaticreaDati();();DatiPersonaliDatiPersonali dati2 = dati2 = creaDaticreaDati();();

ComparatoreDescrizioniComparatoreDescrizioni <<DatiPersonaliDatiPersonali> prova = > prova = new new ComparatoreDescrizioniComparatoreDescrizioni<<DatiPersonaliDatiPersonali> (dati1,dati2);> (dati1,dati2);

StringString risultato = prova.risultato = prova.inizioComuneinizioComune();();. . .. . .

}}. . .. . . Il tipo generico T viene sostituito

da DatiPersonali in questo utilizzo




Classi generiche: Classi generiche: regole e convenzioniregole e convenzioni

•• La definizione di una classe generica è La definizione di una classe generica è parametrica rispetto ad uno o più parametri di parametrica rispetto ad uno o più parametri di tipo, indicati tra <> dopo il nome della classetipo, indicati tra <> dopo il nome della classe

•• Per convenzione i parametri di tipo vengono Per convenzione i parametri di tipo vengono indicati con singole lettere maiuscole: indicati con singole lettere maiuscole: T, S, U per qualunque usoT, S, U per qualunque usoE per indicare elementi di strutture collettiveE per indicare elementi di strutture collettiveK,V per indicare chiave e valore di K,V per indicare chiave e valore di MapMap



•• I nomi dei parametri di tipo possono essere I nomi dei parametri di tipo possono essere usati (quasi) come qualunque altro nome di usati (quasi) come qualunque altro nome di tipo nella definizione di una classe ma ci sono tipo nella definizione di una classe ma ci sono delle limitazioni:delle limitazioni:–– non è possibile creare istanze di tipi parametricinon è possibile creare istanze di tipi parametrici

(un’istruzione (un’istruzione new Tnew T non è possibile)non è possibile)

–– non è possibile definire attributi non è possibile definire attributi static static di un tipo di un tipo parametrico o usare un tipo parametrico parametrico o usare un tipo parametrico all’interno di metodi all’interno di metodi staticstatic





•• Al momento dell’uso ciascun parametro di Al momento dell’uso ciascun parametro di tipo generico deve essere sostituito con un tipo generico deve essere sostituito con un tipo strutturatotipo strutturato

•• I tipi elementari non sono utilizzabili a questo I tipi elementari non sono utilizzabili a questo scopo scopo


Metodi genericiMetodi generici

•• In qualunque classe (generica o no) è In qualunque classe (generica o no) è possibile definire metodi generici, la cui possibile definire metodi generici, la cui definizione dipende da uno o più variabili di definizione dipende da uno o più variabili di tipo (riferite al solo metodo, non alla classe di tipo (riferite al solo metodo, non alla classe di cui fa parte)cui fa parte)

•• Le variabili di tipo sono specificate tra <> Le variabili di tipo sono specificate tra <> prima del tipo ritornatoprima del tipo ritornato

•• Esse devono comparire anche nella Esse devono comparire anche nella definizione del tipo di argomenti formalidefinizione del tipo di argomenti formali





•• Se un metodo generico è definito in una Se un metodo generico è definito in una classe generica non bisogna far confusione classe generica non bisogna far confusione tra variabili di tipo del solo metodo e variabili tra variabili di tipo del solo metodo e variabili di tipo dell’intera classedi tipo dell’intera classe

•• Spesso i metodi generici sono Spesso i metodi generici sono static static e definiti e definiti in classi non generichein classi non generiche

•• Esempi di metodi generici Esempi di metodi generici static static sono presenti sono presenti nelle classi (non generiche) nelle classi (non generiche) Arrays Arrays e e CollectionsCollections


Un esempio di metodo Un esempio di metodo generico (classe generico (classe ArraysArrays))

staticstatic <T> T[] <T> T[] copyOfcopyOf(T[] (T[] originaloriginal, , int newLengthint newLength))CopiesCopies the the specified arrayspecified array, , truncatingtruncating or or padding padding with nullswith nulls ((if necessaryif necessary) so the copy ) so the copy hashas the the specified lengthspecified length..

Il metodo copyOf è generico rispetto al tipo T

Il metodo restituisce un array di T

Il primo argomento formale del metodo è a sua volta un array di T





•• L’invocazione di un metodo generico non L’invocazione di un metodo generico non richiede di specificare esplicitamente la richiede di specificare esplicitamente la sostituzione tra parametri di tipo e tipi sostituzione tra parametri di tipo e tipi effettivamente utilizzati: il compilatore effettivamente utilizzati: il compilatore riconosce la sostituzione dal passaggio dei riconosce la sostituzione dal passaggio dei parametri (parametri (purchèpurchè compatibile con la compatibile con la definizione)definizione)

•• Anche per i metodi generici non è possibile Anche per i metodi generici non è possibile utilizzare tipi elementari come sostituti di utilizzare tipi elementari come sostituti di parametri di tipoparametri di tipo


Vincoli sui parametri di tipoVincoli sui parametri di tipo

•• In alcuni casi non si vuole che una classe In alcuni casi non si vuole che una classe generica sia “universale” (cioè che ciascun generica sia “universale” (cioè che ciascun parametro di tipo sia sostituibile da parametro di tipo sia sostituibile da qualunque tipo strutturato): il tipo generico qualunque tipo strutturato): il tipo generico può essere vincolato a rispettare delle può essere vincolato a rispettare delle caratteristichecaratteristiche

•• I vincoli specificabili sono legati alle relazioni I vincoli specificabili sono legati alle relazioni di ereditarietàdi ereditarietà




Vincolo Vincolo extendsextends

•• Si può imporre al tipo generico di essere Si può imporre al tipo generico di essere derivato da una certa classe o interfacederivato da una certa classe o interface

•• In questo modo qualunque tipo sostituito In questo modo qualunque tipo sostituito avrà delle caratteristiche comuni garantite avrà delle caratteristiche comuni garantite sulle quali la definizione della classe generica sulle quali la definizione della classe generica può fare affidamentopuò fare affidamento

•• Il vincolo viene espresso tra le <> usando la Il vincolo viene espresso tra le <> usando la parola chiave parola chiave extendsextends p.e.p.e.<T <T extends Comparableextends Comparable>>


Vincolo superVincolo super

•• In modo analogo è possibile imporre il vincolo In modo analogo è possibile imporre il vincolo di essere superclasse di un tipo specificatodi essere superclasse di un tipo specificato

•• Il vincolo è espresso usando la parola chiave Il vincolo è espresso usando la parola chiave supersuper tra <> tra <>




Il carattere “jolly” (Il carattere “jolly” (wildcardwildcard))

•• Il carattere ? all’interno di <> rappresenta Il carattere ? all’interno di <> rappresenta l’indicazione jolly di “qualunque tipo”l’indicazione jolly di “qualunque tipo”

•• Esso è utilizzabile in combinazione con i Esso è utilizzabile in combinazione con i vincoli vincoli extends extends o super o da soloo super o da solo

•• Se usato da solo esso indica una sostituzione Se usato da solo esso indica una sostituzione totalmente libera (che però potrebbe essere totalmente libera (che però potrebbe essere vincolata indirettamente da altre parti della vincolata indirettamente da altre parti della definizione della classe o del metodo)definizione della classe o del metodo)


Esempi di vincoli e jollyEsempi di vincoli e jolly

static <T> void copy(List<? super T> dest, List<? extends T> src)Copies all of the elements from one list into another.

Il metodo copy (classe Collections) è generico rispetto al tipo T

Esso riceve come argomenti una List “sorgente” src da cui copiare gli elementi e una List “destinazione” dest dove metterli.Poiché List è un’interface generica va specificato il tipo contenuto di entrambe

La List sorgente deve contenere elementi di una sottoclasse di T

La List destinazione deve contenere elementi di una superclasse di T





boolean addAllboolean addAll((CollectionCollection<? <? extendsextends E> c) E> c) Adds allAdds all of the of the elementselements in the in the specified collection to specified collection to this collectionthis collection (optional (optional operationoperation).).

Il metodo addAll è definito nell’interface Collection che è parametrica rispetto al tipo E dei suoi elementi (qui richiamato)

Esso riceve come argomento una Collection c da cui “pescare” gli elementi da aggiungere

La Collection c deve contenere elementi di una sottoclasse di E



boolean containsAllboolean containsAll((CollectionCollection<?> c) <?> c) Returns true if this collection contains allReturns true if this collection contains all of the of the elementselements in the in the specified collectionspecified collection..

Il metodo containsAll è definito nell’interface Collection che è parametrica rispetto al tipo E dei suoi elementi (qui non richiamato)

Esso riceve come argomento una Collection c da cui “pescare” gli elementi di cui verificare la presenza

La Collection c può contenere elementi di qualunque classe




RoadmapRoadmap•• 13. Strutture dati + 13. Strutture dati + GenericsGenerics

Tipi di dati parametriciTipi di dati parametrici






Guardando dentro: classi e interface genericheGuardando dentro: classi e interface generiche

Esempi di programmazione di strutture dati “classiche”: Esempi di programmazione di strutture dati “classiche”: liste concatenate e alberi binariliste concatenate e alberi binari


Liste concatenateListe concatenate

•• Si parla di lista concatenata per indicare una Si parla di lista concatenata per indicare una struttura nella quale gli elementi (detti anche struttura nella quale gli elementi (detti anche nodi) sono collegati tramite riferimenti nodi) sono collegati tramite riferimenti dall’uno all’altrodall’uno all’altro

•• Il caso più semplice di lista concatenata Il caso più semplice di lista concatenata prevede un collegamento unidirezionale prevede un collegamento unidirezionale sequenziale a partire da un elemento inizialesequenziale a partire da un elemento iniziale




Lista concatenata sempliceLista concatenata sempliceIl primo elemento viene detto “testa” della lista ed è riferito da una variabile che non è un elemento della listaQuesto riferimento è necessario per accedere alla lista

Ogni elemento, tranne l’ultimo, riferisce l’elemento successivo


Lista concatenata doppiaLista concatenata doppia

Ogni elemento contiene due riferimenti (uno all’elemento successivo, uno al precedente)Il primo elemento contiene solo il riferimento al successivo, l’ultimo elemento solo al precedente




Lista circolare sempliceLista circolare semplice

L’ultimo elemento è collegato al primo in modo da chiudere circolarmente il collegamento. Le nozioni di primo e ultimo elemento non sono più essenziali. Rimane la necessità di un riferimento esterno dal quale partire


Lista circolare doppiaLista circolare doppia

I riferimenti tra gli elementi realizzano un doppio anello




Doppio riferimentoDoppio riferimentoIn tutte le varianti, oltre che il riferimento alla testa si può mantenere il riferimento anche all’ultimo elemento (coda) della lista


Strutture dati Strutture dati ricorsivericorsive

•• Gli elementi di strutture dati concatenate sono Gli elementi di strutture dati concatenate sono tipicamente definiti in modo tipicamente definiti in modo ricorsivoricorsivo: infatti ogni : infatti ogni elemento deve contenere un riferimento ad un elemento elemento deve contenere un riferimento ad un elemento dello stesso tipodello stesso tipo

class class NodoLista NodoLista {{

private private NodoListaNodoLista prossimo;prossimo;. . .. . .

}}

class class NodoListaDoppia NodoListaDoppia {{

private private NodoListaDoppiaNodoListaDoppia prossimo;prossimo;private private NodoListaDoppiaNodoListaDoppia precedente;precedente;. . .. . .

}}




Generics Generics e classi internee classi interne

•• Per rappresentare una struttura dati sono tipicamente Per rappresentare una struttura dati sono tipicamente necessarie almeno due classi: una che rappresenta la necessarie almeno due classi: una che rappresenta la struttura (p.e. la lista) “nel suo complesso” e una per struttura (p.e. la lista) “nel suo complesso” e una per rappresentare i singoli elementi della listarappresentare i singoli elementi della lista

•• Per definire strutture parametriche rispetto ai dati Per definire strutture parametriche rispetto ai dati contenuti negli elementi entrambe le classi devono essere contenuti negli elementi entrambe le classi devono essere generiche (p.e. Lista<E>, generiche (p.e. Lista<E>, ElementoListaElementoLista<E>)<E>)

•• Si vuole però specificare che il tipo di una lista e dei suoi Si vuole però specificare che il tipo di una lista e dei suoi elementi deve essere lo stesso. Questo non è possibile se elementi deve essere lo stesso. Questo non è possibile se le due classi sono definite separatamente: bisogna invece le due classi sono definite separatamente: bisogna invece definire una classe internamente all’altra (definire una classe internamente all’altra (inner inner class)class)


Classi interneClassi interne

•• E’ possibile definire una classe all’interno di un’altraE’ possibile definire una classe all’interno di un’altra

•• La classe interna non può essere public e La classe interna non può essere public e tipicamente sarà private (il suo uso è limitato alla tipicamente sarà private (il suo uso è limitato alla classe che la contiene)classe che la contiene)

•• L’uso di classi interne (che non verrà approfondito) è L’uso di classi interne (che non verrà approfondito) è utile in situazioni molto specificheutile in situazioni molto specifiche

•• Una di queste è la condivisione di una variabile di Una di queste è la condivisione di una variabile di tipo: la classe interna sarà definita in termini della tipo: la classe interna sarà definita in termini della variabile di tipo della classe esternavariabile di tipo della classe esterna




Classi Lista e Classi Lista e NodoListaNodoLista

public class Lista<E>public class Lista<E>{{private private NodoLista NodoLista testa;testa;private private int numeroElementiint numeroElementi;;

. . .// METODI VARI DI Lista da approfondire dopo. . .// METODI VARI DI Lista da approfondire dopo

private class private class NodoListaNodoLista{{private E contenuto;private E contenuto;private private NodoLista NodoLista prossimo;prossimo;. . .// METODI DI . . .// METODI DI NodoListaNodoLista da approfondire dopoda approfondire dopo

}}

}}

La classe Lista è parametrica rispetto ad un tipo E

In caso di lista semplice è sufficiente il solo attributo testa che riferisce il primo elemento della lista

La classe NodoLista è interna a Lista. Essa non è esplicitamente generica ma la sua definizione può contenere la variabile di tipo E della classe esterna.

La classe e i suoi attributi sono private, ma visibili all’interno della classe Lista


La classe La classe NodoListaNodoLista

private class private class NodoListaNodoLista{{private E contenuto;private E contenuto;private private NodoListaNodoLista prossimo;prossimo;

public public NodoLista NodoLista (E _contenuto)(E _contenuto){{contenuto = _contenuto;contenuto = _contenuto;prossimo = prossimo = nullnull;;} }

public public NodoListaNodoLista (E _contenuto, (E _contenuto, NodoListaNodoLista _prossimo)_prossimo){{contenuto = _contenuto;contenuto = _contenuto;prossimo = _prossimo;prossimo = _prossimo;} }

}}

La classe NodoLista ha due semplici costruttori: - uno per quando non c’è un elemento successivo- uno per quando c’è




La classe La classe NodoListaNodoLista

private class private class NodoListaNodoLista{. . .{. . .public public String toStringString toString()(){{return contenuto.return contenuto.toStringtoString();();} }

}}La stringa descrittiva di un nodo coincide con la stringa descrittiva del suo contenuto


La classe Lista: costruttoriLa classe Lista: costruttori

public class Lista<E>public class Lista<E>{{

private private NodoListaNodoLista testa;testa;private private int numeroElementiint numeroElementi;;

public Lista()public Lista(){{testa = testa = nullnull;;numeroElementinumeroElementi=0;=0;

}}

public Lista(E public Lista(E primoElementoprimoElemento)){{testa = new testa = new NodoListaNodoLista((primoElementoprimoElemento););numeroElementinumeroElementi=1;=1;

}}

. . .. . .}}

La classe Lista ha due semplici costruttori: - uno creare una lista vuota, priva di elementi- uno per quando il primo elemento è specificato




La classe Lista: La classe Lista: metodi di utilitàmetodi di utilità

public class Lista<E>public class Lista<E>{ . . .{ . . .public public boolean isEmptyboolean isEmpty()(){{return testa == return testa == nullnull;;}}

public public String toStringString toString()(){{ifif ((isEmptyisEmpty()) ()) {{return MESS_VUOTA;return MESS_VUOTA;}}elseelse{{StringBufferStringBuffer risultato = new risultato = new StringBufferStringBuffer();();NodoListaNodoLista corrente = testa;corrente = testa;whilewhile (corrente != (corrente != nullnull) ) {{risultato.risultato.appendappend(corrente.(corrente.toStringtoString() + "() + "\\n");n");corrente = corrente.prossimo;corrente = corrente.prossimo;}}return risultato.return risultato.toStringtoString();();}}

}}

La lista è vuota se il primo riferimento è null

All’interno del metodo toString si ha il tipico modo di scorrere tutti gli elementi di una lista semplice

Viene fissato un riferimento all’inizio della listaLa scansione termina quando il riferimento diventa null

L’avanzata avviene passando al prossimo elemento


Scansione di una listaScansione di una listatesta

next

contenuto

next

contenuto

next

contenuto

next

contenuto

next=null

contenuto

corrente

null




Inserimento in testaInserimento in testa

public public void inserimentoInTestavoid inserimentoInTesta(E contenuto)(E contenuto){{numeroElementinumeroElementi++;++;ifif ((isEmptyisEmpty())())testa = new testa = new NodoListaNodoLista(contenuto);(contenuto);

else else testa = new testa = new NodoListaNodoLista(contenuto, testa);(contenuto, testa);

}}

Il numero di elementi cresce e il nuovo NodoLista sarà riferito da testa in ogni caso

Se la lista è vuota, il nuovo nodo è anche l’unico e avrà null come successore

Altrimenti avrà come successore quello che prima era in testa


Inserimento in codaInserimento in coda

public public void inserimentoInCodavoid inserimentoInCoda(E contenuto)(E contenuto){{numeroElementinumeroElementi++;++;ifif ((isEmptyisEmpty())())testa = new testa = new NodoListaNodoLista(contenuto);(contenuto);else else {{NodoLista NodoLista corrente = testa;corrente = testa;whilewhile(corrente.prossimo != (corrente.prossimo != nullnull))

corrente=corrente.prossimo;corrente=corrente.prossimo;

corrente.prossimo=new corrente.prossimo=new NodoListaNodoLista(contenuto);(contenuto);}}

}}

Si porta il riferimento corrente all’ultimo elemento

. . . e si aggiunge lì il nuovo nodo

Se la lista è vuota, testa e coda coincidono




Inserimento in una posizioneInserimento in una posizionepublic public void void inserimento(inserimento(intint posizione, E contenuto) posizione, E contenuto) throws throws

ArrayIndexOutOfBoundsExceptionArrayIndexOutOfBoundsException{{ifif (posizione < 0 || posizione > (posizione < 0 || posizione > numeroElementinumeroElementi))throw throw new new ArrayIndexOutOfBoundsExceptionArrayIndexOutOfBoundsException();();

ifif (posizione == 0)(posizione == 0)inserimentoInTestainserimentoInTesta(contenuto);(contenuto);

elseelseifif (posizione == (posizione == numeroElementinumeroElementi))inserimentoInCodainserimentoInCoda(contenuto); (contenuto);

else else {{NodoListaNodoLista corrente = testa;corrente = testa;for for ((int int i=1; i < posizione; i++)i=1; i < posizione; i++)


corrente.prossimo=new corrente.prossimo=new NodoListaNodoLista(contenuto,corrente.prossimo);(contenuto,corrente.prossimo);}}

numeroElementinumeroElementi++;++;}}

Controllo che la posizione sia valida

Sappiamo già gestire le posizioni estreme

Si porta il riferimento corrente all’elemento in posizione precedente a quello nuovo

… e si aggiunge lì il nuovo nodo


Rimozione in testaRimozione in testa

public E public E rimozioneInTestarimozioneInTesta() () throws throws NoSuchElementExceptionNoSuchElementException

{{ifif ((isEmptyisEmpty())())throw throw new new NoSuchElementExceptionNoSuchElementException();();

E risultato = testa.contenuto;E risultato = testa.contenuto;testa=testa.prossimo;testa=testa.prossimo;

numeroElementinumeroElementi----;;return risultato;return risultato;}}

Metto via il risultato

Controllo che ci sia almeno un elemento da togliere

Spostando avanti il riferimento ottengo un’eliminazione implicita




Rimozione in codaRimozione in codapublic E public E rimozioneInCodarimozioneInCoda()()throws NoSuchElementExceptionthrows NoSuchElementException{{

ifif ((isEmptyisEmpty())())throw throw new new NoSuchElementExceptionNoSuchElementException();();

if if ((numeroElementi numeroElementi == 1)== 1)return return rimozioneInTestarimozioneInTesta();();elseelse{{NodoListaNodoLista corrente = testa;corrente = testa;forfor ((intint i=1; i < i=1; i < numeroElementinumeroElementi--1; i++)1; i++)

corrente=corrente.prossimo;corrente=corrente.prossimo;E risultato = corrente.prossimo.contenuto;E risultato = corrente.prossimo.contenuto;corrente.prossimo = corrente.prossimo = nullnull;;numeroElementinumeroElementi----;;return risultato;return risultato;}}

}}

Se l’elemento è uno solo so già come fare

Controllo che ci sia almeno un elemento da togliere

Porto il riferimento corrente sul penultimo elemento

Metto via il risultato

Mettendo a null il riferimento ottengo un’eliminazione implicita


Rimozione in una posizioneRimozione in una posizionepublic E rimozione (public E rimozione (intint posizione) posizione) throws throws

ArrayIndexOutOfBoundsException ArrayIndexOutOfBoundsException {{ifif (posizione < 0 || posizione > (posizione < 0 || posizione > numeroElementinumeroElementi--1)1)throw throw new new ArrayIndexOutOfBoundsExceptionArrayIndexOutOfBoundsException();();

ifif (posizione == 0)(posizione == 0)return return rimozioneInTestarimozioneInTesta();();

elseelseifif (posizione == (posizione == numeroElementinumeroElementi--1)1)return return rimozioneInCodarimozioneInCoda(); ();

else else {{NodoListaNodoLista corrente = testa;corrente = testa;for for ((int int i=1; i < posizione; i++)i=1; i < posizione; i++)


E risultato = corrente.prossimo.contenuto;E risultato = corrente.prossimo.contenuto;corrente.prossimo=corrente.prossimo.prossimo; corrente.prossimo=corrente.prossimo.prossimo; numeroElementinumeroElementi----;;return risultato;return risultato;

}}}}

Controllo che la posizione sia valida

Sappiamo già gestire le posizioni estreme

Si porta il riferimento corrente all’elemento in posizione precedente a quello da eliminare

L’eliminazione si ottiene con uno scavalcamento




Alberi binariAlberi binari

•• Un albero binario è un albero con la Un albero binario è un albero con la caratteristica che ogni nodo può avere al più caratteristica che ogni nodo può avere al più due figlidue figli

•• Gli alberi binari (in forme più sofisticate di Gli alberi binari (in forme più sofisticate di quella elementare che vedremo noi) sono quella elementare che vedremo noi) sono molto utilizzati per la gestione di dati dotati di molto utilizzati per la gestione di dati dotati di ordinamento, in quanto consentono ordinamento, in quanto consentono l’effettuazione efficiente di operazioni di l’effettuazione efficiente di operazioni di inserimento e ricercainserimento e ricerca


Albero binarioAlbero binario




Albero binarioAlbero binario

E

C

A

O

R

PB

G

U

CA

A

OR

R

P

P

P

B

B

B

G

G

U

U

U


Le classi Le classi BTreeBTree e e TreeNodeTreeNode

public class public class BTreeBTree <E <E extendsextends ComparableComparable<? super E>><? super E>>{{

private private TreeNode rootTreeNode root;;

. . .. . .private class private class TreeNodeTreeNode{{private E private E valuevalue;;private private TreeNode leftTreeNode left;;private private TreeNode rightTreeNode right;;. . .. . .

}}

La classe BTree è generica rispetto ad un tipo E che deve estendere l’interfaceComparable (deve essere possibile stabilire tra due elementi quale viene prima)

Poiché l’interface Comparable è a sua volta generica, si specifica il relativo tipo. In pratica si indica che E può estendere Comparable direttamente o anche ereditandola da una superclasse

Analogamente al caso precedente, la classe BTree ha un solo attributo per riferire la radice dell’albero e contiene come classe interna quella relativa ai nodi




La classe La classe BTreeBTreepublic class public class BTreeBTree <E <E extendsextends ComparableComparable<? super E>><? super E>>{{private private TreeNode rootTreeNode root;;

public public BTreeBTree() () { { rootroot = = nullnull; ; }}

public public void insertNodevoid insertNode(E(E newElementnewElement)){{ifif ( ( rootroot == == nullnull ))rootroot = new = new TreeNodeTreeNode((newElementnewElement););elseelserootroot..insertinsert((newElementnewElement););

}}

L’albero viene costruito inizialmente vuoto

Per l’inserimento di un nodo:- se l’albero è vuoto si crea semplicemente la radice- altrimenti si invoca sulla radice un metodo di inserimento della classe TreeNode


La classe La classe TreeNodeTreeNodeprivate class private class TreeNodeTreeNode{{private E private E valuevalue;;private private TreeNode leftTreeNode left;;private private TreeNode rightTreeNode right;;

public public TreeNode TreeNode (E _(E _valuevalue)){{value value = _= _valuevalue;;left left = = nullnull;;right right = = nullnull; ; }}

public public String toStringString toString()(){{return return valuevalue..toStringtoString();();} }




Metodo di inserimento Metodo di inserimento "ordinato" in "ordinato" in TreeNodeTreeNode

public public void insertvoid insert(E (E newElementnewElement)){{ifif ((newElementnewElement..compareTocompareTo((valuevalue) < 0) ) < 0) {{ifif ((leftleft == == nullnull))leftleft = new = new TreeNodeTreeNode((newElementnewElement););elseelseleftleft..insertinsert((newElementnewElement););

}}else else ifif ((newElementnewElement..compareTocompareTo((valuevalue) > 0) ) > 0) {{ifif ((rightright == == nullnull) ) rightright = new = new TreeNodeTreeNode((newElementnewElement););elseelserightright..insertinsert( ( newElementnewElement ););

}}}}

Il nuovo elemento è minore del valore di questo nodo: si va a sinistraSe a sinistra non c’è nulla, si crea lì un nuovo nodo

Altrimenti si invoca ricorsivamente il metodo sul figlio di sinistra

Il caso di elemento maggiore è del tutto analogo

Se newElement è un doppione, viene ignorato


Ricerca di un elemento Ricerca di un elemento (nella classe (nella classe BTreeBTree))

public public boolean binarySearchboolean binarySearch(E (E toFindtoFind) ) { { return return searchHelpersearchHelper((rootroot, , toFindtoFind); ); }}

private private boolean searchHelperboolean searchHelper((TreeNode nodeTreeNode node, E , E wantedwanted)){{ifif ((nodenode == == nullnull) return false;) return false;

ifif ((wantedwanted..compareTocompareTo((nodenode..valuevalue) == 0) ) == 0) return return truetrue;;

ifif ((wantedwanted..compareTocompareTo((nodenode..valuevalue) < 0)) < 0)return return searchHelpersearchHelper((nodenode..leftleft, , wantedwanted););elseelsereturn return searchHelpersearchHelper((nodenode..rightright, , wantedwanted););

}}

Il metodo di ricerca pubblico si avvale di un metodo ricorsivo privato

Se nella ricerca si arriva a null, l’elemento cercato non è presente

Qui abbiamo trovato l’elemento

La ricerca, se non è terminata, prosegue ricorsivamente a sinistra o a destra




Traversata in ordineTraversata in ordine

public public void inOrderTraversalvoid inOrderTraversal() () { { inOrderHelperinOrderHelper((rootroot); ); }}

private private void inOrderHelpervoid inOrderHelper((TreeNode nodeTreeNode node)){{ifif ((nodenode == == nullnull))return;return;

inOrderHelperinOrderHelper((nodenode..leftleft););System.out.System.out.printlnprintln((nodenode..toStringtoString()); ());

//o qualunque altra operazione//o qualunque altra operazioneinOrderHelperinOrderHelper((nodenode..rightright););}}


Traversata in Traversata in preordinepreordine

public public void preOrderTraversalvoid preOrderTraversal() () { { preOrderHelperpreOrderHelper((rootroot); ); }}

private private void preOrderHelpervoid preOrderHelper((TreeNode nodeTreeNode node)){{ifif ((nodenode == == nullnull))return;return;

System.out.System.out.printlnprintln((nodenode..toStringtoString()); ()); //o qualunque altra operazione//o qualunque altra operazione

preOrderHelperpreOrderHelper((nodenode..leftleft););preOrderHelperpreOrderHelper((nodenode..rightright););}}




Traversata in Traversata in postordinepostordine

public public void postOrderTraversalvoid postOrderTraversal() () { { postOrderHelperpostOrderHelper((rootroot); ); }}

private private void postOrderHelpervoid postOrderHelper((TreeNode nodeTreeNode node)){{ifif ((nodenode == == nullnull))return;return;

postOrderHelperpostOrderHelper((nodenode..leftleft););postOrderHelperpostOrderHelper((nodenode..rightright););System.out.System.out.printlnprintln((nodenode..toStringtoString()); ());

//o qualunque altra operazione//o qualunque altra operazione}}

Roadmap - tritone.ing.unibs.ittritone.ing.unibs.it/fp/Slides/VersionePDF/13-StruttureDati...Modulo...

Documents

Transcript of Roadmap - tritone.ing.unibs.ittritone.ing.unibs.it/fp/Slides/VersionePDF/13-StruttureDati...Modulo...