Informatica 2 Lezione 4

Corso di laurea in matematicaInformatica 2

Corso di laurea matematicaindirizzo matematica per le applicazioni gestionali ed economiche

indirizzo matematica per le applicazioni tecnologiche e dell’ingegneria

Corso di laurea specialistica in matematica e applicazioni indirizzo matematica

Universita di Camerino

Informatica 2 Lezione 4

1

Arrays e vettori

• Arrays e vettori sono oggetti con cui organizziamo i dati

– Dichiarazione e uso di array

– Array di oggetti

– Array passati come parametri a metodi

– Ordinare elementi in un array

– Array multidimensionali

– La classe Vector– Uso di array per gestire oggetti grafici

Informatica 2 Lezione 4

1

Il tipo array

• Un array è una lista ordinata di elementi

0 1 2 3 4 5 6 7 8 9

79 87 94 82 67 98 87 81 74 91

Un array di dimensione N ha l’indice che varia tra 0 e N-1

punteggi

L’arrayha un nome

Ogni valore è accessibiletramite un indice numerico

Questo array contiene 10 valori che hanno indice tra 0 e 9

Informatica 2 Lezione 4

1

Array

• Un qualunque valore dell’array è referenziato mediante l’operatore di selezione

– L’operatore di selezione viene invocato con il nome dell’array e l’indice tra le parentesi [ e ]

– L’indice indica la posizione del valore

– L’espressione punteggi[2]riporta il valore 94 che è il III nell’array

• L’operatore di selezione [] ha la precedenza più alta

Informatica 2 Lezione 4

1

Array

• Un’espressione di selezione può essere usata ogni volta sia appropriato usare una variabile del tipo base dell’arraylista[indice] = valore;valore = lista[indice] + terminesomma = lista[indice] + lista[indice+1] – Anche l’indice può essere un’espressione, purchè di tipo

adeguatolista[indice*2] += valore;valoreCasuale = lista[(int)Math.random()*scala];

Informatica 2 Lezione 4

1

Array

• Un’array contiene diversi elementi dello stesso tipo

• Il tipo degli elementi può essere sia primitivo sia riferimento a oggetti

– array di interi, di caratteri, di stringhe della classe String o di oggetti definiti come Rectangle

• In Java, l’array è un oggetto

• Quindi il nome dell’oggetto rappresenta una variabile riferimento e l’array stesso può essere instanziato in un diverso momento

Informatica 2 Lezione 4

1

Dichiarazione di array

• Una variabile punteggi di tipo array può essere dichiarata:

int[] punteggi = new int[10];

• Notare che il tipo dell’array non specifica la sua dimensione, ma il tipo di ogni elemento dell’array

• Ogni oggetto del tipo dichiarato ha la sua dimensione che viene stabilita alla creazione

• Il tipo della variabile punteggi è int[]

– Cioé un array di interi

• La variabile viene inizializzata con un nuovo array di 10 elementi di tipo intero

• BasicArray.java

Informatica 2 Lezione 4

1

Dichiarazione di array

• Esempi di dichiarazioni di array:

float[] prezzi = new float[5];

boolean[] etichette;

etichette = new boolean[20];

char[] codes = new char[26];

Informatica 2 Lezione 4

1

Controllo dei limiti

• Una volta creato l’array ha una dimensione fissata

• Un indice usato in una espressione che referenzia quell’array deve indicare un elemento valido

– Cioè l’indice deve essere nei limiti da 0 a N-1

• L’interprete Java solleva un’eccezione se viene usato un indice di array al di fuori dei limiti

– Questo processo si chiama controllo dei limiti

Informatica 2 Lezione 4

Controllo dei limiti

• L’ array prezzi contiene 5 valori, e l’indice per selezionarne uno deve variare tra 0 e 4

• l’espressione di riferimento, in cui la variabile cont abbia valore 7, prezzi[cont], causa l’invio dell’eccezione

ArrayOutOfBoundsException

• Un errore molto comune consiste nell’usare un indice non valido rispetto al limite

for (int index=0; index <= 5; index++) prezzi[index] *= tasse;

problema

Informatica 2 Lezione 4

1

Controllo dei limiti

• Ogni oggetto array ha l’attributo length pubblico e costante che immagazzina la dimensione dell’array

• Viene chiamata tramite il nome dell’array

prezzi.length

• Si noti ancora che length contiene il numero degli elementi non l’indice più grande

Informatica 2 Lezione 4

1

Dichiarazione di array

• Le parentesi [] possono essere associate al tipo dell’array o al suo nome

• Le due dichiarazioni sono equivalenti:

float[] prezzi;

float prezzi[];

• In genere si preferisce la prima dichiarazione

Informatica 2 Lezione 4

1

Lista di inizializzazione

• Per istanziare un array è possibile usare una lista per inizializzare l’array in un passo

• I valori iniziali da attribuire agli elementi dell’array sono delimitati da { e } e separati da ,

int[] lista = {147, 323, 89, 933, 540, 269, 97, 114, 298, 476};

char[] sezioni = {'A', 'B', 'C', 'D', 'F'};

Informatica 2 Lezione 4

1

Lista di inizializzazione

• Quando si usa una lista d’inizializzazione:

– L’operatore new non viene usato per istanziare l’array

– La sua dimensione non viene esplicitamente dichiarata

– Ma viene determninata dal numero degli elementi della lista

• La lista d’inizializzazione può essere usata solo nella dichiarazione dell’array

Informatica 2 Lezione 4

1

Parametri di tipo array

• Un intero array può essere passato come parametro attuale ad un metodo

• Come per ogni altro oggetto, viene passato il riferimento all’array

– il parametro formale e quello attuale diventano sinonimi

• Cambiare un elemento di un array in un metodo implica il cambiamento dell’array originale

• Anche un singolo elemento dell’array può essere passato come parametro attuale a un metodo e seguirà le regole del passaggio di valore al parametro a seconda del suo tipo

Informatica 2 Lezione 4

1

Array di oggetti

• Gli elementi di un array possono essere riferimenti a oggetti

String[] words = new String[25];• Nella dichiarazione si reclama spazio per archiviare 25

riferimenti a oggetti di tipo String

• NON vengono creati gli oggetti di tipo String

• Ogni oggetto archiviato in un array deve essere istanziato separatamente

Informatica 2 Lezione 4

Argomenti sulla linea di comando

• La segnatura del metodo main indica che il metodo può avere come parametri un array di oggetti di tipo String

• Questi valori provengono dalla riga di comando e vengono passati quando viene chiamato l’interprete

> java DoIt pennsylvania texas california

• All’atto dell’invocazione l’interprete passa al metodo main un array di tre oggetti String

• Le tre stringhe di caratteri sono passate come parametro e riferibili con indice 0-2

Informatica 2 Lezione 4

1

Array di oggetti

• Oggetti possono avere array come variabili d’stanza

• Si possono così creare strutture complesse

• La struttura dei dati in array e oggetti è responsabilità del programmatore

Informatica 2 Lezione 4

1

Ordinamento

• Ordinamento è il processo con cui si sistemano gli elementi di una lista in un ordine particolare

• Gli elementi devono essere ordinabili secondo un dato criterio

• Esistono numerosi algoritmi di ordinamento, che variano in efficienza

• Due molto comuni: – Ordinamento per selezione– Ordinamento per inserzione

Informatica 2 Lezione 4

1

Ordinamento per selezione

• Seleziona un valore e collocalo nella sua destinazione finale– Ripetere per tutti gli elementi

• Precisamente:– Trovare il più piccolo valore della lista– Scambiare posizione con il primo elemento della lista– Trovare il successivo valore secondo il criterio di

ordinamento scelto– Scambiarlo con la seconda posizione– Ripetere fino a che tutti gli elementi sono sistemati

Informatica 2 Lezione 4

1

Ordinamento per selezione

• Lista iniziale da ordinare in ordine crescente

3 9 6 1 2

il valore più piccolo è 1: 1 9 6 3 2

il successivo è 2: 1 2 6 3 9

il succesivo è 3: 1 2 3 6 9

il succesivo è 6: 1 2 3 6 9

Informatica 2 Lezione 4

1

Ordinamento per inserzione

• Selezionare un elemento e inserirlo nella posizione finale in una sotto lista ordinata– Ripetere fino a che tutti gli elementi sono stati inseriti

• Preciamente:– Il primo elemento sia appartenente a una sottolista oprdinata di

lunghezza 1– Inserire il secondo elemento nella sottolista, facendo scivolare se

necessario gli elementi di una posizione per fare spazio per l’inserimento– Inserire il III elemento nella sottolista ordinata di lunghezza due, con

slittamento degli elemenit se necessario– Ripetere fino a che tutti gli elementi sono stati inseriti nella posizione

opportuna

Informatica 2 Lezione 4

1

Ordinamento per inserzione

• Lista iniziale: 3 9 6 1 2

inserire 9 : 3 9 6 1 2

inserire 6 e slittare: 3 6 9 1 2

inserire 1 e slittare: 1 3 6 9 2

inserire 2 e slittare: 1 2 3 6 9

Informatica 2 Lezione 4

1

Ordinare oggetti

• Gli interi hanno un ordinamneto intrinseco, ma l’ordine di un insieme di oggetti deve essere definito da chi definisce la classe

• Un’interfaccia Java può essere usata come nome di un tipo e garantisce che un determinato metodo sarà implementato type name and guarantees that a particular class has implemented particular methods

• L’interfaccia Comparable serve per implementare un generico ordinamento per un insieme di oggetti

Informatica 2 Lezione 4

1

Confronto tra gli ordinamenti

• Gli ordinamento per selezione e inserzione sono simili per efficienza

• Entrambi hanno un ciclo esterno che scandisce gli elementi e un ciclo interno che confronta il valore del ciclo esterno con quasi tutti i valori della lista

• Quindi eseguiamo approssimativamente n2 confronti per ordinare una lista di dimensione n

• Sidice che questi due algoritmi di ordinamento sono di ordine n2

• Esistono algoritmi più efficienti, dell’ordine di n log2 n

Informatica 2 Lezione 4

1

Array di due dimensioni

• Un array a 1 dimensione archivia una lista di valori

• Un array a 2 dimensioni costituisce un tavola di valori organizzata per righe e colonne

• Un elemento di un array a 2 dimensioni element è riferito con l’uso di due indici

• Precisamente, un array a 2 dimensioni in Java è un array di array

Informatica 2 Lezione 4

1

Array multidimensionali

• Un array può avere più dimensioni

• Ciascuna dimensione suddivide la precedente in un numero specificato di elementi

• Ciascuna dimensione dell’array ha la propria costante length

• Poiché ogni dimensione dell’array è a sua volta un array di riferimenti a oggetti, potrà avere lunghezza diversa

Informatica 2 Lezione 4

1

La classe Vector

• Un oggetto della classe Vector è simile a un’array perchè consente di archiviare diversi valori

• Ma un oggetto della classe Vector – Archivia solo oggetti– Non ha la sintassi di indicizzazione dell’array

• I metodi della classe Vector sono usati per interagire con gli elementi del vettore

• La classe Vector fa parte del pacchetto java.util

Informatica 2 Lezione 4

1

La classe Vector

• Differenza tra array e vettori:

– Un vettore può dinamicamente cambiare la propria dimensione

• Per ogni vettore viene allocata una certa quantità di memoria iniziale per archiviare gli elementi elements

• Se un nuovo elemento viene aggiunto viene automaticamente acquisito nuovo spazio

Informatica 2 Lezione 4

1

La classe Vector

• La classe Vector è implementata mediante un array

• Quando serve nuovo spazio, viene creato un nuovo arrary di dimesioni maggiori e i valori del vecchio array vengono ricopiati nel nuovo

• Per inserire un elemento, dapprima vengono copiati i vecchi elementi uno ad uno nella nuova posizione del nuovo array

• Quindi, l’implementazione di Vector non è molto efficiente per inserire elementi