1
|
|
2
|
- Un vector de datos es un conjunto de variables adyacentes de un tipo
determinado.
- Los vectores facilitan la administración de conjuntos de datos
relacionados, ya que no se tienen que manipular individualmente.
|
3
|
- Un vector se compone de variables o celdas consecutivas que pueden
almacenar valores de un tipo específico. Cada celda puede almacenar un
valor y a cada una se le asocia un entero conocido como “índice” que es
la posición que ocupa dentro del vector. Todos los valores almacenados
en el vector son del mismo tipo.
|
4
|
- Al igual que una variable simple un vector debe declararse primero y
luego inicializarse.
- Posteriormente se pueden guardar y recuperar valores en celdas
independientes accediendo a ellas mediante el índice correspondiente.
- También se puede “recorrer” el vector incrementando o decrementando el
valor de una variable entera utilizada como índice.
|
5
|
- La declaración de un vector se puede hacer de la siguiente manera:
- tipo v []; // se declara v que es una referencia a un vector
- v = new tipo [cantidadDeCeldas]; // se inicializa el vector
- También se puede realizar con una sola instrucción:
- tipo v [] = new tipo [cantidadDeCeldas];
- El tamaño de un vector puede ser un valor literal o una variable entera:
- int c[] = new int [variable];
- int c[] = new int [5];
|
6
|
- Un vector puede ser declarado e inicializado en la misma instrucción:
- int c[] = {20, 45, 32, 5, 1};
- Luego de inicializar el vector, su tamaño queda almacenado dentro del
vector en una variable pública llamada length. Ejemplo:
- Si c = new int [5]; entonces c.length vale 5.
|
7
|
- Para asignar un valor x a la posición i del vector indicando el índice
de la celda deseada. Ejemplo:
- v[i] = x;
- Para asignar a x el valor almacenado en la posición i del vector se hace
lo mismo. Ejemplo:
- x = v[i]; //Denominado como “campo v sub i”.
- // i se conoce como índice.
|
8
|
- Un vector puede ser fácilmente recorrido por medio de un ciclo for.
- Se entiende por recorrido a una secuencia de accesos consecutivos a las
celdas del vector.
- El recorrido se logra variando el valor del índice de acceso a las
celdas del vector.
|
9
|
|
10
|
|
11
|
- int vector []; // El vector es una referencia a un vector
- vector = new int[5]; // Se crea el vector de 5 celdas (0-4)
- int i = 3; // i se usará para indicar el índice
- vector[i] = 8; // Se asigna a la celda 3 el valor 8
|
12
|
|
13
|
|
14
|
- Si se trata de acceder a una posición no existente se producirá una
excepción con el mensaje: ArrayIndexOutOfBoundsException
- Significa que se está tratando de acceder a algo que está fuera de los
límites establecidos para el vector.
- Para que un programa no se caiga debido a esto es conveniente utilizar
manejo de excepciones (try { } catch(){ }).
|
15
|
- El nombre de un vector es una referencia que contiene la dirección
inicial donde se ubican los datos asociados al mismo.
- Los cambios efectuados a un vector dentro de un método que lo recibe
como parámetro se mantienen aún después de finalizado el método.
- Al pasar un vector como parámetro a un método solo se copia la dirección
del vector hacia la referencia que existen dentro del método (no se genera una copia de los datos
almacenados en las celdas del vector).
A partir de este punto tanto la referencia utilizada para
ejecutar el llamado (externa al método) y el parámetro que recibe la
referencia, “apuntan” al inicio del mismo grupo de datos en memoria.
|
16
|
|
17
|
|
18
|
|
19
|
|
20
|
- Cada celda de un vector es equivalente a una variable por lo que se
puede declarar un vector de referencias a objetos.
- En Java las referencias a objetos van a ser automáticamente
inicializadas a null al crear el vector.
- Posteriormente hay que crear cada objeto independientemente y asignarlo
a la celda deseada.
|
21
|
|
22
|
|
23
|
|
24
|
- Los vectores son de las estructuras más importantes en la mayoría de los
lenguajes.
- Normalmente sirven para almacenar, procesar, buscar y recuperar valores
específicos dentro de un grupo de datos.
|
25
|
- Entre los usos comunes que se les pueden dar son:
- Calcular valores nuevos a partir de secuencias de valores leídos sin
perder el detalle de los mismos.
- Para ordenar una serie de valores entre sí.
- Para buscar si un valor específico pertenece a un grupo de valores
previamente almacenados.
- Para indexar información.
- Para asociar valores entre sí.
- Para clasificar información.
|
26
|
- Calcular la suma de los valores almacenados.
- Calcular el promedio.
- Encontrar el mayor valor dentro del vector.
- Encontrar el menor valor dentro del vector.
|
27
|
- El ejemplo del recorrido visto previamente muestra como, mediante el uso
de una variable acumuladora, se puede ir sumando cada elemento del
vector para finalmente acceder al valor acumulado.
- Este tipo de procedimiento es típico y puede utilizarse para diferentes
cálculos incluyendo el del promedio de un grupo de valores.
|
28
|
- Para calcular un promedio simplemente bastaría con acumular la suma y
dividir entre el total de elementos que fueron sumados.
- Si el promedio incluye a todos los elementos del vector basta con
dividir entre el tamaño del mismo.
- En caso contrario hace falta disponer de un contador para incrementarlo
en uno cada vez que se suma un valor a la suma total y al final dividir
entre dicho valor.
- En caso típico es promediar solamente los valores mayores que cero
dentro de un vector o que cumplen con algún criterio de selección
específico.
|
29
|
- Otro ejemplo típico de recorrido en vectores incluye el encontrar la
posición del elemento mayor o menor.
- Normalmente se puede asumir que el valor más alto o más bajo se
encuentra en la primera posición del vector, a partir de ahí se puede
llevar a cabo un recorrido buscando otro elemento que sea más pequeño
que el menor o más grande que el mayor.
- Un error común es definir una variable para guardar el valor del menor o
el mayor inicializando en 0 la misma.
Por ejemplo: Si todos los números son negativos { -12, -6, -10}
va a salir que el mayor es 0 aunque el mayor es -6. Aunque son cálculos
simples siempre hay que tener cuidado con esto.
|
30
|
|
31
|
|
32
|
- Los algoritmos de ordenamiento son de los más estudiados en el campo de
la computación.
- Los algoritmos más comunes y simples de ordenamiento son: burbuja y
selección.
- Existen otros más eficientes y complejos tales como el ordenamiento
rápido o “quicksort” cuyo estudio se lleva a cabo en cursos de
Estructuras de Datos y Análisis de Algoritmos.
|
33
|
- El algoritmo de burbuja se basa en llevar a cabo recorridos por el
vector comparando el elemento de cada celda con el de la siguiente
celda.
- En cada momento se intercambian los elementos o se dejan tal y como
están para asegurar que el valor más alto encontrado “suba” o se
desplace hacia la derecha.
- El efecto de esto es lograr que el valor más alto o bajo (dependiendo de
la forma en que se programe) “suba” hasta la última posición del vector
a modo de “burbuja”.
- Si este proceso se repite tantas veces como elementos tiene el vector, todos
los elementos subieron hasta la posición más alta que podían encontrar,
asegurando que que el vector ha quedado ordenado.
|
34
|
|
35
|
|
36
|
|
37
|
- Dependiendo del hecho de que un
vector esté ordenado o no, así se puede utilizar alguno de los
siguientes tipos de búsqueda:
- Búsqueda secuencial: consiste en llevar a cabo un recorrido a lo largo
de todos los elementos del vector.
Esto hay que hacerlo si los elementos del vector no están
ordenados.
- Búsqueda binaria: consiste en descartar con cada comparación la mitad de
los elementos restantes en el vector.
Aplica solo si el vector está ordenado y puede reducir el tiempo
de búsqueda llevando a cabo solo unas cuantas comparaciones.
|
38
|
|
39
|
- La búsqueda binaria consiste en ubicar la posición de un elemento
ubicado dentro de un rango de elementos.
- El rango se define mediante la posición del elemento inicial y la
posición del elemento final.
- La idea central detrás del algoritmo de búsqueda binaria es que con una
sola comparación se logre reducir a la mitad el rango de búsqueda dentro
del vector. Se elimina la mitad
del rango donde se sabe que el elemento no está.
|
40
|
- Lo anterior se logra al comparar siempre el valor buscado con el que se
encuentra en la posición ubicada en la mitad del camino entre la primera
y última posición del rango de valores dentro de los que se está
buscando.
- Si el valor es igual al encontrado se devuelve esa posición.
- Si es menor se busca en el nuevo rango definido desde el inicio hasta
la mitad – 1. Si el valor es mayor se busca en el rango comprendido
entre la mitad + 1 y el final.
- Si el inicio y el final llegan al mismo punto sin encontrar el elemento
se devuelve una posición inválida indicando que el elemento no se
encuentra en el vector.
- Note que el proceso es naturalmente recursivo.
|
41
|
|
42
|
|
43
|
|
44
|
- Además de permitir almacenar múltiples datos a la vez, la capacidad de
utilizar índices para ubicar o “desreferenciar” el valor de una celda
específica le da una versatilidad importante y muy útil a los vectores.
- Métodos como utilizar un mismo índice para acceder a varios vectores a
la vez, o utilizar el valor de un vector como índice en otro vector (uso
de índices de forma anidada o indirecta) permiten codificar de forma
inmediata operaciones comunes en las aplicaciones modernas.
|
45
|
- Existen varias formas de asociar vectores, la más común es asumiendo que
cada celda en una posición dada de un vector tiene relación con los
valores de las celdas de otros vectores que se ubican en una posición con
el mismo valor .
- Esto permite recorrer varios vectores en un solo ciclo relacionando los valores de las celdas con
posiciones comunes entre sí.
|
46
|
|
47
|
|
48
|
- Cuando se tiene una estructura o vector con datos pertenecientes a
objetos compuestos cuya información no se quiere duplicar, se pueden
crear otros vectores que contengan las posiciones o “índices” del vector
de datos.
- Cada vector con índices tendrá el orden en que se desean “recorrer” los
datos del vector principal .
- Si se quieren los datos en el orden especificado en un vector de
indexación se recorre tomando los valores de cada celda y se utiliza
cada uno como el índice para ubicar posiciones en el vector que contiene
los datos.
- La siguiente figura muestra el uso de tres índices de ordenamiento
diferentes para un mismo vector de objetos.
|
49
|
|
50
|
|
51
|
- Otro caso típico es tener un vector que se asocia mediante el índice a
un vector y su contenido se utiliza como índice de un tercer vector.
- La combinaciones que se den van a depender del problema que se quiere
resolver y de la forma en que se visualice la información que se quiere
representar.
|
52
|
|
53
|
|
54
|
|
55
|
|
56
|
- Una matriz es típicamente una estructura bi-dimensional compuesta de
celdas.
- Cada celda es identificada por las coordenadas asociadas a cada una de
las dos dimensiones que la componen.
- La matriz puede ser vista como una tabla compuesta por filas y columnas.
|
57
|
|
58
|
- En java una matriz se implementa mediante un vector de vectores.
- Se puede declarar e inicializar primero un vector de filas, y luego
declarar e inicializar cada una de las filas individualmente.
|
59
|
|
60
|
- Para tener acceso a las celdas de una matriz se debe “desreferenciar” la
celda deseada indicando los índices o coordenadas de la misma dentro de
la matriz.
- Aunque los índices no corresponde a filas o columnas es “útil” tener
consistencia en la interpretación que se le da a cada coordenada. Por
ejemplo asumir que la primera coordenada siempre representa filas y la
segunda las columnas.
- En la mayoría de los lenguajes se utilizan paréntesis cuadrados para
indicar las coordenadas.
|
61
|
|
62
|
- Dependiendo del problema se puede requerir llevar a cabo secuencias de
acceso a las celdas en forma consecutiva.
- Por ejemplo:
- sumar todos los valores de una fila específica, o de una columna.
- imprimir los valores de las celdas que se encuentran alrededor de una
celda específica.
- A estas secuencias de accesos consecutivos se les llama “recorridos”.
- Para recorrer eficientemente una matriz es conveniente comprender como
variar los índices para manipular el orden en que se visitan las celdas.
|
63
|
- En esta matriz de 2 filas y 3 columnas se visitan las celdas en el orden
siguiente:
- (0,0) (0,1) (0,2)
- (1,0) (1,1) (1,2)
- (2,0) (2,1) (2,2)
- Por lo que se imprime la salida:
- 5 12 10
- 2 8 45
- 14 21 37
|
64
|
|
65
|
|
66
|
- Para calcular la posición de una celda con respecto a otra con el fin de
“recorrer” la matriz en una dirección específica basta con obtener
“nuevas” coordenadas.
- Las “nuevas coordenadas” se obtienen a partir de las “originales”
dependiendo de la dirección deseada.
- Se debe modificar cada índice de fila y columna ya sea sumando 1,
restando 1 o dejando el valor igual.
|
67
|
- Desplazarse ascendentemente en diagonal se logra decrementando la
coordenada de la fila e incrementando la columna en cada iteración.
|
68
|
- Una forma de desplazarse alrededor de una celda con coordenadas
(fActual,cActual) de manera automática es obteniendo todas las posibles
combinaciones de -1, 0 y 1 para obtener las coordenadas de las celdas
restringidas a las filas y columnas anteriore y siguiente con respecto a
la actual.
- En otras palabras solo las celdas con valores entre fActual-1 y fActual+1 y entre
cActual-1 y cActual+1 se deben tomar en cuenta. Sin embargo así no se
puede controlar el orden de visita, sinó que solo se puede asegurar que
todas las celdas vecinas son visitadas.
|
69
|
- Las celdas alrededor de la celda actual (1 , 2) son aquellas con valores
entre las columnas 0 y 2 y las filas 1 y 3.
- Los valores del rango se obtienen sumando y restando 1 a la fila y
columna actual.
|
70
|
- El cálculo de las nuevas coordenadas al moverse en una dirección dada
siempre se puede llevar a cabo con una simple suma.
- Para subir, a la fila se le suma -1, para bajar se le suma 1
- Para ir a la izquierda, a la columna se le suma -1, para ir a la derecha
se le suma 1
- El siguiente diagrama muestra los valores que hay que sumar a las
coordenadas actuales para desplazarse en la dirección indicada.
|
71
|
|
72
|
- Una posible forma de generalizar el concepto de dirección es almacenando
los valores de desplazamiento en vectores de dos vectores utilizados
para el cálculo de índices. Uno para filas y otro para columnas.
- El índice de cada uno de los dos vectores representa la dirección
deseada y el contenido de cada celda es el valor que hay que sumarle a
la posición actual para moverse en la dirección asociada al indice.
- De esta forma se puede controlar el orden de visita a las celdas y
pueden visitarse una misma celda varias veces en un recorrido.
|
73
|
|
74
|
|
75
|
|
76
|
|
77
|
|