11. Strutture dati - copernico.bo.it · In Java le strutture dati di utilità sono contenute nel...

appunti Java pag.154

11. Strutture datiNella soluzione dei problemi sono già stati utilizzati diversi tipi di strutture datima fino ad ora non si è discusso in modo sistematico delle loro caratteristiche especificità d'uso. Una prima definizione approssimata di struttura dati potrebbeessere la seguente:

Una struttura dati è un "contenitore" diinformazioni che si caratterizza per i suoiattributi "logici", quali Modalità di accesso,Dimensionamento, Organizzazione dei suoicomponenti, o per gli attributi "fisici", quali iTempi di accesso ad un componente e la Persistenzadelle informazioni .

Un array ha i seguenti attributi "logici":1. Modalità di accesso

sequenziale se per trovare una informazione lo si deve scorrere dallaprima componente fino a quella desiderata;

indicizzato se si conosce la posizione del dato cercato e si usal'indice per accedervi direttamente.

2. Dimensionamento statico di norma, infatti un array una volta dimensionato nel

programma non può essere "fatto crescere".3. Organizzazione dei componenti

disordinata se questi vengono inseriti senza un particolare ordine; ordinata se gli Oggetti inseriti sono dotati di una particolare relazione

d’ordine che viene mantenuta dalla struttura: ordine Alfabetico,ordine di Grandezza crescente, decrescente ecc.;

in ogni caso un array è sempre aderente alla struttura della memoriaRAM in quanto ogni locazione di questa ha un indirizzo numerico el'array è memorizzato in celle adiacenti (sequenza) a cui si facorrispondere un indice intero da 0..n.

con componenti duplicati o non duplicati a seconda del programmache gestisce la struttura.

Ma un array è dotato anche dei seguenti attributi "fisici":4. Persistenza delle informazioni

"breve" o "volatile" in quanto la memoria conserva i dati solo fin cheil programma è in esecuzione o il computer è alimentato da corrente.Si dice che è una struttura dati Volatile (e non permanente comeinvece è il file memorizzato su supporto magnetico).

5. Tempi di accesso ad un componente "molto veloci" in quanto il suo supporto è la memoria RAM (ordine di

grandezza dei nanosecondi 10-9 s.). In contrasto con i file di caratterio byte che hanno per supporto un disco che sono "lenti" (ordine digrandezza dei millisecondi 10-3 s.).

In sostanza i parametri per valutare una struttura dati potrebbero essere:


Accesso Dimensionamento Organizzazione Persistenza Tempi di accesso sequenziale indicizzato

statico dinamico

ordinata disordinata con duplicati senza duplicati

volatile permanente

lento (10-3) veloce(10-9)

Se si analizzano le strutture dati a noi note e si classificano usando gli attributidiscussi si ottiene la seguente tabella comparativa:

Accesso Dimensionamento Organizzazione Persistenza Tempo di acc.Array mono opluridimensionale

sequenziale eindicizzato

statico disordinata oordinatacon duplicati

volatile veloce

File di caratteri obyte


dinamico disordinata oordinatacon duplicati

permanente lento

Stream o Filtro dicaratteri o byte


dinamico disordinata oordinata con duplicati

volatile lento o veloce

String oStringBuffer


dinamico in javastatico Pascal o C

disordinata oordinatacon duplicati

volatile veloce

11.1 Strutture dati di uso comuneE' pratica consolidata di chi progetta programmi quella di utilizzare tipi distrutture dati diverse a seconda del problema da risolvere in modo che questesiano aderenti alla specifica situazione. Si è quindi consolidata in informatica laformalizzazione di alcune strutture dati di uso frequente quali liste, pile, codeinsiemi, alberi, grafi e altre ancora.I linguaggi più moderni forniscono queste strutture dati, con le relative operazioniformalizzate, per sollevare di una parte di lavoro di codifica il programmatore diapplicazioni. In Java le strutture dati di utilità sono contenute nel packagejava.util (in parte in java.io visto in precedenza) e ciascuna di esse è una classeche appartiene ad una ben strutturata gerarchia. Si studieranno in seguitoalcune delle classi più importanti del package java.util.

11.2 ListeUna delle strutture dati di più largo uso in programmazione è la Lista che sipotrebbe definire come un Abstract Data Type (Tipo di Dato Astratto) nel seguentemodo:

Una lista è una struttura dati sequenzialecostituita da zero o più oggetti.

La definizione ci informa che: Una lista può essere vuota; Se non è vuota ha un primo elemento (detto anche testa della lista) e un

ultimo elemento;


INIATT

. . . . . . EOF

Ogni suo elemento, esclusi il primo e l'ultimo, è dotato di un predecessore edi un successore;

Può essere virtualmente illimitata (su un computer la lista è forzatamentelimitata dalle dimensioni della memoria)

Si rappresenta, come una successione, nel seguente modo { a1, a2, ... , an}

Tra le strutture dati studiate la String è una tipica Lista di caratteri, come pureun File di caratteri o di byte. Il file è stato rappresentato come una sequenza didati nel seguente modo:

Analogamente al File si potrebbe immaginare la rappresentazione grafica di unalista come una struttura costituita da Nodi; tali nodi contengono Oggetti (leinformazioni) collegati tra loro da "link o reference" mediante i quali è possibilepassare da un nodo al suo successore (predecessore) come nella figura.

Si nota che una lista deve essere sempre dotata di un "link" particolare che indicala sua "testa" (iniz) e deve essere dotata di un "segno" particolare (null) che neindica la conclusione.A differenza del file questa struttura, memorizzata in memoria di lavoro, è volatile.Ogni Object deve essere dotati di uno o più link che indicano il suo successore(e/o predecessore); tale link sono rappresentati graficamente con una freccia.Una struttura dati di questo tipo (una classe in Java) di quali operazioni deveessere dotata ?

Ragionando sull'Abstract Data Type Lista si dovrebbe disporre di :

Costruttore/iInserzione, Cancellazione e Ricerca:

Aggiunta di un oggetto in testa Aggiunta di un oggetto in coda Aggiunta di un oggetto in una posizione qualsiasi Cancellazione di un oggetto noto Cancellazione di un oggetto di posizione nota Ricerca dell'esistenza di un oggetto noto Determinazione della posizione di un oggetto noto

Concatenazione: Aggiungere una Lista in coda a una Lista data

Altri metodi: Operatore per leggere l'oggetto di testa Operatore per leggere l'oggetto in coda Operatore per leggere un oggetto di posizione nota Operatore per stabilire se la lista è Vuota o meno

Object Object Object Object

null

iniz


Operatore per conoscerne la dimensione Operatore per sapere se durante la lettura si è giunti al termine della

Lista (deve consentire lo scorrimento in sequenza dal primo all'ultimoelemento);

Se si analizza la struttura di Lista e la si classifica usando gli attributi discussi siottiene la seguente tabella comparativa:

Accesso Dimensionamento Organizzazione Persistenza Tempo di acc.ListaSequenziale sequenziale dinamico disordinata o

ordinatacon duplicati

volatile veloce

La classe LinkedList del package java.util rappresenta pienamente tale ADT. Eccodi seguito i suoi metodi:

Classe LinkedListIdentificatori: LinkedList();

Invocazione: LinkedList L =new LinkedList();

Costruttori

Effetti: Crea un oggetto Lista identificato da L vuoto.

Identificatore void add(Object);void add(Index, Object);void addFirst(Object);boolean remove(Object);Object remove(Index);void clear();boolean contains(Object);int indexOf(Object);boolean addAll(Collection);Object getFirst();Object getLast();Object get(Index);boolean isEmpty();int size();Iterator iterator();ListIterator listIterator():

Invocazione:

Metodi

Effetti::Pckage eGerarchia

java.util java.Object java.util.AbstractCollection java.util.LinkedList

Si noti che i metodi iterator() e listIterator() sono metodi particolari che hanno lafunzione di creare un Oggetto iteratore (più esattamente si tratta di unainterfaccia) che serve per "scorrere" la lista.

Un Iterator e un ListIterator differiscono solo lievemente. Il primo è dotato di duemetodi e consente di scorrere la sequenza solo dalla testa alla fine, mentre ilsecondo possiede altri due metodi che consentono lo scorrimento a ritroso.


Interface IteratorUsando un opportuno metodo che ottiene unIteratore da una Classe di tipo "struttura dati"come ad esempio la LinkedList, un Vector o unSet

Come si ottiene uniterator

esempio LinkedList L=new LinkedList(); ....Iterator iter = L.iterator();

Identificatore boolean hasNext();Object next();

Invocazione: LinkedList L= ......;......;Iterator iter=L.iterator(); // crea un iteratorewhile (iter.hasNext()) { // iter non è finito ? Object o = iter.next(); // leggi l'oggetto .....; }

Metodi

Effetti:: Scorre l'iteratore ottenuto dalla lista dal primoall'ultimo oggetto.

Pckage eGerarchia

java.util java.Object java.util.Iterator

Interface ListIteratorUsando un opportuno metodo che ottiene unIteratore da una Classe di tipo "struttura dati"come ad esempio la LinkedList, un Vector o unSet

Come si ottiene unListIterator

esempio LinkedList L=new LinkedList(); ....ListIterator iter = L.listIterator();

Identificatore boolean hasNext();Object next();boolean hasPrevious();Object previous();

Invocazione: ListIterator iter=L.listIterator();// Attenzione ! Il puntatore è sulla testa della// lista e la chiamata:boolean B = iter.hasPrevious();// restituisce false e quindi non si può scorrere a// ritroso se prima non si è usato next()

Metodi

Effetti:: Scorre l'iteratore ottenuto dalla lista dal primoall'ultimo oggetto e viceversa.

Pckage eGerarchia

java.util java.Object java.util.ListIterator

Per verificare la differenza tra l'interfaccia Iterator e ListIterator si propone unesempio che indica come fare per creare e scorrere una lista dal primo all'ultimoelemento.

esempio 1. "Si desidera realizzare una lista nella quale inserire alcuni OggettiInteger, String e Boolean e quindi stamparli in sequenza." Richiesta:Realizzare un main() che prima inserisca i dati e poi li stampi tramite un ciclo.


Codifica:import java.util.*;public class cap11_es_01 {

public static void main(String args[]) {LinkedList L=new LinkedList(); // (1)Integer I=new Integer(99);L.add(I); // (2)String S=new String ("Banana");L.add(S); // (3)Boolean B=new Boolean(true);L.add(B); // (4)I=new Integer(3); L.add(I);I=new Integer(17); L.add(I);B=new Boolean(false); L.add(B);System.out.println("Lista di "+L.size()+" Oggetti:"); // (5)Iterator it=L.iterator(); // (6)while (it.hasNext()) // (7)

System.out.println(""+it.next()); // (8)System.out.println("Fine esecuzione.");

}}

Esecuzione: l’output della finestra sarà:

Lista di 6 Oggetti:99Bananatrue317falseFine esecuzione.

Commento al codice:La nota (1) mostra il costruttore, le (2, 3, 4) la costruzione e l'inserimento dioggetti, la (5) invoca il metodo che restituisce l'Iteratore it con il quale siutilizzano i metodi it.hasNext() (6) e it.next() (7) per realizzare il ciclo di scansionedella Lista. Il metodo hasNext() esegue il test per verificare se si è giunti alla finedella lista e next() acquisisce in lettura l'oggetto e sposta il puntatore all’elementosuccessivo.

Sostituendo alle ultime righe le seguenti (6', 7', 8', 9', 10')si ottiene prima unidentico risultato (la stampa diretta) e quindi la stampa inversa della lista.

ListIterator lit=L.listIterator(); // (6')while (lit.hasNext()) // (7')

System.out.println(""+lit.next()); // (8')System.out.println("Fine lettura diretta.");while (lit.hasPrevious()) // (9')

System.out.println(""+lit.previous()); // (10')System.out.println("Fine lettura inversa.");


esempio 2. "progettare una sottoclasse di LinkedList chiamata Lista cheimplementi il solo metodo di inserimento ordinato di Stringhe in modo che ciascunastringa sia collocata in ordine lessicografico." Richieste:Il metodo oltre a mantenere l'ordine deve inserire anche stringhe ripetute chedovranno essere consecutive. Il main() di prova dovrà stampare la lista con uniteratore per verificare il corretto funzionamento del metodo.

L’esercizio chiede di progettare la classe Lista sottoclasse di LinkedList comemostrato dalla figura sottostante. La sottoclasse da progettare non ha unavalidità generale nel senso che non consente di inserire in modo ordinato Oggettiqualunque ma solo oggetti di tipo String. Si tratta di un esempio moltoparticolare.Codifica della sottoclasse:import java.util.*;public class Lista extends LinkedList {

public void put(String S) {int i=0; boolean trovato=false, esiste=false;while (i<size() && !trovato && !esiste) { (0)

String A=(String) get(i);if (A.compareTo(S)>0) trovato=true; (1)else if (A.compareTo(S)==0) esiste=true; (2)

else i++; (3)}add(i,S); (4)}

}

Codifica del main:import java.util.*;public class cap11_es_02 {

public static void main(String args[]) {Lista L=new Lista(); (5)String S[]={"fico","banana","mela","fico","zucca","pera","pera"};for (int i=0; i<S.length; i++)

L.put(S[i]); (6)System.out.println("\nLista di "+L.size()+" Oggetti:"); (7)Iterator it=L.iterator(); (8)while (it.hasNext()) (9)

System.out.println(""+it.next()); (10)System.out.println("\nFine esecuzione.");

}}

Output:

Lista di 7 Oggetti:bananaficoficomelaperaperazucca

Fine esecuzione.

Commento al codice:

LinkedList

Lista


Nel metodo put() la condizione (0) evidenzia che l’inserimento ordinato può essereeseguito solo dopo una ricerca che determina la posizione di inserimento dellastringa nella lista. La ricerca ha termine in tre casi distinti (1) se ho trovato unastringa che segue alfabeticamente quella da inserire; (2) se ho trovato una stringaidentica a quella da inserire; (3) se sono arrivato al termine.La nota (4) evidenzia il metodo usato per inserire la stringa nella popsizionecorretta. Le note da (5) a (10) mostrano che la sottoclasse Lista è autorizzata adusare i metodi della classe genitrice che ha ereditato.

11.3 Vettori dinamiciTra le altre strutture dati di vasto uso in programmazione vi è sicuramentel'array; ma anche in java si tratta di una struttura dati sostanzialmente statica.Anche se può essere dimensionato dinamicamente durante l'esecuzione, la suadimensione non è più modificabile pena la perdita delle informazioni allocate finoa quel momento.Un vettore dotato di indice e capace di crescere dinamicamente come la Listasarebbe ideale per risolvere problemi che devono trattare i dati sia in sequenza(lista) che in modo indicizzato (array). Una struttura con queste caratteristichedeve forzatamente sacrificare "sull'altare della dinamicità " un poco di efficienzama la sua costruzione è possibile e in effetti tale struttura "ibrida" è presente injava.util sotto forma di Classe con i seguenti metodi:

Classe VectorIdentificatori: Vector();

Vector(Collection c);Vector(int initCapacity);Vector(int initCapacity, int capacityIncr);

Invocazione: Vector V = Vector();

Costruttori

Effetti: Crea un oggetto Vector identificato da V vuoto.

Identificatore void add(Object);void add(Index, Object);void insertElementAt(Index, Object);void setElementAt(Index, Object);boolean remove(Object);void removeElementAt(Index);void clear();boolean contains(Object);int indexOf(Object);boolean addAll(Collection);Object elementAt(Index);Object get(Index);boolean isEmpty();int size();int capacity()

Invocazione:

Metodi


java.util java.Object java.util.AbstractCollection java.util.Vector


Se si analizza le struttura di tipo Vector e la si classifica usando gli attributidiscussi si ottiene la seguente tabella comparativa:

Accesso Dimensionamento Organizzazione Persistenza Tempo di acc.Vector sequenziale e

indicizzatodinamico disordinata o

ordinatacon duplicati

volatile veloce

per verificare come operare per creare e scorrere un Vector dal primo all'ultimoelemento proponiamo un esempio.

esempio 3. "Si desidera realizzare un Vector nel quale inserire alcuni OggettiInteger, String e Boolean e quindi stamparli in sequenza." Richiesta:Realizzare un main() che prima inserisca i dati e poi li stampi in un ciclo.

Codifica:import java.util.*;public class cap11_es_03 { public static void main(String args[]) {

Vector V=new Vector(); // (1)Integer I=new Integer(99);V.add(I); // (2)String S=new String ("Banana");V.add(S); // (3)Boolean B=new Boolean(true);V.add(B); // (4)I=new Integer(3); V.add(0,I); // (5)I=new Integer(17); V.setElementAt(I,1); // (6)B=new Boolean(false); V.add(B);System.out.println("Capacità="+V.capacity()+" Dimensione="+V.size()); // (7)int i=0; // (8)while (i<V.size()) { // (9)

System.out.println("V["+i+"]="+V.get(i)); // (10) i++; }

System.out.println("Fine esecuzione.");}

}


Capacità=10 Dimensione=5V[0]=3V[1]=17V[2]=BananaV[3]=trueV[4]=falseFine esecuzione.

Commento al codice:La nota (1) mostra il costruttore, le (2, 3, 4) la costruzione e l'inserimento in codadi oggetti, la (5) invoca il metodo che inserisce un elemento nella componente diposizione 0, la (6) utilizza il metodo di sovrascrittura sull'Oggetto di posizione 1,(l'Integer 99 viene sovrascritto in modo distruttivo). Le (7 8, 9, 10) utilizzano imetodi necessari per realizzare il ciclo di scansione del Vector utilizzando l'indicedi scorrimento.


11.4 Collezioni e InsiemiSi discuteranno dal punto di vista astratto due strutture dati la Collezione el'Insieme per vedere le proprietà di cui godono. In particolare un insieme (dioggetti) deve rispettare la nozione che conosciamo dalla matematica e consentirel'esecuzione corretta delle operazione note.

Un insieme è una collezione o aggregato di oggettidefiniti e distinti tra loro che si dicono elementidell'insieme.

Alla nozione di insieme sono associate simboli e operazioni in particolare siutilizzano i simboli di:

appartenenza [ x ε D ] insieme vuoto [ Φ ] sottoinsieme [ A ⊆⊆⊆⊆ B] rappresentazione dell'insieme [ { a,b,c,d})

Ci attendiamo poi che si possano eseguire le operazioni di: Unione [ ∪∪∪∪ ] Intersezione [ ∩∩∩∩ ] Differenza.

Ragionando sull'Abstract Data Type Insieme si dovrebbe disporre di :

Costruttore/iInserzione, Cancellazione e Ricerca:

Aggiunta di un oggetto all'insieme (solo se non è già presente) Cancellazione di un oggetto noto Ricerca dell'esistenza di un oggetto noto (appartenenza) Sottoinsieme

Operazioni: Unione Intersezione Differenza

Altri metodi: Cardinalità dell'insieme (la sua dimensione attuale) Operatore per stabilire se si tratta di un insieme Vuoto Operare lo scorrimento (in qualche modo) di tutti gli oggetti per

ottenerne una rappresentazione tabulare.

La nozione di Insieme utilizza il termine Collezione o Aggregato di oggetti, e sipotrebbe pensare che una Collezione sia un termine che designa una entità piùgenerale (o generica) del concetto di insieme. In cosa può consistere talediversità? Che cosa hanno in comune Collezione e l'Insieme?

Potremmo dire che sia la Collezione che l'Insieme hanno la proprietà comune diessere entrambi "contenitori" di oggetti senza ordine (non esiste un primo o unultimo elemento di un insieme, esso può contenere oggetti non confrontabili).


Contemporaneamente potremmo dire che la differenza tra le due entità consistenel fatto che l'insieme NON ammette elementi ripetuti mentre una Collezionepuò ammetterli.Potremmo definire tale struttura dati nel seguente modo:

la Collezione è una raccolta di oggetti distinti oduplicati. In altri termini si potrebbe dire che unInsieme è una Collezione che non ammette oggettiduplicati.

Ma quali sono le operazioni che ci attendiamo di poter eseguire su una entità(struttura dati) di questo tipo ?Nella seconda definizione si nota che esiste una relazione di generalizzazione traInsieme e Collezione (un insieme è una collezione particolare) che potrebberendere applicabile il concetto di ereditarietà tipico della progettazione di classi.Molte delle operazioni che valgono per una Collezione potrebbero valere anche perun Insieme.

Accesso Dimensionamento Organizzazione Persistenza Tempo di acc.Insieme non sequenziale

non indicizzatodinamico disordinata

senza duplicativolatile veloce

Collection non sequenzialenon indicizzato

dinamico disordinatacon duplicati

volatile veloce

Si analizzerà di seguito la struttura della gerarchia delle Classi e Interfacce dijava.util, per progettare se necessario gli ADT che non ci soddisfanocompletamente.

alcune classi e interfacce del package java.util

Object

Vector

AbstractCollection

Stack java.util (parte)

LinkedList HashSet

Coda

Collection

List Set

ListIterator

Iterator

Insieme

TreeSet


Lasciando al lettore l'analisi delle altre Classi del package java.util quali Date,Calendar, Time molto utili nella programmazione di applicazioni, si cercherà diinterpretare la "filosofia" con cui le sole classi in grassetto nella gerarchiadisegnata sono state progettate.

La prima cosa da notare è la gerarchia di Classi:AbstractCollection, LinkedList, Vector, HashSet.e di InterfacceCollection, List e Set.Il progettista ha deciso che le caratteristiche comuni a tutte le strutture datidinamiche sono "raggruppate" nella classe AbstractCollection che implemental'intefaccia Collection.In altri termini tutte le strutture dati dinamiche sono collezioni. In altre parolepossono essere "pensate" come raccolte indifferenziate di oggetti duplicati o meno.Un HashSet è una Collection cosi come lo è una LinkedList o un Vector.

La seconda cosa da notare è che non tutti gli ADT Collection sono Liste. Ilprogettista ha suddiviso le Collection in strutture dati sequenziali (LinkedList,Vector) e per queste ha realizzato l'interfaccia List e in strutture senza duplicati(HashSet e TreeSet) e per queste ha realizzato l'interfaccia Set.In altre parole una LinkedList e un Vector sono una List, un HashSet è un Set.Tutte sono AbstractCollection e quindi Collection.

Se si esamina la classe HashSet, o l'interfaccia Set, sotto sono elencati costruttorie metodi, si nota che le operazioni non sono del tutto coincidenti con quelle atteseper una struttura dati di tipo Insieme.

Classe HashSetIdentificatori: HashSet();

HashSet(Collection c);Invocazione: HashSet A = new HashSet();

Costruttori

Effetti: Nel primo caso Crea un oggetto HashSetidentificato da A vuoto. Nel secondo crea un set daun Vector eliminando i duplicati.

Identificatore void add(Object);boolean remove(Object);boolean removeAll(Collection);void clear();boolean equals(HashSet);boolean contains(Object);boolean addAll(Collection);boolean isEmpty();int size();

Invocazione:

Metodi


java.util java.Object java.util.AbstractCollection java.util.HeshSet


Mancano le operazioni "dirette" di Unione e Intersezione e Differenza anche seesistono operazioni di concatenamento tra Collection e di cancellazione dielementi o collezioni. Questa insoddisfazione sarà "risolta" progettando una classeInsieme come sottoclasse di HashSet nella quale siano implementate leoperazioni elencate in precedenza per gli insiemi.

Per quanto riguarda la Collection, l'interfaccia esistente in java.util può esseresoddisfacente in quanto consente tutte le operazioni di inserimento, ricerca ecancellazione e mantiene anche elementi duplicati.

11.4.1 La sottoclasse InsiemeSi progetterà di seguito la classe insieme come sottoclasse di HashSet e si farà inmodo che questa sia ancora una Collection. La gerarchia del paragrafoprecedente mostra la collocazione ereditaria della classe Insieme. Di seguito si èindicato lo schema della classe con i metodi richiesti.

La codifica è lasciata come esercizio al lettore esercizio 11.09.

Proponiamo un esempio di utilizzo della Classe Insieme progettata.

esempio 4. "Assegnare a un insiemi i numeri da 20 a 29 e ad un secondo insieme inumeri 15 a 24 e stamparli. Ottenere Unione, Intersezione e le due differenze estamparle ancora". Richiesta : realizzare il solo main().

HashSet

Insieme

Insieme()Insieme(Collection c);

Insieme unione(Insieme i);Insieme intersezioine(Insieme i);Insieme differenza(Insieme i);boolean contiene(Object o);void metti(Object o);boolean togli(Object o);boolean vuoto();int cardin();boolean sottins(Insieme i);boolean identico(Insieme i);void svuota();Iterator iterator();



public static void main(String args[]) {Insieme L=new Insieme(),L1=new Insieme();for (int i=20; i<30; i++) L.metti(new Integer(i)); // (1)for (int i=15; i<25; i++) L1.metti(new Integer(i));// stampare con IteratorSystem.out.println("\nL1 ha "+L1.cardin()+" Oggetti:");Iterator it=L1.iterator(); // (2)while (it.hasNext()) System.out.print(""+it.next()+",");// stampare la Collection con toString()System.out.println("\nL ha "+L.cardin()+" Oggetti:");System.out.println(L); // (3)

// unione Insieme C=L1.unione(L);

System.out.println("\nL1 + L="+C);// intersezione

C=L1.intersezione(L);System.out.println("\nL1 * L="+C);

// prima differenzaC=L.differenza(L1);System.out.println("\nL - L1="+C);// seconda differenzaC=L1.differenza(L);System.out.println("\nL1 - L="+C);

}}

Esecuzione:

l’output della finestra sarà:L1 ha 10 Oggetti:20,21,22,23,24,25,26,27,28,29,L ha 10 Oggetti:[15, 16, 17, 18, 19, 20, 21, 22, 23, 24]L1 + L=[15, 16, 17, 18,..,25, 26, 27, 28, 29]L1 * L=[20, 21, 22, 23, 24]L – L1=[15, 16, 17, 18, 19]L1 – L=[25, 26, 27, 28, 29]

Le note (1) (2) (3) evidenziano i metodi utilizzati per costruire l’insieme, stamparlousando un iteratore oppure il metodo toString() di ogni Collection.

esempio 5. "Immettere in un insieme i numeri da 1 a 25 e stamparlo, eliminaretutti i numeri dispari e stamparlo ancora". Richiesta : realizzare il solo main().


public static void main(String args[]) {Insieme L=new Insieme();for (int i=1; i<26; i++) L.metti(new Integer(i));// stampaSystem.out.println("\nL ha "+L.cardin()+" Oggetti:");System.out.println(L);

// Eliminazione


for (int d=1; d<26; d=d+2) { Integer A=new Integer(d); L.togli(A); }

// stampaSystem.out.println("\nL ha "+L.cardin()+" Oggetti:");System.out.println(L);

}}

Esecuzione:

l’output della finestra sarà:L ha 25 Oggetti:[1,2,3,..,20,21,22,23,24,25]L ha 12 Oggetti[2,4,6,8,10,12,14,16,18,20,22,24]

11.4.2 L'interfaccia CollectionSe si guarda la cima della piramide delle Classi java.util si nota che tutte lestrutture date implementano l’interfaccia Collection e quindi possono esseretrattate tutte come Collezioni di oggetti. Tutte le Classi che sono Collectiondebbono implementare i seguenti metodi:

Interface CollectionIdentificatori: Class AbstractCollectionClassi che imple-

mentano l’inter-faccia Collection Si ricorda che Abstract collection è genitrice di

tutte le struture studiate: LinkedList, Vector,HasSet ecc.

Metodi Identificatore boolean add(Object);boolean addAll(Collection);boolean remove(Object);boolean removeAll(Collection);void clear();boolean equals(Collection);boolean contains(Object);boolean isEmpty();int size();

Package java.util

esempio 6: “Dopo aver creato una oggetto Vector di Numeri che contengasicuramente duplicati, ottenere rapidamente, usando i metodi di Collection, daquesto un Insieme senza duplicati.”Richieste:Nel main() generare un vector con duplicati, stamparlo, trasformarlo in Insieme estamparlo di nuovo.



public static void main(String args[]) {Vector A=new Vector();A.add(new Integer(11));A.add(new Integer(11));A.add(new Integer(23));A.add(new Double(3.1));A.add(new Double(9.9));A.add(new Double(9.9));System.out.print("Contiene "+A.size()+" elementi\n Contiene="+A);Insieme I=new Insieme(A);System.out.print("\nContiene "+I.size()+" elementi\nContiene="+I+"\n");

}}

Output:Contiene 6 elementiContiene=[11, 11, 23, 3.1, 9.9, 9.9]Contiene 4 elementiContiene=[11, 23, 9.9, 3.1]

11.5 Pila e CodaDue ulteriori strutture dati usate in programmazione sono la Coda e la Pila (ininglese Queue e Stack). Queste due strutture dati sono di norma utilizzate come“intermediari” tra un processo produttore di Dati e un processo consumatore. Inqualche modo sono analoghe al concetto di Stream o di Filtro visto nel capitolo 9.Infatti uno stream o un filtro sono entità che mettono in comunicazione dueprocessi.Allo stesso modo pila e coda sono utilizzate in programmazione per collegare unprocesso produttore e uno consumatore:

Us esempio di processo che usa una Coda è un qualsiasi programma di Stampa;questo è un processo produttore di caratteri ad alta velocità mentre unastampante è un processo consumatore di caratteri molto lento. La Coda diStampa è l’intermediario che consente di accumulare i caratteri prodotti dalprogramma e pronti per la stampa in attesa che il processo di stampa li consumialla sua ridotta velocità. In questo caso la coda funge da “filtro sincronizzatore”dei due processi.

Produttore Consumatore

X Y Z T

Coda

Produttore Consumatore

PilaXYZ

Programma Stampante

X Y Z T

Coda di stampa


Così una Pila è usata per mantenere processi “sospesi” in attesa che altri processi“abbiano completato il lavoro”. Si immagini un “programma P” che chiama una“procedure P1” la quale a sua volta chiama una “procedure P2” e così via come infigura.

In questo esempio la Pila degli indirizzi di programma consente di mantenerel’ordine corretto di esecuzione; il processo principale P viene sospeso (e simemorizza l’indirizzo di rientro 40) in attesa che venga svolto il processo P1, maquesto incontra la chiamata di P2, P1 è sospeso (si memorizza l’indirizzo dirientro 180) in attesa che P2 abbia termine. Quando P2 ha termine il controllo delprocesso ritorna a P1 e quando questo termina il controllo ritorna la processoprincipale P. Questo lavoro è svolto da una Pila che come in figura accumula gliindirizzi a cui i processi sospesi e debbono poi essere riavviati.

Dagli esempi mostrati si nota che le strutture dati Pila e Coda hanno in letturaun comportamente molto simile a Stream, ma molto diverso rispetto a List, Vectoro Insieme. Infatti Pila, Coda, Stream sono strutture nelle quali la lettura èdistruttiva, nel senso che leggendo il dato lo si cancella-consuma. List, Vector eSet cono contenitori senza lettura distruttiva, infatti consentono di leggere leinformazioni più volte senza eliminarle.

11.5.1 l’ADT PilaSi potrebbe dare le seguente definizione dell’ADT:

Si dice Pila una struttura dati sequenziale che consentel’input e l’output di un dato da uno stesso lato dellasequenza.

Processo P

Processo P1

Processo P2

10 istr. 120 istr. 230 chiama P140 istr. 350 fine P.

160 istr. xx170 chiama P2180 fine P1

260 istr. yy270 istr. zz280 fine P2

40

18040

40

180

40

put Pila

put Pila

get Pila

get Pila


La figura mostra graficamente uno Stack:

In sostanza l’ultimo elemento che entra nella coda è anche il primo elemento chene esce. La Pila prende il nome di struttura (LIFO) Last In First Out. Oltre aquesto si deve ricordare che la lettura di un dato è distruttiva.

Queste sono le operazioni che caratterizzano l’ADT Pila:

Costruttore/i Aggiunta di un oggetto in testa Lettura distruttiva dell’oggetto di testa Lettura NON distruttiva dell’oggetto di testa Operatore per stabilire se La Pila è vuota

In Java esiste la Classe Stack come sottoclasse di Vector con i seguenti metodi

Classe StackIdentificatori: Stack();

Invocazione: Stack A = new Stack();

Costruttori

Effetti: Nel primo caso Crea un oggetto Stack identificatoda A vuoto.

Metodi Identificatore void push(Object);Object pop();Object peek();boolean isEmpty();

Pckage eGerarchia

java.util java.Object java.util.AbstractCollection java.util.Vector java.util.Stack

esempio 7. “creare e stampare uno Stack di Integer”


public static void main(String args[]) {Stack A=new Stack();for (int i=0; i<7; i++)

A.push(new Integer(i));while (!A.isEmpty())

System.out.println(A.pop());}

}

Dato n

….

Dato 2

Dato 1

Push Dato Pop Dato



6543210

esempio 8. “usare una Pila per verificare se una sequenza di parentesi tondeaperte e chiuse è legittima”

Indicazioni: una sequenza corretta di parentesi è quella usata per scrivereespressioni aritmetiche rispettando l’ordine di priorità. La correttezza èindipendente dal contenuto. Es. la sequenza (()())() è corretta la sequenza (()()() èerrata perche manca una parentesi chiusa. In ogni caso non basta che il numerodi parentesi aperte sia uguale a quelle chiuse, infatti nell’esempio ())(() le parentesipur essendo equilibrate non sono corrette.Un algoritmo per verificare la correttezza della sequenza, facendo uso di unoStack, potrebbe essere il seguente:inserisci la sequenza di parentesi in uno StringBuffer Sb;

1. crea uno Stack Vuoto St;2. Fintanto che (Sb non è vuoto <e> non c’è errore)3. preleva una parentesi da Sb;4. Se è una ‘(‘ Allora inseriscila nello Stack;5. Altrimenti Se lo Stack non è Vuoto Allora preleva la ‘(‘6. Altrimenti c’e un Errore7. Se (Stack è Vuoto <e> non c’e errore) Allora la sequenza è Corretta8. Altrimenti la sequenza è Errata


public static void main(String args[]) {StringBuffer Sb=new StringBuffer(args[0]); // input args[0]Stack St=new Stack();boolean err=false;while (Sb.length()!=0 && !err) {

char Ch=Sb.charAt(0);Sb=Sb.deleteCharAt(0);if (Ch=='(') St.push(new Character(Ch));else if (!St.isEmpty()) St.pop();

else err=true;}

if (!err && St.isEmpty()) System.out.println("OK");else System.out.println("ERRATA");}

}


11.5.2 l’ADT Coda

Si potrebbe dare le seguente definizione di Coda:

Si dice Coda una struttura dati sequenziale che consentel’input di un dato da un capo e l’output dal capo opposto.

La figura mostra graficamente una Coda:

In sostanza il primo elemento che entra nella coda è anche il primo elemento chene esce. La Coda prende il nome di struttura (FIFO) First In First Out. Oltre aquesto si deve ricordare che la lettura di un dato è distruttiva.

Operazioni che caratterizzano l’ADT Coda: Costruttore/i Aggiunta di un oggetto in coda Lettura distruttiva dell’oggetto di testa Lettura NON distruttiva dell’oggetto di testa Operatore per stabilire se la Coda è vuota

in Java NON esiste una tale struttura ma la si può facilmente progettare comesottoclasse di LinkedList. Di seguito si fornisce il diagramma della classe Codaprogettata come sottoclasse di LinkedList.

La progettazione della sottoclasse Coda è lasciata come esercizio vedi 11.18

LinkedList

Coda

+ Coda()

+ put(Object) : void+ get( ) : Object+ peek( ) : Object+ isEmpty( ) : boolean

Dato n ….. Dato 2 Dato 1Put Dato Get Dato


esempio 9 :“creare e stampare una CODA di Integer”


public static void main(String args[]) {Coda A=new Coda();for (int i=0; i<5; i++)

A.put(new Integer(i));while (!A.isEmpty())

System.out.println(A.get());}

}


01234

esempio 10. “Date due code di parole ordinate, fonderle in una terza codamantenendo l’ordine lessicografico”.Richieste: nel main() creare le due code ordinate partendo da due Array distringhe ordinate usando gli opportuno metodi di coda.Realizzare poi un metodo statico fusione() con gli opportuni parametri erichiamarlo.


public static Coda fondi(Coda a, Coda b) {Coda C=new Coda();while (!a.isEmpty() && !b.isEmpty()) {

String Sa=(String) a.peek();String Sb=(String) b.peek();if (Sa.compareTo(Sb)<=0) {C.put(Sa); a.get();}else { C.put(Sb); b.get();}}

if (a.isEmpty()) C.addAll(b); else C.addAll(a);return C;}

public static void main(String args[]) {String[] S1={"asino", "cavallo", "somaro"};String[] S2={"cane", "cavalla", "leone", "liocorno"};Coda A=new Coda();for (int i=0; i<S1.length; i++)

A.put(new String(S1[i]));System.out.println("Coda A="+A);Coda B=new Coda();for (int i=0; i<S2.length; i++)

B.put(new String(S2[i]));System.out.println("Coda B="+B);Coda C=fondi(A,B);System.out.println("Coda A+B="+C);}

}



Coda A=[asino, cavallo, somaro]Coda B=[cane, cavalla, leone, liocorno];Coda A+B=[asino, cane, cavalla, cavallo, leone, liocorno, somaro]

11.6 Alberi BinariDefinizione di Albero Binario

1. Un albero binario è un Nodo vuoto (null) chiamato Radice2. Oppure è un Nodo Radice dotato di due alberi binari

detti sottoalberi sinistro e destro.

La difinizione è ricorsiva in quanto la seconda riga definisce un albero binariousando la parola albero binario. Aiutiamoci con alcuni esempi di alberi binari:

Il caso (A) soddisfa alla definizione (1). I casi (B) (C) alla definizione di riga (2) eriga (1). Infatti (B) ha una Nodo Radice (def. 2) e due sottoalberi Vuoti (def. 1).

Un albero si caratterizza per il numero di Livelli o Profondità. La profondità di(A) e (B) è 0 quella di (C) è 2. Si ricorda che il livello della radice è il livello 0 e isuccessivi sono i livelli 1, 2,..n.Le Foglie di un Albero sono i nodi terminali. L’albero (C) ha tre foglie 20, 36, 99.L’albero (B) ha una sola foglia 33 che coincide con la Radice.I Rami sono i collegamenti tra Nodi.

11.6.1 Generazione, Visita e Ricerca in un albero Binario

Un albero Binario di norma memorizza nei nodi informazioni con Chiavi nonRipetute o Univoche.

Si dice Campo Chiave di una informazione il campo che la caratterizzaUnivocamente.

Ad esempio se le informazioni da memorizzare in un nodo sono Cognomi (nonripetuti) di persone e le relative età, il campo Chiave diviene il Cognome, ciascunnodo conterrà tutta l’informazione ma il campo chiave è il solo Cognome.Il nodo avrà la seguente struttura:

Albero (A)

null

Albero (B) Albero (C)

33

38

33

nullnull

nullnull 20

9936


Se invece le informazioni da memorizzare sono Cognomi e Nomi che si possonoripetere, occorre definire un campo chiave diverso; per esempio il Codice Fiscaleche ha la caratteristica di essere univoco per ogni cittadino.Il nodo avra la seguente struttura:

Il campo chiave univoco è essenziale sia per generare correttamente l’albero siaper ricercare le informazioni in modo rapido.La visitazione di un albero, la lettura dei suoi nodi, può essere eseguita in variemodalità le due principali sono la visita in Profondità e quella in Ampiezza.Per esempio la visita in profondità con il metodo SRD (Sinistra Radice Destra) perl’albero (C) genera la seguente sequenza di lettura:

20, 33, 36, 38, 99

Una visita in ampiezza la seguente:

33, 20, 38, 36, 99

In seguito si tratterà di un solo tipo di albero binario, in particolare di AlberiBinari Ordinati ed Equilibrati, generati e scanditi in modalità SRD.

(a) Generare un albero in modalità SRD significa che ogni Nodo ha nel suosottoalbero sinistro solo CHIAVI Minori della radice e viceversa nel sottoalberoDestro.(b) La lettura di un tale albero produce sempre un elenco con Chiavi Ordinate inmodo Crescente.(c) Se l’albero è Equilibrato, ovvero la differenza tra la maggiore e la minore dellesue profondità non è mai superiore ad UNO, il tempo per la ricerca di una Chiaveè molto rapida e non impiega mai un numero di confronti tra nodi superiore

2log N dove N è il numero totale dei Nodi.

Cognome età

chiave

Cognome età

chiaveNomeCod.Fiscale

Albero (C)

38

33

20

9936

Albero (C)

38

33

20

9936


L’albero C soddisfa tette le condizioni (a), (b),(c).

Se si deve eseguire una ricerca su un numero molto alto di elementi e siconfrontano le velocità di ricerca in una Lista Sequenziale rispetto ad un Albero,si possono notare immediatamente i vantaggi offerti dal secondo:

Lista Sequenziale Albero Binario BilanciatoNr. Elementi Numero max.ricerche Numero max.ricerche8 8 2log 8=3128 128 2log 128=71.024 1.024 2log 1024=101.048.576 1.048.576 2log 1048576=20

I vantaggi elencati in (b) e (c), ordinamento immediato delle chiavi e ricercaproporzianale al logaritmo si “pagano” rispetto ad altre strutture dati, in fase digenerazione e mantenimento dell’equilibrio dell’albero.

Nella sintesi finale cercheremo di completare una tabella di confronto tra tutte lestrutture dati trattate introducendo anche il concetto di efficienza e velocità diuna struttura dati rispetto alle operazioni di Inserimento di un Nodo,Cancellazione di un Nodo, Ricerca di Un Nodo, Ordinamento delle chiavi eaccesso alla struttura.

11.6.2 La Classe TreeSet

L’ADT Albero binario e le sue Operazioni: Costruttore/i Aggiunta di un oggetto Cancellazione di un oggetto Ricerca dell’esistenza di un Oggetto Operatore per stabilire se l’albero è vuoto Modalità di visita completa dei nodi

Esaminiamo la Classe TreeSet. La prima annotazione da fare è che si trattaancora di una struttura di tipo Set che ne implementa l’interfaccia come HashSetinfatti come questo ammette solo chiavi non ripetute e quindi è ancora un Set.

Classe TreeSetIdentificatori: TreeSet();

TreeSet(Collection c);Invocazione: TreeSet A = new TreeSet();

Costruttori

Effetti: Nel primo caso Crea un oggetto TreeSetidentificato da A vuoto.

Metodi Identificatore boolean add(Object);void clear();boolean contain(Objects);boolean isEmpty();boolean remove(Objects);Iterator iterator()


Pckage eGerarchia

java.util java.Object java.util.AbstractCollection java.util.TreeSet

esempio 11. “generare l’albero di Integer di figura (C) inserendo i numeri in ordinecasuale e stamparlo con e senza Iterator”Richiesta: realizzare il solo main().


public static void main(String args[]) {TreeSet A=new TreeSet();A.add(new Integer(99));A.add(new Integer(20));A.add(new Integer(36));A.add(new Integer(38));A.add(new Integer(33));Iterator it=A.iterator();System.out.println("Albero A="+A);// usa toString()predefinitowhile (it.hasNext())

System.out.println(it.next()); // Ciclo con Iterator}

}

Output:Albero a=[20, 33, 36, 38, 99]2033363899

Per verificare che la ricerca di un elemento in un albero bilanciato è più rapidarispetto ad una lista, mentre la generazione è più lenta realizzeremo dueprogrammi per confrontare le due strutture.esempio 12. “Si vuole realizzare un programma che confronti la velocità di ricercadi una chiave in un albero rispetto ad una lista di Double di grandi dimensioni”Indicazioni: Generare prima un albero e una lista di 70.000 Double con unafunzione random() e testare il tempo di ricerca, generare ancora un albero e unalista di 700.000 double e testare ancora il tempo di ricerca di una chiave.Richieste:Il main() dopo la generazione delle due strutture dati deve chiamare la funzionecontains(Double) con la stessa chiave e rilevare il tempo di inizio e fine dellachiamata stampando il tempo trascorso.


public static TreeSet Genera_tree(long N) {TreeSet A=new TreeSet();long i=0;Double NUM=null;


double num=0;while (i<N) {

num=(Math.random()*2*N);NUM=new Double(num);if (A.add(NUM)) i++;}

return A;}

public static LinkedList Genera_list(long N) {LinkedList A=new LinkedList();long i=0;Double NUM=null;double num=0;while (i<N) {


return A;}

public static void main(String args[]) {TreeSet A=Genera_tree(70000);LinkedList L=Genera_list(70000);// Chiave da cercareDouble Key=new Double((70000/2)*0.33333);

long t=System.currentTimeMillis();A.contains(Key);long tf=System.currentTimeMillis();t=tf-t;long s=System.currentTimeMillis();L.contains(Key);long sf=System.currentTimeMillis();s=sf-s;System.out.println("N=70.000\nRicerca Albero ="+t+" Lista="+s);

A=Genera_tree(700000);L=Genera_list(700000);// Chiave da cercareKey=new Double((700000/2)*0.33333);

t=System.currentTimeMillis();A.contains(Key);tf=System.currentTimeMillis();t=tf-t;s=System.currentTimeMillis();L.contains(Key);sf=System.currentTimeMillis();s=sf-s;System.out.println("N=700.000\nRicerca Albero ="+t+" Lista="+s);}

}

Output:N Albero Lista

70.000 0 ms (*) Circa 40 ms (**)700.000 0 ms (*) Circa 360 ms(**)


(*) il tempo di ricerca nell’albero è sempre inferiore al millisecondo e non èpossibile rilevare tempi inferiori.(**) i tempi possono variare a seconda del computer utilizzati e della sua velocitàin ogni caso il rapporto è circa 10/1 nei due casi.

esempio 13. “Si vuole realizzare un programma che confronti la velocità digenerazione di in un albero rispetto ad una lista di Double di grandi dimensioni”Indicazioni: Generare prima un albero e una lista di 70.000 Double con unafunzione random() e testare il tempo impiegato, generare ancora un albero e unalista di 700.000 double e testare ancora il tempo di generazione.Richieste:Il main() deve rilevare il tempo necessario per la generazione delle due strutturedati rilevando il tempo di inizio e fine della chiamata e stampando il tempotrascorso.


public static TreeSet Genera_tree(long N) {TreeSet A=new TreeSet();long i=0;Double NUM=null;double num=0;while (i<N) {


return A;}

public static LinkedList Genera_list(long N) {LinkedList A=new LinkedList();long i=0;Double NUM=null;double num=0;while (i<N) {


return A;}

public static void main(String args[]) {// 70.000long t=System.currentTimeMillis();TreeSet A=Genera_tree(70000);long tf=System.currentTimeMillis();t=tf-t;long s=System.currentTimeMillis();LinkedList L=Genera_list(70000);long sf=System.currentTimeMillis();s=sf-s;System.out.println("N=70.000\nGenerazione Albero ="+t+" Lista="+s);// 700.000t=System.currentTimeMillis();A=Genera_tree(700000);


tf=System.currentTimeMillis();t=tf-t;s=System.currentTimeMillis();L=Genera_list(700000);sf=System.currentTimeMillis();s=sf-s;System.out.println("N=700.000\nGenerazione Albero ="+t+" Lista="+s);}

}

Output:N Albero Lista

70.000 Circa 550 ms Circa 500 ms700.000 Circa 9200 ms Circa 6600 ms

Anche in questo caso si nota che il rapporto tra i tempi di generazione della lista ècirca 10/1, nell’albero tale rapporto tende ad aumentare fino a 20/1 a causa delmaggior tempo necessario per riequilibrare un albero via via crescente.

Date post:	15-Feb-2019
Category:	Documents
Upload:	ngohanh
View:	215 times
Download:	0 times

11. Strutture dati - copernico.bo.it · In Java le strutture dati di utilità sono contenute nel...

Documents