Arrays PDF
Arrays PDF
Arrays PDF
Pedro Corcuera
Dpto. Matemtica Aplicada y Ciencias de la Computacin Universidad de Cantabria
[email protected]
Objetivos
Familiarizarse con el uso de arrays y array lists para coleccionar valores. Usar el ciclo for para el recorrido de arrays y array lists. Aprender algoritmos comunes para el procesado de arrays y array lists. Usar arrays multidimensionales.
Java
ndice
Arrays Ciclo for mejorado Algoritmos con arrays Uso de arrays con mtodos Arrays multidimensionales Array Lists
Java
Qu es un array? Es usual en los programas la necesidad de almacenar una lista de valores para despus procesarlos. Una posibilidad es asociar a cada valor una variable, pero esto sera ineficiente y engorroso. Un array es una variable que almacena una lista de valores del mismo tipo. El array se almacena en posiciones continuas de memoria y el acceso a los elementos se realiza mediante ndices.
Java
4
Declaracin de Arrays Para declarar un array se requiere el tipo de dato de los elementos a almacenar y un nombre para el array. Sintaxis:
double[] data; // declara var. array data
o
double data[]; Tipo double Corchetes [ ] Nombre Array data punto y coma ;
Java
Creacin de un array (instancia) Despus de declarar un array es necesario reservar memoria para todos los elementos. Se especifica el nmero de elementos del array a travs de un mtodo constructor (new).
Nota: No se puede cambiar el tamao despus de crear el array Nombre Array Pal.reservada Tipo Tamao punto y coma data = new double [10] ; data [0]
double
[1]
double
[2]
double
Java
[3]
double
[4]
double
[9]
double
6
double
[]
data
new
double [10]
Java
Declaracin y Creacin de un array Se puede declarar y asignar el valor inicial de todos los elementos:
Tipo Corchetes Nombre Array Lista del contenido pyc
int
[ ]
primos
= { 2, 3, 5, 7}
Se declara:
Nombre del array : primos Los elementos del array son del tipo: int Reserva espacio para cuatro elementos
El compilador los cuenta
Ejemplos de declaracin
//creacion y asignacion de un array de 4 valores //booleanos boolean resultados[] = {true,false,true,false}; //creacion y asignacion de un array de 4 valores //double double[] notas = {100, 90, 80, 75}; //creacion y asignacion de un array de 7 cadenas //de caracteres String dias[] = {Lun, Mar, Mie, Jue, Vie, Sab, Dom};
Java
Acceso a elementos de un array Cada elemento del array est numerado mediante un ndice, de tipo entero, que empieza en 0 y progresa secuencialmente hasta tamao_array 1.
Cuando se declaran y construyen arrays de datos numricos todos los elementos se inicializan a 0. Para tipos de datos referencia como los Strings se deben inicializar explcitamente.
public static void main(String[] args) { double data[]; data = new double[10]; data[4] = 35; }
Java
11
Nmeros de ndice de array El ndice de un array empieza en 0. Un array de n elementos tiene como rango de ndice 0an1
El primer elemento est en el ndice 0
public static void main(String[] args) { double data[]; data = new double[10]; }
Longitud del array Un array sabe cuntos elementos puede almacenar con data.length donde data es el nombre del array. Se puede usar para comprobar el rango y prevenir errores de lmites.
public static void main(String[] args) { int i = 10, value = 34; double data[] = new double[10]; if (0 <= i && i < data.length) { // valor es 10 data[i] = value; } }
Java
13
Valores
14
Alias de arrays Se puede hacer que una referencia de array se refiera al mismo contenido de otro.
int scores[] = { 10, 9, 7, 4, 5 }; int values[] = scores; // Copia de la ref. del array
Variable Array Contenido del Array
Referencias Una variable array especifica la lacalizacin del array. Al copiar la referencia se consigue una segunda referencia al mismo array.
Java
Valores
15
Recomendaciones de codificacin Declarar las dimensiones de los arrays usando constantes para facilitar las modificaciones.
final int ARRAY_SIZE = 1000; //declara una constante ... int edades[] = new int[ARRAY_SIZE];
Cuando se usan for para el recorrido de una array usar array.length en la condicin del for.
int edades[] = new int[100]; for (int i=0; i < edades.length; i++) { ... }
Java
18
Ciclo for mejorado for each Hay un ciclo for, llamado for each, que permite acceder a cada elemento del array secuencialmente. No permite modificar un elemento del array.
double[] data = . . .; double sum = 0; for (double element : data) { sum = sum + element; }
Esta variable es asignada a cada elemento del array en cada iteracin del ciclo. Est definida slo dentro del ciclo
Java
19
Arrays multidimensionales Un array multidimensional es tratado como un array de arrays. Los arrays multidimensionales se declaran colocando un nmero de corchetes igual a la dimensin del array antes/despus del nombre del array.
//array de doubles de 512x128 elementos double twoD[][] = new double[512][128] ; //array de caracteres de 8x16x24 elementos char[][][] threeD = new char[8][16][24]; //declaracion e inicializacion de una matriz double[][] m1 = {{1,2,3},{4,5,6}};
Java
20
Declaracin e inicializacin.
const int PAISES = 7; const int MEDALLAS = 3; int[][] cuenta = {{ 0, 0, 1 },
{ { { { { { }; 0, 1, 3, 0, 0, 0, 1, 0, 0, 1, 0, 2, 1 0 1 0 1 0 }, }, }, }, }, }
21
Java
Arrays multidimensionales - Acceso El acceso a un elemento de un array md es igual que en un array unidimensional. Caso bidimensional
Fila Columna
Suma y promedio
double total = 0, promedio = 0; for (double elemento : data) { total = total + elemento; } if (data.length > 0) { promedio = total / data.length; }
Java
25
Java
27
Java
28
Java
29
Java
30
Java
31
Java
32
Java
33
Algoritmos comunes - Ordenacin Ordenacin o clasificacin es el proceso de reordenar un conjunto de objetos en un orden especfico. El propsito de la ordenacin es facilitar la bsqueda de elementos en el conjunto ordenado. Existen muchos algoritmos de ordenacin, siendo la diferencia entre ellos la eficiencia en tiempo de ejecucin. Los mtodos de ordenacin se pueden clasificar en dos categoras: ordenacin de ficheros o externa y ordenacin de arrays o interna.
Java
35
Normalmente, la funcin de ordenamiento se guarda como un componente explcito (campo) de cada item (elemento). Ese campo se llama la llave del item. Un mtodo de ordenamiento es estable si el orden relativo de elementos con igual llave permanece inalterado por el proceso de ordenamiento.
Java
36
Algoritmos comunes - Ordenacin Los mtodos de ordenacin buscan un uso eficiente de la memoria por lo que las permutaciones de elementos se har in situ (uso del array original). Existen varios mtodos de ordenacin: burbuja, agitacin, seleccin, insercin, quicksort, etc.
http://personales.unican.es/corcuerp/ProgComp/Ordena/AlgoritmosOrdenamiento.html
http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
La API de Java API ofrece un mtodo de ordenacin eficiente (ascendente por defecto):
Arrays.sort(data); // Ordenacion de todo el array Arrays.sort(data, 0, currentSize); // parcial
Java
37
Anlisis de Algoritmos: Complejidad Para comparar algoritmos se pueden estudiar desde dos puntos de vista:
el tiempo que consume un algoritmo para resolver un problema (complejidad temporal) ms inters la memoria que necesita el algoritmo (complejidad espacial).
Para analizar la complejidad se cuentan los pasos del algoritmo en funcin del tamao de los datos y se expresa en unidades de tiempo utilizando la notacin asntotica O- Grande (complejidad en el peor caso).
Java
38
Anlisis de Algoritmos: Complejidad Problema: Buscar el mayor valor en una lista de nmeros desordenados (array)
Algoritmo: (n = nmero de elementos) 1 max = s1 2 i = 2 3 while i <= n 4 if si > max then 5 max = si 6 i = i + 1 7 endwhile
Java
39
Sean f(n) y g(n) funciones no negativas, f(n) es O(g(n)) si hay un valor c > 0 y n0 1 tal que f(n) cg(n) para n n0 Se dice que f(n) es de orden g(n) Ej: 7n 4 es O(n) si c=7 y n0 = 1
Java
40
Mtodo de Ordenacin: burbuja Es un mtodo caracterizado por la comparacin e intercambio de pares de elementos hasta que todos los elementos estn ordenados. En cada iteracin se coloca el elemento ms pequeo (orden ascendente) en su lugar correcto, cambindose adems la posicin de los dems elementos del array. La complejidad del algoritmo es O(n2).
Java
41
1 iter
2 iter
3 iter
4 iter
5 iter
6 iter
7 iter
1 iter
2 iter
3 iter
4 iter
5 iter
6 iter
7 iter
1 iter
2 iter
3 iter
4 iter
5 iter
6 iter
7 iter
1 iter
2 iter
3 iter
4 iter
5 iter
6 iter
7 iter
1 iter
2 iter
3 iter
4 iter
5 iter
6 iter
7 iter
1 iter
2 iter
3 iter
4 iter
5 iter
6 iter
7 iter
2 iter
3 iter
4 iter
5 iter
6 iter
7 iter
3 iter
4 iter
5 iter
6 iter
7 iter
4 iter
5 iter
6 iter
7 iter
4 iter 06 12 18 42 44 55 67 94
5 iter 06 12 18 42 44 55 67 94
6 iter 06 12 18 42 44 55 67 94
7 iter 06 12 18 42 44 55 67 94
51
Mtodo de Ordenacin: insercin Mtodo usado para ordenar una mano de naipes. Los elementos estn divididos conceptualmente en una secuencia destino y una secuencia fuente. En cada paso, comenzando con i=2 e incrementando i en uno, el elemento i-simo de la secuencia fuente se toma y se transfiere a la secuencia destino insertndolo en el lugar adecuado. Este algoritmo puede mejorarse fcilmente si vemos que la secuencia destino a1 , a2 , , ai1 est ordenada, por lo que usamos una bsqueda binaria para determinar el punto de insercin. La complejidad del algoritmo es O(n2). Es estable.
Java
53
Java
54
Java
55
Java
56
Java
57
Mtodo de Ordenacin: seleccin En ste mtodo, en el i-simo paso seleccionamos el elemento con la llave de menor valor, entre a[i],, a[n] y lo intercambiamos con a[i]. Como resultado, despus de i pasadas, el i-simo elemento menor ocupar a[1],, a[i] en el lugar ordenado. La complejidad del algoritmo es O(n2).
Java
59
Java
60
Java
61
Java
62
Java
63
Mtodo de Ordenacin: Quicksort Se basa en el hecho que los intercambios deben ser realizados preferentemente sobre distancias grandes. El algoritmo (tcnica de dividir y vencer) simplificado es:
Seleccionar un elemento del array (elemento pivote, p.e. el que se encuentra en la mitad). Todos los elementos menores al pivote se colocan en un array y los mayores en otro. Se aplica el mismo procedimiento de forma recursiva, sobre los subarrays hasta que solo exista un elemento.
Java
66
06 06
12 12
18 18
42 42
44 44
55 55
94 67
67 94
Java
67
Java
68
Bsqueda binaria
Se aplica a arrays ordenados. Compara el elemento en la mitad del array con el buscado, si es menor excluye la mitad menor, si es mayor excluye la mitad mayor. Repetir hasta encontrar el valor buscado o no se puede dividir.
Java
70
Bsqueda binaria
double searchedValue = XXX; // Valor a buscar boolean found = false; int low = 0, pos = 0; int high = data.length - 1; while (low <= high && !found) { pos = (low + high) / 2; // Mitad del array if (data[pos] == searchedValue) { found = true; } // Encontrado else if (data[pos] < searchedValue) { low = pos + 1; } // Busca en la primera mitad else { high = pos - 1; } // Busca en la segunda mitad } if (found) { System.out.println("Encontrado en la posicion " + pos+1); } else { System.out.println("No encontrado"); }
Java
71
Paso de arrays a mtodos Es comn usar arrays como parmetros de mtodos y como valor de retorno de mtodos.
Los arrays se pasan como referencia en los mtodos.
Paso de referencias El paso de una referencia da al mtodo invocado acceso a todos los elementos.
Puede modificar los datos.
public static void multiply(double[] data, double factor) { for (int i = 0; i < data.length; i++) data[i] = data[i] * factor; }
Java
73
Listas Cuando se escribe un programa que colecciona datos, no siempre se sabe cuntos valores se tendr. En tal caso una lista ofrece dos ventajas significativas:
La lista puede crecer o disminuir como sea necesario. La clase ArrayList ofrece mtodos para las operaciones comunes, tal como insertar o eliminar elementos.
Las listas con una clase genrica (puede contener muchos tipos de objetos) que se encuentra en el paquete java.util.ArrayList
Java
74
Pasar un ndice y el nuevo elemento a aadir en esa posicin. Los otros elementos se mueven.
names.add(1, Cindy);
Java
76
Java
77
Uso de ArrayList
ArrayList<String> names = new ArrayList<String>(); names.add(Ann); names.add(Cindy); System.out.println(names); names.add(1,Bob); names.remove(0); names.set(0, Bill); String name = names.get(i); String last = names.get(names.size() - 1);
Java
78
Copia de ArrayList ArrayList mantiene una referencia como los arrays. Copiando una referencia:
Para hacer una copia, pasar la referencia del ArrayList original al constructor del nuevo:
referencia ArrayList<String> newNames = new ArrayList<String>(names);
Java
79
ArrayList y mtodos De igual manera que los arrays, un ArrayList puede ser usado como parmetro o valor retornado. Ejemplo: mtodo que recibe un ArrayList y devuelve la referencia lista invertida
public static ArrayList<String> reverse(ArrayList<String> names) { // Crea una lista para el resultado del metodo ArrayList<String> result = new ArrayList<String>(); // Recorre la lista de nombres en orden inverso (ltimo a primero) for (int i = names.size() - 1; i >= 0; i--) { // Aade cada nombre al resultado result.add(names.get(i)); } return result; }
Java
80
Wrappers y auto-boxing Java ofrece las clases wrapper para tipos primitivos.
Las conversiones son automticas usando auto-boxing Tipo primitivo a clase Wrapper
double x = 29.95; Double wrapper; wrapper = x; // boxing
Wrappers y auto-boxing No se puede usar tipos primitivos en un ArrayList, pero se puede usar sus clases wrapper.
Depende del auto-boxing para la conversin
Java
82
Algoritmos con ArrayList La conversin de arrays a ArrayList requiere el cambio de: double largest = data[0];
uso de ndices [i] for
data.length
{ (int i = 1; i < data.length; i++) if (data[i] > largest) { largest = data[i]; } } double largest = data.get(0); for (int i = 1; i < data.size(); i++) { if (data.get(i) > largest) { largest = data.get(i); } }
Java
83
a
mtodos get()
data.size()
Usar un ArrayList
en cualquiera de los otros casos especialmente si se tiene un nmero desconocido de valores de entrada
Java
84
Cuidado con length o size No hay consistencia para determinar el nmero de elementos en un Array, ArrayList o String
Java
85