Capitolo 8 Array Lucidi relativi al volume: Java – Guida alla programmazione James Cohoon, Jack...

Capitolo 8Array

Lucidi relativi al volume:

Java – Guida alla programmazione James Cohoon, Jack Davidson

Copyright © 2004 - The McGraw-Hill Companies srl

Java – Guida alla programmazione - James Cohoon, Jack Davidson


Nozioni di base Spesso il programmatore deve poter rappresentare un gruppo

di valori come elenco L'elenco può essere unidimensionale o multidimensionale

Java fornisce le classi per array e insiemi

Vediamo prima gli array



Terminologia di base L'elenco è composto di elementi

Gli elementi in un elenco hanno un nome comune

L'elenco è referenziato attraverso il nome comune

Gli elementi dell'elenco sono dello stesso tipo (il tipo di base)

Gli elementi di un elenco sono referenziati indicizzando il nome comune



Funzioni degli array Java Gli indici sono indicati come espressioni tra parentesi quadre: [ ]

Il tipo di base può essere qualsiasi tipo

La dimensione dell'array può essere specificata in fase di esecuzione

Il tipo dell'indice è intero e l'intervallo deve essere 0 … n-1 Dove n è il numero di elementi

Controllo automatico dei confini Assicura che qualsiasi riferimento a un elemento dell'array sia

valido

La lunghezza del campo dati specifica il numero di elementi nell'elenco

L'array è un oggetto Presenta funzioni comuni a tutti gli altri oggetti


Copyright © 2004 - The McGraw-Hill Companies srlStili di definizione delle variabili array Senza inizializzazione

Type ofvalues in

list

Name oflist

Bracketsindicate arrayvariable being

defined

ElementType[] id ;

Tipo dei valori

dell'elenco

Le parentesi quadre

caratterizzano la definizione

di una variabile array

Nome dell'elenco


Copyright © 2004 - The McGraw-Hill Companies srlStili di definizione delle variabili array Con inizializzazione

ElementType[] id = new ElementType[n];

Nonnegative integer expression specifying thenumber of elements in the array

Reference to a new array of nelements

Espressione intera non negativa che specifica il numero di elementi dell'array

Riferimento a un nuovo array di n elementi



Esempio Definizioni

char[] c;int[] value = new int[10];

Provoca La variabile oggetto c non è inizializzata La variabile oggetto array v fa riferimento a un nuovo

elenco di dieci elementi interi Ogni intero è inizializzato per impostazione predefinita

a 0

value 0 0.0 0 0 0

-c



Considerare

int[] v = new int[10];int i = 7;int j = 2;int k = 4;v[0] = 1;v[i] = 5;v[j] = v[i] + 3;v[j+1] = v[i] + v[0];v[v[j]] = 12;System.out.println(v[2]);v[k] = Integer.parseInt(stdin.readLine());

v 00 0 00 0 00 00

v[2]v[0] v[1] v[5]v[3] v[4] v[7]v[6] v[9]v[8]



Considerare


v 01 0 00 0 00 00

v[2]v[0] v[1] v[5]v[3] v[4] v[7]v[6] v[9]v[8]



Considerare


v 01 0 00 0 50 00

v[2]v[0] v[1] v[5]v[3] v[4] v[7]v[6] v[9]v[8]



Considerare


v 81 0 00 0 50 00

v[2]v[0] v[1] v[5]v[3] v[4] v[7]v[6] v[9]v[8]



Considerare


v 81 0 06 0 50 00

v[2]v[0] v[1] v[5]v[3] v[4] v[7]v[6] v[9]v[8]



Considerare


v 81 0 06 0 50 012

v[2]v[0] v[1] v[5]v[3] v[4] v[7]v[6] v[9]v[8]



Considerare


v 81 0 06 0 50 012

v[2]v[0] v[1] v[5]v[3] v[4] v[7]v[6] v[9]v[8]

Viene visualizzato 8



Considerare


v 81 0 06 3 50 012

v[2]v[0] v[1] v[5]v[3] v[4] v[7]v[6] v[9]v[8]

Si supponga di estrarre 3



Considerare Segmento

int[] b = new int[100];b[-1] = 0;b[100] = 0;

Provoca La variabile array fa riferimento a un nuovo elenco di 100

interi Ogni elemento è inizializzato a 0

Due eccezioni da lanciare -1 non è un indice valido (troppo piccolo) 100 non è un indice valido (troppo grande)

IndexOutOfBoundsException



Considerare

Point[] p = new Point[3];p[0] = new Point(0, 0);p[1] = new Point(1, 1);p[2] = new Point(2, 2);p[0].setX(1);p[1].setY(p[2].getY());Point vertex = new Point(4,4);p[1] = p[0];p[2] = vertex;



Considerare


Point: (0, 0)

p

p[0] p[1]

Point: (1, 1) Point: (2, 2)

p[2]



Considerare


Point: (1, 0)

p

p[0] p[1]

Point: (1, 1) Point: (2, 2)

p[2]



Considerare


Point: (1, 0)

p

p[0] p[1]

Point: (1, 2) Point: (2, 2)

p[2]



Considerare


Point: (1, 0)

p

p[0] p[1]

Point: (1, 2) Point: (2, 2)

p[2]

vertex

Point: (4, 4)



Considerare


Point: (1, 0)

p

p[0] p[1]

Point: (2, 2)

p[2]

vertex

Point: (4, 4)



Considerare


Point: (1, 0)

p

p[0] p[1] p[2]

vertex

Point: (4, 4)



Inizializzazione esplicita Sintassi

ElementType[] id = { exp0 , exp1 , ... expn-1 };

id references an array of n elements. id[0] hasvalue exp0 , id[1] has value exp1 , and so on.

Each expi is an expression thatevaluates to type ElementType

id fa riferimento a un array di n elementi. id[0] ha valore exp0, id[1] ha valore exp1 e così via

Ogni elemento exp è un'espressione che dà un risultato di tipo ElementType



Inizializzazione esplicita Esempio

String[] puppy = "nilla“, “darby“, "galen", "panther" };

int[] unit = 1 };

Equivale aString[] puppy = new String[4];puppy[0] = "nilla"; puppy[1] = “darby";puppy[2] = "galen"; puppy[4] = "panther";

int[] unit = new int[1];unit[0] = 1;



Membri dell'array Lunghezza del membro

Dimensione dell'arrayfor (int i = 0; i < puppy.length; ++i) {

System.out.println(puppy[i]);}



Membri dell'array Membro clone()

Produce una copiaPoint[] u = new Point(0, 0), new Point(1, 1)};Point[] v = u.clone();

v[1] = new Point(4, 30);





v[1] = new Point(4, 30);

Point: (0, 0)

v

v[0] v[1]

Point: (1, 1)

u

u[0] u[1]





v[1] = new Point(4, 30);

Point: (0, 0)

v

v[0] v[1]

Point: (1, 1)

u

u[0] u[1]

Point: (4, 30)



Creazione di una copia approfondita Esempio

Point[] w = new Point[u.length];for (int i = 0; i < u.length; ++i) {

w[i] = u[i].clone();}



Creazione di una copia approfondita

Point: (0, 0)

w

w[0] w[1]

Point: (2, 1) Point: (2, 2)

w[2]

u

u[0] u[1] u[2]

Point: (0, 0) Point: (2, 1) Point: (2, 2)



Ricerca di un valore

System.out.println("Enter search value (number): ");int key = Integer.parseInt(stdin.readLine());

int i;for (i = 0; i < data.length; ++i) {

if (key == data[i]) {break;

}}

if (i != data.length) {System.out.println(key + " is the " + I

+ "-th element");}else{

System.out.println(key + " is not in the list");}



Ricerca di un valoreSystem.out.println("Enter search value (number): ");int key = Integer.parseInt(stdin.readLine());



}}




data 54 9

20 1

key 5

i -







}}




data 54 9

20 1

key 5

i 0







}}




data 54 9

20 1

key 5

i 1






}}




data 54 9

20 1

key 5

i 2



Ricerca del valore minimo Segmento

int minimumSoFar = sample[0];for (int i = 1; i < sample.length; ++i) {

if (sample[i] < minimumSoFar) {minimumSoFar = sample[i];

}}


Copyright © 2004 - The McGraw-Hill Companies srlMethod sequentialSearch() di ArrayTools.java

public static int sequentialSearch(int[] data, int key) {for (int i = 0; i < data.length; ++i)

if (data[i] == key) return i;}

}

return -1;}

Considerareint[] score = 6, 9, 82, 11, 29, 85, 11, 28, 91 };int i1 = sequentialSearch(score, 11);int i2 = sequentialSearch(score, 30);


Copyright © 2004 - The McGraw-Hill Companies srlMethod sequentialSearch() di ArrayTools.java

public static int sequentialSearch(int[] data, int key) {for (int i = 0; i < data.length; ++i)

if (data[i] == key) return i;}

}

return -1;}

Considerareint[] score = 6, 9, 82, 11, 29, 85, 11, 28, 91 };int i1 = sequentialSearch(score, 11);int i2 = sequentialSearch(score, 30);

data 826 9 8511 29 2911 91

20 1 53 4 76 8

key 11



Method putList() di ArrayTools.java

public static void putList(int[] data) for (int i = 0; i < data.length; ++i)

System.out.println(data[i]);}

}

Considerareint[] score = 6, 9, 82, 11, 29, 85, 11, 28, 91 };putList(score);

public static int[] getList() throws IOException {

BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

int[] buffer = new int[MAX_LIST_SIZE];

int listSize = 0;

for (int i = 0; i < MAX_LIST_SIZE; ++i) {String v = stdin.readLine();if (v != null) {

int number = Integer.parseInt(v);buffer[i] = number;++listSize;

}else{

break;}

}

int[] data = new int[listSize];for (int i = 0; i < listSize; ++i) {

data[i] = buffer[i];}

return data;}

Metodo getList() di ArrayTools.java



ArrayTools.java - strutturapublic class ArrayTools {

// costante di classe private static final int MAX_LIST_SIZE = 1000;

// sequentialSearch(): cerca una chiave in un elenco non ordinato

public static int binarySearch(int[] data, int key) ...

// valueOf(): produce una rappresentazione stringa public static void putList(int[] data) ...

// getList(): estrae e restituisce fino a MAX_LIST_SIZE valori

public static int[] getList() throws IOException ...

// reverse(): inverte l'ordine dei valori degli elementi public static void reverse(int[] list) ...

// binarySearch(): cerca una chiave in un elenco ordinato public static int binarySearch(char[] data, char key) ...}



Demo.javaimport java.io.*;

public class Demo {// main(): punto di ingresso per l'applicazionepublic static void main(String[] args) throws IOException {

System.out.println("");System.out.println("Enter list of integers:");int[] number = ArrayTools.getList();

System.out.println("");System.out.println("Your list");ArrayTools.putList(number);

ArrayTools.reverse(number);System.out.println("");System.out.println("Your list in reverse");ArrayTools.putList(number);System.out.println();

}}



Ordinamento Problema

Disporre gli elementi in modo che siano ordinati secondo uno schema desiderato Lo standard è l'ordine non decrescente

Perché non dire ordine crescente?

Attività principali Confronto degli elementi Aggiornamento o spostamento degli elementi



Ordinamento per selezione Base dell'algoritmo

All'iterazione i, un metodo di ordinamento per selezione Trova l'elemento contenente l'iesimo valore più piccolo

del suo elenco v e scambia quell'elemento con v[i]

Esempio - iterazione 0 Scambia l'elemento più piccolo con v[0] Provoca lo spostamento nella posizione corretta per un

risultato ordinato del più piccolo elemento

v 'Q''E' 'W' 'Y''R' 'T' 'I''U' 'P''O'

20 1 53 4 76 98






Esempio - iterazione 1 Scambia il secondo elemento più piccolo con v[1] Provoca lo spostamento nella posizione corretta per un

risultato ordinato del secondo elemento più piccolo

v 'Q''E' 'W' 'Y''R' 'T' 'I''U' 'P''O'

20 1 53 4 76 98






Esempio - iterazione 1 Scambia il secondo elemento più piccolo con v[1] Provoca lo spostamento nella posizione corretta per un

risultato ordinato del secondo elemento più piccolo

v 'Q''E' 'I' 'Y''R' 'T' 'W''U' 'P''O'

20 1 53 4 76 98


Copyright © 2004 - The McGraw-Hill Companies srlOrdinamento per selezione ArrayTools.javapublic static void selectionSort(char[] v) {

for (int i = 0; i < v.length-1; ++i) { // intuisce la posizione dell'iesimo elemento più piccolo

int guess = i;for (int j = i+1; j < v.length; ++j) { if (v[j] < v[guess]) // intuizione corretta?? // aggiorna guess all'indice dell'elemento più

piccologuess = j;

}}

// guess è corretto, quindi scambia gli elementichar rmbr = v[i];v[i] = v[guess];v[guess] = rmbr;

}}



Iterazione i

// intuisce la posizione dell'iesimo elemento più piccolo

int guess = i;for (int j = i+1; j < v.length; ++j) {

if (v[j] < v[guess]) // l'intuizione è giusta?// aggiorna guess all'indice dell'elemento

più piccologuess = j;

}

// ora guess è corretto, scambia gli elementi v[guess] e v[0]



Array multidimensionali Molti problemi richiedono di organizzare le informazioni come

elenco bidimensionale o multidimensionale

Esempi Matrici Animazione grafica Modelli di previsione economica Rappresentazione di mappe Studi temporali sui cambiamenti della popolazione Progettazione di microprocessori



Esempio Segmento

int[][] m = new int[3][];m[0] = new int[4];m[1] = new int[4];m[2] = new int[4];

Produce

m

m[0] m[1] m[2]

0 0 0 0 0 0 0 0

00 0 0

m[2][0] m[2][1] m[2][2] m[2][3]

m[0][0] m[0][1] m[0][2] m[0][3] m[1][0] m[1][1] m[1][2] m[1][3]



Esempio Segmento

for (int r = 0; r < m.length; ++r) {for (int c = 0; c < m[r].length; ++c) {

System.out.print("Enter a value: ");m[r][c] =

Integer.parseInt(stdin.readLine());}

}



Esempio Segmento

String[][] s = new String[4][];s[0] = new String[2];s[1] = new String[2];s[2] = new String[4];s[3] = new String[3];

Produce

s

s[0] s[1] s[2]

null null

null null

null null null

s[3][0] s[3][1] s[3][2]

s[1][0] s[1][1]

s[0][0] s[0][1]

null null null null

s[2][0] s[2][1] s[2][2] s[2][3]

s[3]



Esempio Segmento

int c[][] = 1, 2, 3, 4, 5, 6, 7, 8, 9}};

Produce

c

c[0] c[1] c[2]

1 2

3 4

7 8 9

c[3][0] c[3][1] c[3][2]

c[1][0] c[1][1]

c[0][0] c[0][1]

5 6

c[2][0] c[2][1]

c[3]



Matrici Un array bidimensionale a volte è conosciuto come matrice

perché ricorda quel concetto matematico

Una matrice con m righe e n colonne è rappresentata matematicamente nel modo seguente

a1 1 a 1 2 a 1 n

a2 1 a 2 2 a 2 n

am 1 a m 2 a m n



Somma di matrici Definizione C = A + B

cij = a1ib1j + ai2b2j + . . . + ainbnj

cij è la somma di termini prodotta dalla moltiplicazione degli elementi della riga i di a con quelli della colonna c di b



Somma di matricipublic static double[][] add(double[][] a, double[][]

b) {

// determina il numero di righe nella soluzioneint m = a.length;

// determina il numero di colonne nella soluzioneint n = a[0].length;

// crea l'array per contenere la sommadouble[][] c = new double[m][n];

// calcola la somma della matrice riga per rigafor (int i = 0; i < m; ++i) {

// produce la riga correntefor (int j = 0; j < n; ++j) {

c[i][j] = a[i][j] + b[i][j];}

}

return c;}

Capitolo 8 Array Lucidi relativi al volume: Java – Guida alla programmazione James Cohoon, Jack...

Documents

Transcript of Capitolo 8 Array Lucidi relativi al volume: Java – Guida alla programmazione James Cohoon, Jack...