Strutture dati: array & co.
Fondamenti di programmazione Java
Matteo Baldoni
Dipartimento di Informatica
Universita` degli Studi di Torino C.so Svizzera, 185 I-10149 Torino [email protected]
2
Array
■ Gli array sono oggetti veri e propri (e quindi vanno prima creati esplicitamente dal programmatore per essere
utilizzati)
■ Hanno una dimensione fissa (dopo la creazione)
■ Esistono solo unidimensionali (ma e` possibile definire array di array)
■ Il primo elemento ha indice “0”
■ La creazione avviene mediante l’operatore new
Array
■ Es.: la dichiarazione di un array che puo` contenere 100 numeri interi
■ Gli elementi saranno indicizzati da 0 a 99
■ L'interprete controlla che gli indici siano sempre
nell'intervallo specificato al momento della creazione
int[] arrayOfInt = new int[100];
operatore che permette di
creare un oggetto
numero di elementi dell’array nome dell’array
tipo di un elemento dell’array
tipo array
arrayOfInt[5]
indice
4
Array
■ Il nome dell’array e` un puntatore ad una struttura contenente i vari elementi
■ ma differenza del C/C++ il nome dell’array non indica anche il primo elemento dell’array stesso (non esiste un’aritmetica dei puntatori)
■ In Java non esistono analoghi di & e * del C/C++
int array_interi[];
int *array_interi;
array_interi[2]
*(array_interi + 2)
in C/C++ sono equivalenti
in C/C++ sono equivalenti
Array
■ Se assegno un array ad un altro non copio gli elementi che esso contiene ma semplicemente il valore del
puntatore, i due array condivideranno la stessa struttura (esiste pero` arraycopy nella classe System)
■ length (campo read-only) restituisce la lunghezza di un array
int[] arrayOfInt = new int[6];
[…]
int[] altroArrayOfInt;
[…]
altroArrayOfInt = arrayOfInt;
[…] stampa 6
arrayOfInt
altroArrayOfInt
6
Array
Contatore cont[];
cont
Array
Contatore cont[];
cont = new Contatore[3];
cont
8
Array
Contatore cont[];
cont = new Contatore[3];
cont[0] = new Contatore(10);
cont contatore
10
Inizializzazione di array
■ Mediante un loop (tipicamente un ciclo for)
■ oppure durante la definizione stessa
■ array anonimi come parametri attuali
int[] arrayOfInt = new int[100];
for (int i=0; i<100; i++) arrayOfInt[i] = i;
int[] arrayOfInt = {1, 2, 4, 10}; utile per array con pochi elementi
new int[] {1, 2, 4, 10} utile per essere passato come parametro attuale di un metodo senza dover creare solo per questo una variabile
[…]
a.metodo(new int[] {1, 2, 4, 10});
10
Array multidimensionali
■ Ossia array di array (ma non matrici!)
■ Ossia un elemento di un array puo` essere a sua volta un array
int[][] arrayOfArrayOfInt = new int[10][5];
int[][] arrayOfArrayOfInt = new int[10][];
for (int i=0; i<10; i++)
arrayOfArrayOfInt[i] = new int[5];
int[][] arrayOfArrayOfInt = new int[10][];
for (int i=0; i<10; i++)
arrayOfArrayOfInt[i] = new int[i];
quadrato di
elementi 10 x 5
triangolo di elementi
Array
■ Gli array sono oggetti di “prima classe”
■ Gli array sono built-in nel linguaggio
■ L’operatore [] e`un costruttore di tipo!
public class Counter { private int c;
[…]
}
Counter[] arrayOfCounters = new Counter[10];
Definisce il tipo Counter
Definisce il tipo array di Counter
12
Array
class ProvaArray { public static void
main(String[] args) { ClasseUno[] arrayClasseUno;
ClasseDue[] arrayClasseDue;
ClasseTre[] arrayClasseTre;
ClasseDue[] arrayClasseDueBis;
arrayClasseDue = new ClasseDue[]
{new ClasseDue(2,3), new ClasseDue(3,4)};
arrayClasseUno = arrayClasseDue;
arrayClasseDueBis =
(ClasseDue[]) arrayClasseUno;
arrayClasseTre = new ClasseTre[]
{new ClasseTre("ab"), new ClasseTre("cd")};
arrayClasseUno = arrayClasseTre;
...
} Upcast di tutti gli elementi
Downcast di tutti gli elementi Errore!
Array
class ProvaArray { public static void
main(String[] args) { ClasseUno[] arrayClasseUno;
ClasseDue[] arrayClasseDue;
...
arrayClasseDue = new ClasseDue[]
{new ClasseDue(2,3), new ClasseDue(3,4)};
...
arrayClasseUno = arrayClasseDue;
...
arrayClasseUno[0] = new ClasseUno(2);
}
Errore a run-time!!
A tempo di compilazione è corretto
assegnare ad un campo dell’array di tipo ClasseUno un elemento di tipo ClasseUno ma a run-time questo contiene un elemento di tipo ClasseDue,
14
La classe java.util.Arrays
■ Mette a disposizione una serie di metodi statici di utilita` per trattare con array:
◆ equals
◆ fill
◆ sort
◆ binarySearch
■ I metodi sono overloaded per ogni tipo primitivo e per Object.
Fa uso di equals e non di ==
Fa uso di compareTo
dell’interfaccia Comparable per parametrizzare l’algoritmo di
ordinamento rispetto gli elementi Permette di usare anche oggetti
di tipo Comparator (interfaccia) per parametrizzare rispetto al confronto
Strutture dati: Interfacce
■ Collection: un arbitraio gruppo di oggetti
■ List: un gruppo di oggetti memorizzati in una data sequenza
■ Set: un gruppo di oggetti senza duplicati
■ Map: un gruppo di coppie
(oggetti) chiave-valore Sono tutte interfacce!
16
Strutture dati: Implementazioni
■ Ogni interfaccia ha piu` implementazioni che possono essere scelte in modo indifferente a seconda delle esigenze (anche di efficienza)
Strutture dati
■ Tassonomia completa delle strutture dati disponibili nel package java.util
■ Si noti Vector
ancora consentito sebbene gli venga ora preferito
ArrayList
18
Strutture dati
■ Gli oggetti che possono essere contenuti in una qualsiasi struttura dati sono di tipo Object, quindi un oggetto
qualsiasi
■ Un oggetto di tipo, ad esempio, ArrayList puo` contenere oggetti di tipo diverso, anche non omogenei (perche`
comunque di tipo Object)
■ Viene persa l’informazione sul tipo di un oggetto quando è inserito in una struttura dati di questo genere (è come fare upcasting ad Object!)
■ Estratti gli oggetti è necessario fare downcasting per poterli riutilizzare correttamente (invocare metodi della loro classe di appartenenza), in contrapposizione agli array
Un esempio
■ Tratto da: B. Eckel, Thinking in Java, Prentice Hall, 2000.
Cap. 9, pag. 450 e seguenti.
public class Cat {
private int catNumber;
Cat(int i) { catNumber = i; } void print() {
System.out.println("Cat #" + catNumber);
} }
public class Dog {
private int dogNumber;
Dog(int i) { dogNumber = i; } void print() {
System.out.println("Dog #" + dogNumber);
20
Un esempio
import java.util.*;
public class CatsAndDogs {
public static void main(String[] args) { ArrayList cats = new ArrayList();
for(int i = 0; i < 7; i++) cats.add(new Cat(i));
cats.add(new Dog(7));
for(int i = 0; i < cats.size(); i++) ((Cat)cats.get(i)).print();
} }
ArrayList non ha nessun
riferimento a cosa conterra`
in seguito!
Posso benissimo aggiungere un oggetto di tipo Dog in cats!
Durante la compilazione non viene rilevato nessun errore ma durante l’esecuzione (run-time) verra` sollevata un’eccezione (ClassCastException) poiche` verra` trovato un elemento non di tipo Cat (il downcast non è un cast alla C ma sono una
verifica che l’oggetto sia effettivamente di un certo tipo) Senza downcast non potrei invocarlo
Un esempio
public class Cat1 {
private int catNumber;
Cat(int i) { catNumber = i; } public String toString() { return "Cat #" + catNumber;
} }
public class Dog1 {
private int dogNumber;
Dog(int i) { dogNumber = i; } public String toString() { return "Dog #" + dogNumber;
} }
A differenza di prima abbiamo un metodo
toString() per stampare
22
Un esempio
import java.util.*;
public class CatsAndDogs {
public static void main(String[] args) { ArrayList cats = new ArrayList();
for(int i = 0; i < 7; i++) cats.add(new Cat1(i));
cats.add(new Dog1(7));
for(int i = 0; i < cats.size(); i++) //((Cat)cats.get(i)).print();
System.out.println(cats.get(i).toString());
} }
Non viene sollevata nessuna eccezione durante l’esecuzione!!
Tutto funziona perfettamente. Questo perche` abbiamo fatto overriding di un metodo appartenente alla classe Object e quindi sopraclasse sia di Cat1 che di Dog1. Il binding
dinamico associera` il corretto codice durante l’esecuzione
Posso aggiungere
un oggetto di tipo Dog Viene invocato
implicitamente non è necessario scriverlo
Durante la compilazione nessun errore poiche`
String toString() è un metodo disponibile in Object
Il metodo toString()
■ E` il metodo che viene automaticamente richiamato per la conversione di un oggetto in una stringa da stampare
■ Puo` essere ridefinito per adattarlo alle proprie esigenze
24
Il metodo toString()
public class Counter {
public Counter() {
nomeContatore = "Contatore anonimo";
}
public Counter(int val){
c = val;
nomeContatore = "Contatore anonimo";
}
public Counter(int val, String nome){
c = val;
nomeContatore = nome;
} […]
public void setName(String nome) { nomeContatore = nome;
}
public String toString(){
return ("Valore contatore " + nomeContatore + ": " + c);
}
private int c;
private String nomeContatore;
}
overriding dell’omonimo metodo nella classe Object
Un nome al contatore
Iteratori
■ È un oggetto che permette di attraversare agevolmente una struttura dati qualsiasi (indipendentemente dalla sua implementazione)
■ nest(), hasNext(), remove()
import java.util.*;
public class CatsAndDogs2 {
public static void main(String[] args) { Collection cats = new ArrayList();
for(int i = 0; i < 7; i++) cats.add(new Cat(i));
Iterator e = cats.iterator();
while(e.hasNext())
((Cat)e.next()).print();
