Corso JAVA
Lezione n° 11
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Le Strutture Dati
Per struttura dati, in informatica si intende una struttura logica atta a contenere un certo numero
di dati, nella quale è possibile inserire dati, toglierli, cercarli, ecc. Una semplice struttura
dati l’abbiamo gia vista: l'array.
Esso contiene un certo numero di dati che possono essere qualsiasi cosa, da byte ad oggetti
complessi; si possono fare inserzioni, ricerche, cancellazioni e, come abbiamo potuto
vedere anche in uno dei nostri esercizi delle lezioni scorse, volendo può anche essere
ordinato.
Per vedere se in un array grande N è presente un dato X, occorre visitare tutto l'array e fare dei
confronti con ogni elemento dell'array, capite bene che questa è una operazione abbastanza
complessa in termini di n° di operazioni.
Esistono delle strutture dati che questa ricerca la fanno impiegando un solo accesso alla
struttura, ad esempio le tabelle hash.
La scelta delle strutture dati da usare in un programma è una scelta abbastanza complicata,
infatti si sceglie una struttura anziché un'altra in base all'uso che ne deve essere fatto nel
programma, ad esempio è difficile che in un database molto grande in cui si fanno continue
ricerche si usi un array come struttura dati, perché ogni ricerca costerà tanto in termini di
tempo.
2
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Le Strutture Dati (2)
Ovviamente non considerate il caso in cui il numero di elementi da controllare siano poche
decine o qualche centinaia, in quel caso l’incidenza delle strutture dati e minimo;
considerate il caso in cui gli elementi siano in un numero pari a qualche miliardo di
elementi, in cui un singolo accesso in memoria realizzato grazie ad una tabella hash, deve
essere paragonato a qualche miliardo di accessi per fare confronti, in un array tradizionale.
Java mette a disposizione degli utenti tutta una gamma di strutture dati che è in grado di gestire
autonomamente, lasciando all’utente il solo compito di usarle.
Per la scelta della struttura dati più consona al nostro scopo, useremo il buon senso, perché per
sceglierla in modo rigoroso occorrono delle conoscenze molto specifiche, tra cui i dettagli
realizzativi delle strutture, studiate in corsi universitari quali Algoritmi e Strutture Dati , e
Fondamenti di Complessità.
In questa lezione vedremo brevemente quali sono le classi che Java mette a disposizioni per
implementare queste strutture dati e se necessario verranno fatti degli accenni riguardo i
tempi di inserzioni, ricerche, eccetera..., ma sempre evitando di entrare in discussioni
troppo formali che vi risulterebbero forse incomprensibili.
3
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
BitSet
La prima struttura dati che vediamo oggi è il BITSET.
La classe java.util.BitSet implementa vettori di bit che aumentano se necessario. Ogni
componente del BitSet è individuato da un intero non negativo ed è associato ad un valore
booleano, memorizzato in un bit, a cui si può accedere individualmente.
Una volta che abbiano istanziato un oggetto Bitset, viene creato un insieme di bit lungo 2 32-1e
tutti questi bit sono settati a false.
I metodi più comuni che si utilizzano su di un oggetto Bitset sono i seguenti:

void set(int i);

void clear(int i);
che rispettivamente pongono a true o a false il bit di indice i.
 void set(int i, int j);

void clear(int i, int j);
che rispettivamente pongono a true o a false i bit tra l'indice i compreso e l’indice j escluso.
4
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
BitSet (2)
boolean get(int i);
che restituisce il valore del bit di indice i.

int nextSetBit(int i);
che restituisce il valore dell'indice del primo bit true dopo quello di indice i-1.

int length();
che restituisce la grandezza logica del Bitset, ovvero il bit più alto settato a true, più uno.

int size();
che restituisce il numero di bit attuali del Bitset, è il bit più alto che può essere posto a uno
senza ampliare il Bitset.

cardinality()
che restituisce il numero di bit settati a true nel Bitset.

String toString(),
che trasforma la Bitset in una stringa.

5
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Esempio di utilizzo di BitSet
Vediamo adesso un semplice programma che fa uso di un BitSet: il problema del crivello di
Eratostene.
Il crivello di Eratostene è un antico procedimento per il calcolo delle tabelle di numeri primi
fino ad un certo numero n prefissato. Esso deve il nome al matematico Eratostene di
Cirene, che ne fu l'ideatore, ed è a tutt'oggi utilizzato come algoritmo di calcolo dei numeri
primi da molti programmi per computer; pur non essendo un algoritmo straordinariamente
efficiente, infatti, è in compenso piuttosto semplice da tradurre in un qualsiasi linguaggio
di programmazione.
Il procedimento è il seguente:

Si scrivono tutti i naturali a partire da 2 fino n in un elenco detto setaccio.

Poi si cancellano (setacciano) tutti i multipli del primo numero del setaccio (escluso lui
stesso).

Si prosegue così fino ad arrivare in fondo.

I numeri che restano sono i numeri primi minori od uguali a n.
È come se si utilizzassero dei setacci a maglie via via più larghe: il primo lascia passare solo i
multipli di 2, il secondo solo i multipli di 3, e così via.
6
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Esempio di utilizzo di BitSet
/** * Calcola il numero di primi minori di n */
import java.util.Bitset;
int Crivello_Erastotene(int n)
{
BitSet primi = new BitSet(n);
primi.set(2,n);
int i=1;
while (i*2<n) {
i = primi.nextSetBit(i+1);
for(int k=i*2; k<n; k+=i)
primi.clear(k);
}
return primi.cardinality();
}
7
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Vector
Prima di introdurre questa struttura dati vediamo quali sono gli svantaggi degli array, ovvero
della struttura dati che più si avvicina ad un vector, che ci permetterà quindi di apprezzare i
vantaggi dell’utilizzo dei vector.
Il grosso difetto di fondo di un array è che bisogna conoscere a priori il numero massimo di dati
da inserire.
Se, per esempio, dobbiamo gestire un archivio destinato a crescere nel tempo è del tutto
inefficiente poiché potremmo trovarci un giorno a dover correggere direttamente il codice.
Oltre a questo problema l'array ha anche degli altri aspetti negativi relativi all'utilizzo della
memoria di cui non ci occuperemo sia perché esulano dai nostri scopi sia perché nei PC
moderni che dispongono di grosse quantità di memoria non siamo mai portati ad
occuparcene.
Vi basti sapere che l'array è la struttura dati indicata se il numero dei dati è conosciuto a priori
(oppure è conosciuto il loro massimo valore, ad esempio nella gestione dell'anagrafica di
una piccola azienda si può tranquillamente stimare un valore per eccesso) ed è
relativamente basso.
8
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Vector (2)
Per ovviare agli inconvenienti visti prima, la teoria delle strutture dati ci offre varie alternative,
una delle quali è implementata in Java tramite la classe Vector che offre, rispetto all'array, i
seguenti vantaggi:

La sua dimensione può variare dinamicamente

E' possibile inserire e cancellare elementi in qualunque posizione senza lasciare "buchi"
tramite l'invocazione di opportuni metodi

Gli elementi del vector possono essere anche disomogenei.
Per quanto riguarda l'efficienza del vector è doveroso precisare che esso è meno performante
dell'array se vengono effettuate ripetute operazioni di inserimento e cancellazione e che il
suo utilizzo deve essere limitato a insiemi non eccessivamente numerosi, per i quali è
necessario usare strutture dati complesse o, nei casi estremi, una base di dati.
N.B.: I Vector possono contenere solamente oggetti, no tipi fondamentali.
9
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Vector (3)
L'implementazione dei vettori è basata sugli array.
Al momento della creazione di un vettore, viene utilizzato un array di dimensioni
predefinite; successivamente, se la capacità dell'array non è più sufficiente, viene
creato un nuovo array più grande nel quale vengono copiati tutti gli elementi del
vecchio.
I principali costruttori di un vector sono 3:
 Vector (), che costruisce un vettore grande 10, e con possibilità di incremento
pari a zero.
 Vector (int Capacità_Iniziale), costruisce un vettore grande quando
Capacità_Iniziale, con possibilità di Incremento_Capacità pari a zero.
 Vector (int Capacità_Iniziale, int Incremento_Capacità), costruisce un vettore
grande Capacità_Iniziale, con la possibilità di incremento pari a
Incremento_Capacità.
10
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Vector (4)
I metodi più comuni che si utilizzano su di un oggetto Vector sono i seguenti:

int capacity ();
che restituisce la capacita' del vettore.

int size ();
che restituisce il numero di elementi contenuti nel vettore.

Object elementAt (int index);
che restituisce l'elemento di indice index.

void setElementAt (Object obj, int index);
che sostituisce l’oggetto obj all'oggetto della posizione index.

void insertElementAt (Object obj, int index);
che inserisce l’oggetto obj nella posizione index e sposta tutti gli elementi, da index in poi, di
una posizione.

void addElement (Object obj);
che aggiunge l’oggetto obj dopo l'ultimo elemento.
11
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Vector (5)
void removeElementAt (int index);
che rimuove l'oggetto presente nella posizione index e sposta all’indietro di una posizione tutti
gli elementi successivi a quello rimosso.

boolean removeElement (Object obj);
che rimuove l’oggetto obj se presente restituendo true, altrimenti restituisce false.

int indexOf (Object elemento);
che cerca la prima occorrenza del dato elemento nel vettore, e ne restituisce l'indice. Nel caso
in cui l’elemento non sia presente nel vettore restituisce –1.

boolean isEmpty(),
che restituisce true se il vettore è vuoto, false altrimenti.

Object lastElement(),
che restituisce l’ultimo elemento del vettore.

12
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Vector VS. Array
Array
13
Vector
// Nessun pacchetto richiesto
import java.util.Vector;
String[] elenco = new String[5];
Vector elenco = new Vector(5);
for (int i=0 ; i<elenco.length ; i++) {
{ elenco[i] = "Numero "+i; }
for (int i=0 ; i<elenco.capacity() ; i++)
{ elenco.addElement("Numero "+i); }
System.out.println(elenco[2]);
System.out.println(elenco.elementAt(2));
for (int i=0 ; i<elenco.length ; i++)
{ System.out.println(elenco[i]); }
for (int i=0 ; i<elenco.size() ; i++)
{System.out.println(elenco.elementAt(i));}
elenco[2] = "Mario Rossi";
elenco.setElementAt("Mario Rossi",2);
for (int i=elenco.length-1 ; i>2 ; i--)
{ elenco[i] = elenco[i-1]; }
elenco[2] = "Mario Verdi";
elenco.insertElementAt("Mario Verdi",2);
for (int i=3 ; i<elenco.length ; i++)
{ elenco[i-1] = elenco[i]; }
elenco[elenco.length-1] = null;
elenco.removeElementAt(2);
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Tipi primitivi in un vettore
I numeri in Java sappiamo che non sono oggetti, quindi non è possibile inserirli direttamente in
un vettore; Per memorizzare una sequenza di numeri interi, numeri in virgola mobile, o
valori di tipo boolean in un vettore, si devono usare le classi involucro.
Le istanze di queste classi sono usate per incapsulare valori primitivi all'interno di un oggetto.
Questo ci permette di trattare in maniera omogenea tipi primitivi ed oggetti. Gli oggetti
involucro possono naturalmente essere inseriti in un vettore.
Ci sono classi involucro per tutti i tipi primitivi. Normalmente hanno un nome simile al
corrispondente tipo primitivo, ma iniziano con maiuscola:
Bignum, Boolean, Byte, Character, Double, Float, Integer, Long, Number, Short
Ciascuna di queste classi ha (oltre ai soliti metodi toString e equals):

un costruttore con parametro di tipo primitivo (ad esempio Character(char c) o
Integer(int value));

un costruttore con parametro String (ad esempio Integer(String s));

un metodo <tipo>Value che produce il valore di tipo primitivo corrispondente (ad esempio
intValue());
14
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Esempio: La classe Integer
La classe Integer è la classe involucro per numeri interi.
Ha un costruttore che crea un oggetto di tipo Integer a partire da un valore di tipo int:
Integer numero = new Integer(30);
Viceversa, il metodo intValue restituisce il valore di tipo int memorizzato nell'oggetto di tipo Integer:
int n = numero.intValue();
Ecco come si può aggiungere un numero intero a un vettore:
Vector dati = new Vector();
// Istanzio un vettore;
int n = 30;
Integer numero = new Integer(n); //Istanzio un oggetto Integer inserendo all’interno il ns. intero (30)
dati.addElement(numero);
//Aggiungo l’oggetto Integer appena istanziato al Vector dati
Per recuperare il numero, si deve convertire con un cast il riferimento restituito dal metodo elementAt in
modo da ottenere un oggetto di tipo Integer (il metodo restituisce un Object), per poi invocare il metodo
intValue:
Integer numero = (Integer)dati.elementAt(0);
int n = numero.intValue();
15
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
La Pila - Stack
La pila (stack) è una struttura dati astratta molto semplice, ma dal diffuso impiego.
Intuitivamente, una pila è un sequenza di zero o più elementi in cui è possibile
aggiungere o togliere elementi soltanto ad un estremo della sequenza detto cima
(top) della pila.
Politica di accesso:
LIFO (Last In, First Out)
[ultimo elemento inserito, primo elemento rimosso]
Di solito una pila viene rappresentata graficamente come una sequenza verticale di
"caselle" contenenti i suoi elementi. La casella più in alto è la cima (top).
C
<A, B, C>
B
A
pila di tre elementi vista come sequenza e sua rappresentazione grafica
16
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Operazioni su di uno Stack
Le operazioni definite su una pila sono le seguenti:
 Inserimento di un elemento in cima alla pila (normalmente chiamata push)
 Estrazione dell'elemento in cima alla pila (chiamata pop)
 Lettura dell'elemento in cima alla pila, senza eliminarlo (chiamata top o peek)
 Controllo se la pila è vuota oppure no (predicato isEmpty)
 Svuotamento della pila (chiamata clear)
Abbiamo detto che lo Stack è una struttura dati astratta, questo perché è possibile
utilizzare diverse strutture dati, facendole funzionare come una pila.
Abbiamo detto che Stack è una struttura dati astratta, ma capite bene che, per il
motivo precedente Stack è più propriamente una interfaccia!
17
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Interfaccia Stack
Quindi se vogliamo utilizzare una struttura dati secondo i concetti della pila, dobbiamo
implementare con quella struttura dati la seguente interfaccia:
public interface Stack
Specifica dei metodi per la gestione della pila, con riferimento alle classi di Java Collections
API disponibili in java.util.*.
******************* METODI PUBBLICI **********************
Object push( Object x);
//Inserisce x in cima alla pila
Object pop( );
//Estrae dalla cima della pila
Object peek( );
//Restituisce l'elemento in cima
boolean isEmpty( );
//Verifica se la pila e' vuota
void clear( );
//Svuota la pila
****************** ECCEZIONI ******************************
pop e peek generano java.util.EmptyStackException con pila vuota .
18
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
La Coda - Queue
Una coda (queue) è un sequenza di zero o più elementi in cui è possibile aggiungere elementi
soltanto ad un estremo della sequenza, detto fondo (back), ed è possibile toglierli soltanto
dall'altro estremo, detto testa (front).
Politica di accesso:
FIFO (First In, First Out)
[primo elemento inserito, primo elemento rimosso]
Rappresentiamo una coda come una sequenza di caselle contenenti i suoi elementi, nell'ordine
in cui sono stati inseriti. La casella più a sinistra è la testa (front), quella più a destra è il
fondo (back).
<A, B, C, D, E>
A B C D E
front
back
coda di cinque elementi vista come sequenza e sua rappresentazione grafica
19
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Operazioni su di una Queue
Le operazioni definite su una coda sono le seguenti :
 Inserimento di un elemento in fondo alla coda (chiamata enqueue)
 Estrazione dell'elemento in testa alla coda (chiamata dequeue)
 Lettura dell'elemento in testa alla coda, senza eliminarlo (chiamata front)
 Controllo se la coda è vuota oppure no (predicato isEmpty)
 Svuotamento della coda (chiamata clear)
Si noti che pile e code hanno essenzialmente le stesse operazioni,
ma con significato (e quindi nome) diverso!
Ovviamente anche la Coda è un’interfaccia!
20
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Interfaccia Queue
Quindi se vogliamo utilizzare una struttura dati secondo i concetti della pila, dobbiamo
implementare con quella struttura dati la seguente interfaccia:
public interface Queue
Specifica dei metodi per la gestione della coda, per analogia con la classe Stack di Java
Collections API disponibile in java.util.*.
********************* METODI PUBBLICI ***********************
Object enqueue( Object x);
//Inserisce x in fondo alla coda
Object dequeue( );
//Estrae dalla testa della coda
Object front( );
//Restituisce l'elemento in testa
boolean isEmpty( );
//Verifica se la coda e' vuota
void clear( );
//Svuota la coda
******************** ECCEZIONI ******************************
dequeue e front generano EmptyQueueException con coda vuota
21
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Implementazione dell’interfaccia
Stack con Vector - VectorStack
import java.util.Vector;
import java.util.EmptyStackException;
public class VectorStack implements Stack
{
protected Vector theVector;
public VectorStack( )
//Costruttore dello Stack
{
theVector = new Vector( );
}
public Object push( Object x )
{
if ( x == null ) throw new IllegalArgumentException( );
theVector.addElement( x );
return x;
}
22
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
Implementazione dell’interfaccia
Stack con Vector - VectorStack (2)
public Object pop( )
{
if ( isEmpty( ) ) throw new EmptyStackException( );
return theVector.removeElementAt( theVector.size( )-1 );
}
public Object peek( )
{
if ( isEmpty( ) ) throw new EmptyStackException( );
return theVector.get(theVector.size( )-1 );
}
public boolean isEmpty( )
{
return theVector.isEmpty( );
public void clear( )
{
theVector.clear( );
23
}
Istituto Statale di Istruzione Superiore “F. Enriques”
}
Corso di Programmazione in Java – Lezione n° 11
HashTable
Prima di terminare la lezione faremo un accenno anche ad un’altra struttura dati: le tabelle hash.
Una tabella hash è un insieme di coppie < chiave, valore >; tramite la chiave ed una funzione hash è possibile
recuperare il valore associato alla chiave, in particolare si recupera l’indirizzo di memoria dove il valore
ha inizio.
Ovviamente una funzione hash è una funzione univoca che associa ad ogni chiave un solo valore.
Come per i Vector anche in questo caso sia la chiave che il valore associato devono essere oggetti, pertanto
valgono le stesse considerazioni che sono state fatte per i vector.
La principale caratteristica
dell’Hashtable consiste nel fatto che
l’accesso alle informazioni una volta
ottenuta la chiave è molto veloce,
rispetto ad un Vector.
Ovviamente ogni struttura dati ha i
propri vantaggi e i propri svantaggi.
24
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
HashTable (2)
metodi più importanti implementati da Hashtable sono:

hashtable.size()
che restituisce un intero contenente il numero di elementi inseriti in hashtable;

hashtable.isEmpty ():
che restituisce un valore booleano che indica se l’hashtable è vuota o meno (il valore true
segnala che l’hashtable è vuota);

hashtable.get (Object key):
che restituisce l'oggetto a cui è associata la chiave key, se la chiave non viene trovata restituisce
null;

hashtable.put (Object key, Object elem):
che inserisce nell’hashtable l'elemento elem e gli associa la chiave key, se chiave è già stata
inserita viene sostituito l'oggetto a lei associato e viene restituito, altrimenti viene restituito
null;
25
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
HashTable (3)
metodi più importanti implementati da Hashtable sono:
 hashtable.remove (Object key)):
che rimuove da hashtable l'elemento associato a key, se la chiave non esiste viene
restituito null.
Ad un oggetto di tipo Hashtable può venire associato un oggetto di tipo
Enumeration, che permette di scorrere la collezione di oggetti, utilizzando i
metodi:
enumeration.hasMoreElements ():
che restituisce il valore booleano true se ci sono ancora elementi da scorrere;
enumeration.nextElement():
che si sposta all'elemento successivo.
•
•
26
Istituto Statale di Istruzione Superiore “F. Enriques”
Corso di Programmazione in Java – Lezione n° 11
In Conclusione
In questa lezione abbiamo visto alcune strutture dati, ed alcune interfacce che
permettono di modificare il comportamento di tali strutture dati.
Ovviamente ne esistono molte altre: Liste, Liste a doppia concatenazione, Alberi,
ecc. e capite bene che descriverle tutte sarebbe un lavoraccio.
La cosa che vi deve interessare è che tutte, + o -, hanno metodi per inserire, togliere,
recuperare le informazioni contenute e metodi per gestire la struttura stessa.
Ogni volta che si deve scegliere una struttura dati se ne devono valutare i vantaggi e
gli svantaggi e capire quali influiranno maggiormente nella nostra applicazione;
ovviamente è possibile recuperare tutte le informazioni che servono consultando
la documentazione del Java Development Kit, dove sono descritte tutte queste
classi.
Per il resto del nostro corso sarà sufficiente conoscere le strutture dati che abbiamo
visto in questa lezione.
27
Istituto Statale di Istruzione Superiore “F. Enriques”