Post on 01-May-2015
transcript
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
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;
Point: (0, 0)
p
p[0] p[1]
Point: (1, 1) Point: (2, 2)
p[2]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;
Point: (1, 0)
p
p[0] p[1]
Point: (1, 1) Point: (2, 2)
p[2]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;
Point: (1, 0)
p
p[0] p[1]
Point: (1, 2) Point: (2, 2)
p[2]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;
Point: (1, 0)
p
p[0] p[1]
Point: (1, 2) Point: (2, 2)
p[2]
vertex
Point: (4, 4)
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;
Point: (1, 0)
p
p[0] p[1]
Point: (2, 2)
p[2]
vertex
Point: (4, 4)
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;
Point: (1, 0)
p
p[0] p[1] p[2]
vertex
Point: (4, 4)
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Membri dell'array Lunghezza del membro
Dimensione dell'arrayfor (int i = 0; i < puppy.length; ++i) {
System.out.println(puppy[i]);}
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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);
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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);
Point: (0, 0)
v
v[0] v[1]
Point: (1, 1)
u
u[0] u[1]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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);
Point: (0, 0)
v
v[0] v[1]
Point: (1, 1)
u
u[0] u[1]
Point: (4, 30)
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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();}
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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)
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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");}
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca di un valoreSystem.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");}
data 54 9
20 1
key 5
i -
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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");}
data 54 9
20 1
key 5
i 0
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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");}
data 54 9
20 1
key 5
i 0
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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");}
data 54 9
20 1
key 5
i 0
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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");}
data 54 9
20 1
key 5
i 1
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca di un valoreSystem.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");}
data 54 9
20 1
key 5
i 1
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca di un valoreSystem.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");}
data 54 9
20 1
key 5
i 1
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca di un valoreSystem.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");}
data 54 9
20 1
key 5
i 2
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca di un valoreSystem.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");}
data 54 9
20 1
key 5
i 2
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca di un valoreSystem.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");}
data 54 9
20 1
key 5
i 2
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca di un valoreSystem.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");}
data 54 9
20 1
key 5
i 2
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca di un valoreSystem.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");}
data 54 9
20 1
key 5
i 2
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
Ricerca del valore minimo Segmento
int minimumSoFar = sample[0];for (int i = 1; i < sample.length; ++i) {
if (sample[i] < minimumSoFar) {minimumSoFar = sample[i];
}}
Java – Guida alla programmazione - James Cohoon, Jack Davidson
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);
Java – Guida alla programmazione - James Cohoon, Jack Davidson
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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) ...}
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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();
}}
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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 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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
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;
}}
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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());}
}
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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]
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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
Java – Guida alla programmazione - James Cohoon, Jack Davidson
Copyright © 2004 - The McGraw-Hill Companies srl
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;}