PDF de programación - Tema 6: Estructuras de Datos - Programación Orientada a Objetos

Programación

Orientada a Objetos

Tema 6:

Estructuras de Datos

Contenidos

•

Tema 6: Estructuras de Datos

1. MÉTODOS BÁSICOS DE BÚSQUEDA Y

ORDENACIÓN

2. TIPOS ENUMERADOS
3. COLECCIONES
4. ORDENACIÓN DE OBJETOS
5. TIPOS DE OBJETOS EN COLECCIONES
6. EJEMPLO USO DE COLECCIONES

2

Fundamentos de Ordenación y Búsqueda

•

•

Los algoritmos de ordenación y búsqueda son ampliamente
utilizados en las aplicaciones modernas.
Existe una gran variedad de algoritmos que intentan
optimizar
aplicando diferentes
técnicas.

situaciones,

distintas

• Muchos lenguajes de alto nivel proporcionan funciones que
evitan que el usuario deba implementar estos algoritmos por
sí mismo.
Hay que tener en cuenta el coste computacional asociado a
la búsqueda y ordenación sobre colecciones de tamaño N.

•

3

Búsqueda secuencial

Localizar, en una colección de elementos, el primer elemento que cumple
una condición dada.

Ej: buscar aula libre en una determinada fecha y horario que tenga al menos n asientos

Con mucha frecuencia los elementos (objetos-sujetos) que interesa tratar
informáticamente son identificables  clave =identificador unívoco

Ej: localizar la ficha del alumno con un determinado número de expediente

La búsqueda proporciona la posición, la referencia o una copia del primer
elemento en la colección de elementos que satisface una condición determinada.

Si no hay elemento que satisfaga la condición, se devolverá una indicación de no
encontrado.

4

Algoritmo de búsqueda secuencial

PSEUDOCÓDIGO DEL ALGORITMO GENERAL

La implementación

concreta depende de la

estructura de datos

FUNCION posicion( L, clave)
{

actualprimero_de_L;
MIENTRAS queden y clave≠actual.clave HAZ actualsiguiente;
SI clave=actual.clave ENTONCES posicionpos_de_actual
EN CASO CONTRARIO posicionNoEncontrado

}

5

Búsqueda binaria

Aplicabilidad

• La lista está ordenada por la clave de búsqueda
• Se conoce el número de elementos
• Se tiene acceso directo al elemento por posición en la lista

PSEUDOCÓDIGO DEL ALGORITMO GENERAL

FUNCION posicion_bin( L, clave)
{

tamtamaño_de_la_colección;
inf0;
suptam-1;
MIENTRAS inf<=sup HAZ
{

centro = ((sup + inf) / 2);
SI L[centro].clave = clave ENTONCES
{

posicionpos_de_L[centro];
SALIR;

//inf: limite inferior del intervalo
//sup: limite superior del intervalo

//centro: elemento central del intervalo

}
SI clave<L[centro].clave ENTONCES sup=centro-1
EN CASO CONTRARIO inf=centro+1

}
posicion NoEncontrado;
SALIR;

}

6

Ordenación por inserción directa

La colección inicial de elementos se descompone en dos partes: Una parte cuyos elementos
mantienen un orden y la parte restante.

Inicialmente la parte ordenada consta de un solo elemento (el primero)

En la iteración i, los i primeros elementos están ya ordenados. Se localiza la posición que
correspondería en la parte ordenada al primer elemento de la parte desordenada (elemento i+1) y
se inserta en esa posición.

Ejemplo (En cada iteración se marca la parte ordenada con subrayado):

i=1 44 55 12 42 94 18 06 67
2 44 55 12 42 94 18 06 67
3 12 44 55 42 94 18 06 67
4 12 42 44 55 94 18 06 67
5 12 42 44 55 94 18 06 67
6 12 18 42 44 55 94 06 67
7 06 12 18 42 44 55 94 67
9 06 12 18 42 44 55 67 94



Ordenación por selección directa

La colección inicial de elementos se descompone en dos partes: Una parte cuyos elementos
mantienen un orden y la parte restante.

En la iteración i se busca dentro de la parte desordenada el elemento cuyo valor clave es menor (o
mayor, según el criterio de ordenación) y se coloca en esa posición, de forma que deja de
pertenecer a la parte desordenada de la colección.

Ejemplo (En cada iteración se marca la parte ordenada con subrayado):
i=1 44 55 12 42 94 18 06 67
2 06 55 12 42 94 18 44 67
3 06 12 55 42 94 18 44 67
4 06 12 18 42 94 55 44 67
5 06 12 18 42 94 55 44 67
6 06 12 18 42 44 55 94 67
7 06 12 18 42 44 55 94 67
9 06 12 18 42 44 55 67 94



7

8

Ordenación por intercambio directo

También es conocido como método de la burbuja.

Se basa en realizar pasadas sucesivas sobre todos los elementos de la colección. En cada pasada
se compara cada uno de los elementos de la colección con su adyacente, y se realiza el
intercambio entre ellos en caso de que el criterio de ordenación lo requiera (como si hubiera que
ordenar sólo los dos elementos comparados).

FUNCION ordenarBurbuja (L)
{

PSEUDOCÓDIGO DEL ALGORITMO GENERAL

PARA i=0 HASTA tamaño_de_la_colección-1 HAZ
{

PARA j=0 HASTA tamaño_de_la_colección-2 HAZ

SI L[j].clave>L[j+1].clave ENTONCES // caso de ordenación de menor a mayor
{

// se intercambian los elementos consecutivos
auxL[j];
L[j]L[j+1];
L[j+1]aux;

}

}

}

Ordenación por intercambio directo

Ejemplo método de la burbuja.



Inicio: 44 55 12 42 94 18 06 67
44 12 42 55 18 06 67 94
i=0
1
12 42 44 18 06 55 67 94
12 42 18 06 44 55 67 94
2
12 18 06 42 44 55 67 94
3
12 06 18 42 44 55 67 94
4
5
06 12 18 42 44 55 67 94
06 12 18 42 44 55 67 94
6
7
06 12 18 42 44 55 67 94



9

10

TIPOS ENUMERADOS

• Tipos Enumerados:
• Los tipos enumerados sirven para restringir la selección de valores a

un conjunto previamente definido.

• Un tipo enumerado permite que una variable tenga solo un valor
dentro de un conjunto de valores predefinidos, es decir, valores
dentro de una lista enumerada.

• Los valores que se definen en un tipo enumerado son constantes y se

suelen escribir en mayúsculas.

• La clase que representa los tipos enumerados en Java es

java.lang.Enum.

• Posee una serie de métodos útiles como:

‒ toString(): permite visualizar el nombre de las constantes de una

enumeración.

‒ ordinal(): permite saber el orden de declaración de las

constantes.

‒ values(): genera un vector con los valores de la enumeración.

11

TIPOS ENUMERADOS

• Ejemplos Tipos Enumerados:

public enum ColoresSemaforo {

VERDE, NARANJA, ROJO

}

public class PruebaEnum {

public static void main(String[] args) {

ColoresSemaforo cs = ColoresSemaforo.VERDE;
switch (cs) {

case ROJO:

System.out.println("No puedes pasar.");

break;

case VERDE:

System.out.println("Puedes pasar.");

break;

case NARANJA:

System.out.println("Cuidado al pasar.");

break;

public class PruebaEnum2 {

enum DiasSemana {
L, M, X, J, V, S, D

};

public static void main(String[] args) {
DiasSemana ds = DiasSemana.L;
System.out.println(ds);

}

}

}
if (cs.equals(ColoresSemaforo.VERDE)) {
System.out.println(cs.toString());
for (ColoresSemaforo csf : ColoresSemaforo.values()) {

cs = ColoresSemaforo.ROJO;

}

System.out.println(csf + ", ordinal " + csf.ordinal());

}

}

}

12

COLECCIONES

• Una colección es un objeto que recopila y organiza otros

objetos.

• La colección define las formas específicas en las que se
puede acceder y con las que se pueden gestionar esos
objetos,
los cuales se denominan elementos de la
colección.

• Existen muchos tipos específicos de colecciones que

permiten resolver distintas problemáticas.

• Las colecciones se pueden clasificar en dos categorías
generales: lineales y no lineales (ej.: jerárquica o en red).
• La organización relativa de los elementos de una

colección está determinada usualmente por:
• El orden en que se añaden los elementos a la colección.
• Alguna relación inherente entre los propios elementos.

13

COLECCIONES

• Las Colecciones en Java ofrecen un mecanismo
orientado a objetos para almacenar conjuntos de datos de
tipo similar.

• Tienen su propia asignación de memoria y un conjunto de

métodos para su iteración y recorrido.

• El framework de las colecciones en Java se basa en

una arquitectura unificada que contiene:
•

Interfaces. Tipos abstractos de datos que representan a las
colecciones. Permiten la manipulación de la colección de forma
independiente
o
implementación.
Implementaciones.
concretas de las
reutilizables.

implementaciones
interfaces. Son estructuras de datos

Representan

su

representación

las

de

los

detalles

de

•

• Algoritmos. Representan métodos de utilidad para realizar

búsquedas y ordenación. Estos métodos son polimórficos.

14

COLECCIONES

• Las clases que representan colecciones en Java se

encuentran dentro del paquete java.util.

• Las clases que representan colecciones se basan en una
serie de interfaces que definen los métodos necesarios
para su gestión y que estas clases implementarán.

• Las interfaces más importantes son las siguientes:

15

COLECCIONES

• Las interfaces de las colecciones se basan en genéricos.
Los genéricos
concepto de tipos
parametrizados, que permiten crear colecciones que
resulten fáciles de utilizar con múltiples tipos.

implementan el

• El término “genérico” significa “perteneciente o apropiado

para grandes grupos de clases”.

• Cuando nos encontramos con la definición de una
interface o clase donde se utilice la sintaxis <E> nos está
indicando que se basa en genéricos. Por ejemplo:

public interface Collection<E>

16

COLECCIONES

• La interface Collection representa una secuencia de
elementos individuales a los que se aplica una o más
reglas.

• Una colección List debe almacenar los elementos en la
forma en que fueron insertados, una colección Set no
puede tener elementos duplicados y una colección Queue
produce los elementos en el orden determinado por una
disciplina de cola.

• La interface Map representa un grupo de parejas de
objetos clave-valor, que permite realizar búsquedas de
objetos. No se permiten claves duplicadas.

17

COLECCIONES:

LISTAS

• Listas:
• Un ArrayList es un array de objetos cuyo tamaño puede
variar en tiempo de ejecución. Implementa la interface
List.

• Los objetos se pueden almacenar al final de la colección
o en una posición concreta utilizando el método add() y
borrarlos mediante remove().

• También podemos remplazar un elemento de la colección

con el método set().

• Se puede buscar un elemento en concreto utilizando los

métodos contains(), indexOf() o lastIndexOf().

• Se puede extraer un objeto de una po