Estructuras de datos y algoritmos
Oscar Bedoya.
[email protected]
http://eisc.univalle.edu.co/~oscarbed/Estructuras/
Edificio 331, 2º piso, E.I.S.C.
Arreglos
Definición
Colección finita, homogénea y ordenada de elementos
Arreglos
Definición
Finita:
Todo arreglo tiene un límite; es decir, debe
determinarse cuál será el número máximo de
elementos que podrán formar parte del arreglo.
Homogénea:
Todos los elementos de un arreglo son del mismo tipo
(todos enteros, todos reales, booleanos, etc., pero
nunca una combinación de distintos tipos).
Ordenada:
Se puede determinar cuál es el primer elemento, el
segundo, el tercero,.... y el n-ésimo elemento.
Arreglos
Para un arreglo de tamaño n, se pueden almacenar
elementos desde la posición 0 hasta la posición n-1
23
99
33
8
0
1
2
3
Arreglo de 4
números enteros,
llamado numeros
En la posición 0 se almacena el valor 23, esto es, numeros[0]==23
En la posición 1 se almacena el valor 99, esto es, numeros[1]==99
En la posición 2 se almacena el valor 33, esto es, numeros[2]==33
En la posición 3 se almacena el valor 8, esto es, numeros[3]==8
Arreglos
Operaciones con los arreglos
• Lectura
• Escritura
• Actualización
-Eliminación o borrado
-Modificación
• Ordenación
• Búsqueda
Arreglos
Operaciones con los arreglos (LECTURA)
• Leer el arreglo consiste en indicar una posición
especifica del arreglo y mostrar su contenido.
• Solo es posible leer un valor al tiempo
Arreglos
Operaciones con los arreglos (ESCRITURA)
• Escribir en el arreglo consiste en asignar valores en
una posición especifica del arreglo.
• Solo es posible escribir un valor al tiempo
Arreglos
TDA
Arreglo
Descripción:
Colección finita, homogénea y ordenada de elementos
Invariante:
Arreglo = <elem0 , elem1 , … , elemn-1>, 0≤i<n, elemi Tipo
Operaciones:
Arreglos
import java.io.*;
public class UsaArreglos{
public static void main(String [] args){
int numeros[]= new int[4];
numeros[1]=99;
numeros[3]=33;
numeros[0]=23;
System.out.println("El valor en la posicion 0 del
arreglo es " + numeros[0]);
}
}
Arreglos
int numeros[]= new int[4];
Define un arreglo, llamado numeros, de tipo entero,
con capacidad para 4 elementos
Arreglos
numeros[1]=99;
numeros[3]=33;
numeros[0]=23;
El operador = permite asignar valores al arreglo.
Se debe especificar la posición
Arreglos
System.out.println("El valor en la posicion 0 del
arreglo es " + numeros[0]);
}
}
Para leer el valor en una
posición del arreglo se coloca
el nombre del arreglo, seguido
del indice
Arreglos
Búsqueda
• Lineal
• Binaria
Arreglos
Búsqueda Lineal
Compara cada elemento del arreglo con el
elemento a buscar. Ya que el arreglo no está en
ningún orden especifico, es igualmente probable que
el valor se encuentre en la primer posición que en la
ultima
for(i=0; i<numeros.length; i++){
if(numeros[i]==valor)
System.out.println(“SE ENCONTRO”)
}
Arreglos
Búsqueda Binaria
• Es mas eficiente que la búsqueda lineal
• Requiere que el arreglo esté ordenado
Encuentra el elemento situado en la mitad del
arreglo y lo compara con el valor a buscar.
Si son iguales, se termina la búsqueda.
Si el valor a buscar es menor que el elemento medio,
se repite la búsqueda considerando la mitad
izquierda del arreglo. Sino, se busca en la mitad
derecha.
Arreglos
Búsqueda Binaria
Buscar el valor 6
2
6
9
12
45
67
89
90
123
345
6 < 67. Se busca en el lado izquierdo
412
Arreglos
Búsqueda Binaria
Buscar el valor 6
2
6
9
12
45
67
6 < 9. Se busca en el lado
izquierdo
Arreglos
Búsqueda Binaria
Buscar el valor 6
2
6
9
6 == 6. Se encontró el valor
Arreglos
Arreglos
public class Crear1 implements ActionListener{
public void actionPerformed(ActionEvent e){
a=Integer.parseInt(TFValorA1.getText());
if (i>=10)
miArea.append("\n\nEL ARREGLO ESTA LLENO");
else
{
numeros[i]=a;
miArea.append("\nnumeros[ " + i + " ]= " + a);
i++;
}
}
}
Arreglos
public class Ver implements ActionListener{
public void actionPerformed(ActionEvent e){
miArea.append("\n");
for(int i=0; i<numeros.length; i++)
miArea.append("\nnumeros[ "
numeros[i] );
}
}
+ i + " ]= " +
Arreglos
public class Buscar implements ActionListener{
public void actionPerformed(ActionEvent e){
for(int i=0; i<numeros.length; i++){
if (numeros[i]==Integer.parseInt(TFValorA2.getText()) )
miArea.append("\nEL VALOR " + TFValorA2.getText() + "
ESTA EN EL AREGLO" );
}
}
}
Arreglos
Ciclo del TDA Arreglo:
DISEÑO: Representado por el documento formal donde se
establecen el invariante y las operaciones
IMPLEMENTACIÓN: Los lenguajes de programación ya han
incorporado a los arreglos como tipos de datos. Cada uno de
ellos representa una implementación del mismo TDA
USO:
Arreglos
USO:
•
Desarrollar una programa que permita obtener la suma de los elementos de un
arreglo de 10 números enteros
•
En una arreglo de 100 elementos se ha almacenado números del 1 al 10. Indique la
frecuencia de aparición de cada uno de los 10 números
Descargar

Arreglos.