Strutture dati: array & co. Programmazione in Rete e Laboratorio

(1)

1

Strutture dati: array & co.

Programmazione in Rete e Laboratorio

Matteo Baldoni Dipartimento di Informatica Universita` degli Studi di Torino C.so Svizzera, 185 I-10149 Torino baldoni@di.unito.it

http://www.di.unito.it/~baldoni/didattica

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

3

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

5

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[] altroArrayOfInt;

[…]

altroArrayOfInt = arrayOfInt;

[…]

System.out.println(arrayOfInt.length); ^{stampa 6} arrayOfInt

altroArrayOfInt

6

Array

Contatore cont[];

cont

(2)

2

7

Array

cont = new Contatore[3];

cont

8

Array

cont = new Contatore[3];

cont[0] = new Contatore(10);

cont contatore

10

9

Inizializzazione di array

■

Mediante un loop (tipicamente un ciclo for)

■

oppure durante la definizione stessa

■

array anonimi come parametri attuali

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

11

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!

(3)

3

13

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 ₁₄

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

15

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)

17

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

(4)

4

19

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);

}

} ₂₀

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

21

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

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

23

Iteratori

■

È un oggetto che permette di attraversare agevolmente una struttura dati qualsiasi (indipendentemente dalla sua implementazione)

■

nest(), hasNext(), remove()

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();

} }