Strutture dati: array & co.
Laboratorio di Programmazione ad Oggeti
Matteo Baldoni
Dipartimento di Informatica Universita` degli Studi di Torino C.so Svizzera, 185 I-10149 Torino [email protected]
http://www.di.unito.it/~baldoni/didattica
Stringhe
■
La libreria standard fornisce una classe predefinita String
■
La classe String contiene numerosi metodi:
String s1 = "Buon";
String s2 = "giorno";
String saluto = s1 + s2;
String s = saluto.substring(0,4) //s ha valore "Buon"
int n = saluto.length() // n vale 10
La stringa saluto ha valore:
“Buongiorno”
Il + indica concatenazione
3
Stringhe
■
Le stringhe sono immutabili
■
Non ci sono metodi per cambiare un carattere in una stringa: occorre creare una nuova stringa
String s = "salve";
se vogliamo sostituire la e con una a String s = s.substring(0,4) + "a";
oppure
String s = "salva";
4
Uguaglianza di stringhe
s.equals(t) restituisce true se le due stringhe s e t sono uguali, false altrimenti
String s = "salve";
String t = "salve";
s.equals(t)
dà true
non va bene usare l'operatore ==
darebbe false perché i valori di s e t sono due oggetti diversi, anche se hanno lo stesso valore
s == t
5
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
7
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
8
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;
[…]
System.out.println(arrayOfInt.length); stampa 6 arrayOfInt
altroArrayOfInt
9
Array
Contatore cont[];
cont
Array
Contatore cont[];
cont = new Contatore[3];
cont
11
Array
Contatore cont[];
cont = new Contatore[3];
cont[0] = new Contatore(10);
cont contatore
10
12
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});
[…]
13
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
15
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!
16
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, piu` specifico di ClasseUno, e quindi viene sollevata un’eccezione di tipo ArrayStoreException
17
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!
19
Strutture dati: Implementazioni
■ Ogni interfaccia ha piu` implementazioni che possono essere scelte in modo indifferente a seconda delle esigenze (anche di efficienza)
20
Strutture dati
■ Tassonomia completa delle strutture dati disponibili nel package java.util
■ Si noti Vector ancora consentito sebbene gli venga ora preferito ArrayList
21
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);
} }
23
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
24
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
25
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
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();
} }
