Vettori e array
Anno Accademico 2003/04
Docente modulo 2: Barbara Masucci
Collezione di oggetti: Array List
„
Consideriamo la classe Purse
‰
non tiene traccia dei singoli oggetti di tipo Coin, ma
memorizza solo il valore totale
„
Possiamo memorizzare una collezione di oggetti
mediante la classe ArrayList
„
ArrayList coins = new ArrayList();
coins.add(new Coin(0.1, "dime"));
. . .
„
Il metodo size() restituisce il numero di elementi
della collezione
Linguaggi di Programmazione II
2003-04
2
1
Aggiungere un elemento ad una
collezione
„Per
aggiungere l’elemento alla fine della
collezione si usa il metodo add(obj):
ArrayList coins = new ArrayList ();
coins.add(new Coin(0.1, “dime”));
coins.add(new Coin(0.25, “quarter”);
„Dopo
l’inserimento, la dimensione della
collezione aumenta di uno
Linguaggi di Programmazione II
2003-04
3
Aggiungere un elemento ad una
collezione
„
„
Un ArrayList gestisce oggetti di tipo Object
Possiamo passare qualsiasi obj al metodo
add
ArrayList coins = new ArrayList();
coins.add(new Rectangle(5, 10, 20, 30));
//add non protesta
Coin aCoin = (Coin)coins.get(i);//ERRORE
//un Rectangle non può essere convertito in un Coin!
Linguaggi di Programmazione II
2003-04
4
2
Aggiungere un elemento ad una
collezione
„Per
aggiungere l’elemento in una certa
posizione, facendo slittare in avanti gli altri, si
usa il metodo add(i,obj):
ArrayList coins = new ArrayList ();
coins.add(new Coin(0.1, “dime”));
coins.add(new Coin(0.25, “quarter”);
Coin aNickel = new Coin(0.05, “nickel”);
coins.add(1, aNickel);
//quarter ora è il terzo oggetto della lista
Linguaggi di Programmazione II
2003-04
5
Linguaggi di Programmazione II
2003-04
6
Figura 1
Aggiungere
un elemento
in una posizione
intermedia
di un vettore
3
Rimuovere un elemento dalla
collezione
„
Per rimuovere un elemento da una collezione,
facendo slittare indietro gli altri, si usa il metodo
remove(indice);
ArrayList coins = new ArrayList ();
coins.add(new Coin(0.1, “dime”));
coins.add(new Coin(0.25, “quarter”);
Coin aNickel = new Coin(0.05, “nickel”);
coins.add(1, aNickel);
coins.remove(0);
//il vettore ora ha due elementi: quarter e
nickel
Linguaggi di Programmazione II
2003-04
7
Linguaggi di Programmazione II
2003-04
8
Figura 2
Rimuovere
un elemento
da una posizione
intermedia di un vettore
4
Accedere agli elementi di una
collezione
„
Bisogna usare il metodo get(indice)
‰
„
ArrayList memorizza Object, è necessario un
cast al tipo corretto
‰
„
coins.get(2);
Coin c = (Coin)coins.get(2);
L’indice di un vettore parte da zero
‰
Un errore comune
int n = coins.size();
c = (Coin)coins.get(n); // ERRORE
// gli indici variano da 0 a n-1!!
Linguaggi di Programmazione II
2003-04
9
Esaminare in sequenza gli elementi
di una collezione
„
Calcoliamo il valore totale delle monete nel
vettore
double total =0;
for (int i = 0; i < coins.size(); i++)
{
Coin c = (Coin)coins.get(i);
total = total + c.getValue();
}
Linguaggi di Programmazione II
2003-04
10
5
Modificare un elemento in una
collezione
„
Si usa il metodo set(indice,
obj):
ArrayList coins = new ArrayList();
coins.add(new Coin(0.1, "dime"));
coins.add(new Coin(0.25, “quarter”);
Coin aNickel = new Coin(0.05, “nickel”);
coins.set(0, aNickel);
//la posizione 0 viene sovrascritta
Linguaggi di Programmazione II
2003-04
11
File Purse.java
import java.util.ArrayList;
/**
Un borsellino contiene una raccolta di monete.
*/
public class Purse
{
/**
Costruisce un borsellino vuoto.
*/
public Purse()
{
coins = new ArrayList();
}
/**
Aggiunge una moneta al borsellino.
@param aCoin la moneta da aggiungere
*/
public void add(Coin aCoin)
{
coins.add(aCoin);
}
Linguaggi di Programmazione II
2003-04
12
6
/**
Ispeziona il valore totale delle monete
nel borsellino.
@return la somma dei valori di tutte le monete
*/
public double getTotal()
{
double total = 0;
for (int i = 0; i < coins.size(); i++)
{
Coin aCoin = (Coin)coins.get(i);
total = total + aCoin.getValue();
}
return total;
}
private ArrayList coins;
}
Linguaggi di Programmazione II
2003-04
13
Ricerca Lineare
public class Purse
{
public boolean find(Coin aCoin)
{
for (int i = 0; i < coins.size(); i++)
{
Coin c =(Coin)coins.get(i);
if (c.equals(aCoin)) return true;
//trovato
}
return false; //non trovato
}
...
}
Linguaggi di Programmazione II
2003-04
14
7
Contare elementi di un certo tipo
public class Purse
{
public int count(Coin aCoin)
{
int matches = 0;
for (int i = 0; i < coins.size(); i++)
{
Coin c =(Coin)coins.get(i);
if (c.equals(aCoin)) matches++;//found
a match
}
return matches;
}
...
Linguaggi di Programmazione II
15
2003-04
}
Trovare il massimo
public class Purse
{
public Coin getMaximum()
{
//inizializza il max al primo valore
Coin max =(Coin)coins.get(0);
for (int i = 1; i <coins.size(); i++)
{
Coin c =(Coin)coins.get(i);
if (c.getValue()>max.getValue()) max =c;
}
return max;
}
...
}
Linguaggi di Programmazione II
2003-04
16
8
Trovare il minimo
public class Purse
{
public Coin getMinimum()
{
//inizializza il min al primo valore
Coin min =(Coin)coins.get(0);
for (int i = 1; i <coins.size(); i++)
{
Coin c =(Coin)coins.get(i);
if (c.getValue()<min.getValue()) min =c;
}
return min;
}
...
}
Linguaggi di Programmazione II
2003-04
17
File Purse.java
import java.util.ArrayList;
/**
Un borsellino contiene una raccolta di monete.
*/
public class Purse
{
/**
Costruisce un borsellino vuoto.
*/
public Purse()
{
coins = new ArrayList();
}
/**
Aggiunge una moneta al borsellino.
@param aCoin la moneta da aggiungere
*/
public void add(Coin aCoin)
{
coins.add(aCoin);
}
Linguaggi di Programmazione II
2003-04
18
9
/**
Ispeziona il valore totale delle monete
nel borsellino.
@return la somma dei valori di tutte le monete
*/
public double getTotal()
{
double total = 0;
for (int i = 0; i < coins.size(); i++)
{
Coin aCoin = (Coin)coins.get(i);
total = total + aCoin.getValue();
}
return total;
}
Linguaggi di Programmazione II
2003-04
19
/**
Conta il numero delle monete nel borsellino.
@return il numero di monete
*/
public int count()
{
return coins.size();
}
/**
Verifica se il borsellino contiene almeno
una moneta uguale alla moneta fornita.
@param aCoin la moneta da trovare
@return true se c’è una moneta uguale a aCoin
Linguaggi di Programmazione II
2003-04
20
10
*/
public boolean find(Coin aCoin)
{
for (int i = 0; i < coins.size(); i++)
{
Coin c = (Coin)coins.get(i);
if (c.equals(aCoin)) return true; // trovata
}
return false; // non trovata nell’intera lista
}
/**
Conta il numero di monete nel borsellino che
sono uguali alla moneta fornita.
@param aCoin la moneta da trovare
@return il numero di monete uguali a aCoin
Linguaggi di Programmazione II
2003-04
21
*/
public int count(Coin aCoin)
{
int matches = 0;
for (int i = 0; i < coins.size(); i++)
{
Coin c = (Coin)coins.get(i);
if (c.equals(aCoin)) matches++; // trovata
}
return matches;
}
/**
Trova la moneta con il valore massimo.
(Precondizione: Il borsellino non è vuoto)
@return una moneta con il valore massimo tra
quelle presenti nel borsellino
Linguaggi di Programmazione II
2003-04
22
11
Coin getMaximum()
{
Coin max = (Coin)coins.get(0);
for (int i = 1; i < coins.size(); i++)
{
Coin c = (Coin)coins.get(i);
if (c.getValue() > max.getValue())
max = c;
}
return max;
}
private ArrayList coins;
}
Linguaggi di Programmazione II
2003-04
23
Memorizzare numeri in vettori
„
„
ArrayList memorizza oggetti
Per i numeri (dati primitivi) si utilizzano classi
wrapper (involucro)
‰
‰
„
Double d = new Double(123.45);
double x = d.doubleValue();
Aggiungiamo numeri a un vettore:
‰
ArrayList data = new ArrayList();
Double d = new Double(123.45);
data.add(d);
//recuperiamo il numero
x = ((Double).data.get(i)).doubleValue();
Linguaggi di Programmazione II
2003-04
24
12
Array
„
Array = sequenza di lunghezza prefissata di
valori dello stesso tipo (classe o tipo primitivo)
‰
‰
‰
‰
‰
Ogni posizione è individuata da un indice
La prima posizione ha indice 0
Deve essere creato con new
E’ un oggetto
Ci si riferisce ad esso usando vbl di riferimento
Linguaggi di Programmazione II
2003-04
25
Figura 3
Un riferimento ad array e un array
Linguaggi di Programmazione II
2003-04
26
13
Array vs. ArrayList
„Differenze:
Un array ha un campo chiamato length, piuttosto che un
metodo chiamato size().
‰ Array possono contenere anche dati primitivi (interi) oltre
che oggetti
‰ Elementi di un array sono tutti dello stesso tipo e questo
tipo deve essere dichiarato.
‰ Array non posso crescere in grandezza
‰
Linguaggi di Programmazione II
2003-04
27
Vantaggi e svantaggi
„
Vantaggi degli array:
‰
Possono memorizzare dati primitivi senza
ricorrere a “wrapper”
„
‰
sono più veloci.
Permettono di fare il type checking al tempo di
compilazione perché occorre dichiarare il tipo
Linguaggi di Programmazione II
2003-04
28
14
Vantaggi e svantaggi
„
Svantaggi degli array:
‰
‰
La grandezza dell’array deve essere dichiarata
all’inizio e non può cambiare.
Non si possono usare i metodi che invece sono
disponibili per gli ArrayList
Linguaggi di Programmazione II
2003-04
29
Dichiarare un array
„
Si scrive il tipo di dati e poi delle parentesi chiuse:
‰
‰
‰
„
int[ ] unSaccoDiNumeri;
String[ ] vincitori;
Employee[ ] personale;
Finalmente capiamo che significa
public static void main(String[] args)
‰
‰
args è un array di stringhe (gli argomenti della linea di
comando)
Java MyProgram –d file.txt
„ args[0] = “-d”
„ args[1]= “file.txt”
Linguaggi di Programmazione II
2003-04
30
15
Creare un’istanza di un array
„
Per creare un istanza di un array si usa new
seguito dal tipo e quindi dalla grandezza in
parentesi quadre:
int[] unSaccoDiNumeri;
unSaccoDiNumeri = new int[10000];
//un array di 1000 int
Linguaggi di Programmazione II
2003-04
31
Usare gli array
„
Bisogna indicare l’indice tra parentesi quadre
int[] unSaccoDiNumeri;
unSaccoDiNumeri = new int[10000];
for (int i = 0;
i < unSaccoDiNumeri.length;
i++) {
unSaccoDiNumeri[i] = i;
}
System.out.println(unSaccoDiNumeri[0]);
Linguaggi di Programmazione II
2003-04
32
16
Esempio:
„Stampiamo
gli argomenti della linea di comando
class PrintArgs {
public static void main(String[] args) {
for (int i = 0; i < args.length; i++) {
System.out.println (args[i]);
}
}
}
Linguaggi di Programmazione II
2003-04
33
Copiare Array
Una variabile array memorizza un riferimento
all’array
‰ Copiando la variabile otteniamo un secondo
riferimento allo stesso array
‰
double[] data = new double[10];
// riempi array . . .
double[] prices = data;
Linguaggi di Programmazione II
2003-04
34
17
Copiare Array
Per fare una vera copia deve creare un nuovo
array e copiare tutti gli elementi
double[] prices = new double[data.length];
for (int i=0; i < data.length; i++)
prices[i] = data[i];
Linguaggi di Programmazione II
2003-04
35
Copiare Array
Alternativamente, si può usare il metodo clone()
double[] prices = (double[])data.clone();
Linguaggi di Programmazione II
2003-04
36
18
Copiare elementi da un array
all’altro
System.arraycopy(from, fromStart, to, toStart, count);
Linguaggi di Programmazione II
2003-04
37
Uso di System.arraycopy
‰
Posso aggiungere un elemento in posizione i
ƒ
Sposto di una posizione in avanti tutti gli elementi a partire
da i
System.arraycopy(data, i, data, i+1, data.length-i-1);
data[i]=x;
Linguaggi di Programmazione II
2003-04
38
19
Uso di System.arraycopy
‰
Posso eliminare un elemento in posizione i
ƒ
Sposto di una posizione in indietro tutti gli elementi a partire
da i+1
System.arraycopy(data, i+1, data, i, data.length-i-1);
Linguaggi di Programmazione II
2003-04
39
Array riempiti solo in parte
„
„
Il max numero di elementi nell’array è prefissato
Se non riempiamo tutto l’array dobbiamo tenere
traccia del numero di elementi
final int DATA_LENGTH = 100;
double[] data = new double[DATA_LENGTH];
int dataSize = 0; //variabile complementare
//data.length è la capacità dell’array
//dataSize è la dimesione reale
„
Se inseriamo elementi dobbiamo incrementare la
dimensione
Data[dataSize] = x;
dataSize++;
Linguaggi di Programmazione II
2003-04
40
20
Array riempiti solo in parte
Figura 9
Un array riempito
solo in parte
Linguaggi di Programmazione II
2003-04
41
Array riempiti solo in parte
„ In un ciclo, fermarsi dataSize e non
for (int i = 0; i < dataSize; i++)
sum = sum + data[i];
a data.length
„ Non riempire l’array oltre i suoi limiti
if (dataSize >= data.length)
System.out.println(“Mi dispiace, l’array è pieno");
„ Oppure
creare un nuovo array più grande, copiare
gli elementi e assegnare il nuovo array alla vbl
vecchia
double newData = new double[2 * data.length];
System.arraycopy(data, 0, newData, 0, data.length);
data = newData;
Linguaggi di Programmazione II
2003-04
42
21
Figura 10
Far crescere un array
©Apogeo 2002
43
Array riempiti solo in parte
class StringArray {
private String[] stringhe;
private int stringheSize;
public StringArray () {
stringhe = new String[100];
stringheSize = 0;
}
public void addString (String s) {
stringhe[stringheSize] = s;
stringheSize++;
}
public void print () {
for (int i = 0; i < stringheSize; i++) {
System.out.println(stringhe[i]);
}
}
}
Linguaggi di Programmazione II
2003-04
44
22
File DataSet.java
/**
Questa classe calcola la media di un insieme
di valori.
*/
public class DataSet
{
/**
Costruisce un insieme di dati vuoto.
*/
public DataSet()
{
final int DATA_LENGTH = 100;
data = new double[DATA_LENGTH];
dataSize = 0;
}
/**
Aggiunge un valore all’insieme di dati.
@param x un valore
Linguaggi di Programmazione II
2003-04
45
*/
public void add(double x)
{
if (dataSize >= data.length)
{
// crea un nuovo array grande il doppio
double[] newData = new double[2 * data.length];
// copia tutti gli elementi da data a newData
System.arrayCopy(data, 0, newData, 0, data.length);
// abbandona il vecchio array e inserisci in data
// un riferimento al nuovo array
data = newData;
}
data[dataSize] = x;
dataSize++;
}
Linguaggi di Programmazione II
2003-04
46
23
/**
Restituisce la media dei dati inseriti.
@return la media, oppure 0 se non sono stati
inseriti dati
*/
public double getAverage()
{
if (dataSize == 0) return 0;
double sum = 0;
for (int i = 0; i < dataSize; i++)
sum = sum + data[i];
return sum / dataSize;
}
private double[] data;
private int dataSize;
}
Linguaggi di Programmazione II
2003-04
47
File DataSetTest.java
import java.util.Random;
/**
Questo programma collauda la classe DataSet aggiungendo
all’insieme 10000 numeri casuali e calcolandone la media.
*/
public class DataSetTest
{
public static void main(String[] args)
{
Random generator = new Random();
DataSet data = new DataSet();
final int COUNT = 10000;
System.out.println("Adding " +
COUNT + " random numbers.");
for (int i = 0; i < COUNT; i++)
{
double x = generator.nextDouble();
data.add(x);
}
double average = data.getAverage();
System.out.println("average=" + average);
}
}
Linguaggi di Programmazione II
2003-04
48
24
Array paralleli
„ Non utilizzate array
String[] names;
double salaries;
paralleli
Linguaggi di Programmazione II
2003-04
49
Array di oggetti
„ Riorganizzate i dati in
Employee[] staff;
array di oggetti
Linguaggi di Programmazione II
2003-04
50
25
Array a due dimensioni
•
•
Tabella con righe e colonne
Esempio: la scacchiera del gioco Tris
char[][] board = new char[3][3];
//array di 3 righe e 3 colonne
board[i][j] = 'x';
//accedi all’elemento della riga
i e colonna j
Linguaggi di Programmazione II
2003-04
51
File Tris.java
/**
Una scacchiera 3x3 per il gioco Tris.
*/
public class Tris
{
/**
Costruisce una scacchiera vuota.
*/
public Tris()
{
board = new char[ROWS][COLUMNS];
// riempi di spazi
for (int i = 0; i < ROWS; i++)
for (int j = 0; j < COLUMNS; j++)
board[i][j] = ' ';
}
Linguaggi di Programmazione II
2003-04
52
26
/**
Imposta un settore della scacchiera.
Il settore deve essere libero.
@param i l’indice di riga
@param j l’indice di colonna
@param player il giocatore ('x' o 'o')
*/
public void set(int i, int j, char player)
{
if (board[i][j] != ' ')
throw new IllegalArgumentException(
"Position occupied");
board[i][j] = player;
}
/**
Crea una rappresentazione della scacchiera
in una stringa, come ad esempio
|x o|
| x |
| o|.
@return la stringa rappresentativa
Linguaggi di Programmazione II
2003-04
53
*/
public String toString()
{
String r = "";
for (int i = 0; i < ROWS; i++)
{
r = r + "|";
for (int j = 0; j < COLUMNS; j++)
r = r + board[i][j];
r = r + "|\n";
}
return r;
}
private char[][] board;
private static final int ROWS = 3;
private static final int COLUMNS = 3;
}
Linguaggi di Programmazione II
2003-04
54
27
File Tris.java
import javax.swing.JOptionPane;
/**
Questo programma collauda la classe Tris
chiedendo all’utente di selezionare posizioni sulla
scacchiera e visualizzando il risultato.
*/
public class Tris
{
public static void main(String[] args)
{
char player = 'x';
Tris game = new Tris();
while (true)
Linguaggi di Programmazione II
2003-04
55
{
System.out.println(game); // invoca game.toString()
String input = JOptionPane.showInputDialog(
"Row for " + player + "(Cancel to exit)");
if (input == null) System.exit(0);
int row = Integer.parseInt(input);
input = JOptionPane.showInputDialog(
"Column for " + player);
int column = Integer.parseInt(input);
game.set(row, column, player);
if (player == 'x') player = 'o';
else player = 'x';
}
}
}
Linguaggi di Programmazione II
2003-04
56
28
Esercizi da svolgere
„ P12.10
„ P12.11
„ P12.16
„ P12.17
Linguaggi di Programmazione II
2003-04
57
29