PDF de programación - Estructuras de datos y algoritmos 2. Estructuras de datos lineales

Estructuras de datos y algoritmos
1. Introducción
2. Estructuras de datos lineales
3. Estructuras de datos jerárquicas
4. Grafos y caminos
5. Implementación de listas, colas, y pilas
6. Implementación de mapas, árboles, y grafos

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN
4

© Michael González Harbour

19/oct/09

1

UNIVERSIDAD
DE CANTABRIA

2. Estructuras de datos lineales
• 2.1 Colecciones o bolsas
• 2.2 Conjuntos
• 2.3 Listas y Vectores
• 2.4 Pilas
• 2.5 Colas
• 2.6 Colas de prioridad
• 2.7 Mapas

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

2

2.1 Colecciones o bolsas
La colección es un ADT que permite almacenar grupos de objetos
llamados elementos
• pueden estar repetidos
• no es preciso almacenar ninguna relación de orden o secuencia
También se llaman bolsas

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

3

Operaciones básicas de las colecciones

UNIVERSIDAD
DE CANTABRIA

operación
constructor
añade

argumentos

retorna
Colección

elElemento

borra

elElemento

booleano

hazNula
pertenece

estaVacia
tamaño
iterador

elElemento

booleano

booleano
entero
Iterador

errores

elemento
incompatible
elemento
incompatible

elemento
incompatible

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

4

Notas:

UNIVERSIDAD
DE CANTABRIA

• constructor: Crea la colección con cero elementos
• añade: Añade el parámetro elElemento a la colección. Si elElemento es incompatible con los
elementos que se almacenan en esta colección lanza una excepción
• borra: Si existe en la colección al menos una instancia de elElemento, la borra de la colección y
retorna true. En otro caso, retorna false
• hazNula: Elimina todos los elementos de la colección, dejándola vacía
• pertenece: Si existe en la colección al menos una instancia de elElemento, retorna true. En otro
caso, retorna false
• estaVacia: Si la colección está vacía retorna true. En otro caso, retorna false
• tamaño: Retorna un entero que dice cuántos elementos hay en la colección
• iterador: Retorna un iterador asociado a la colección, para poder recorrer sus elementos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

5

Las colecciones en Java
Las colecciones se representan en java por la interfaz Collection
• No existe ninguna clase que la implemente directamente
• Puede usarse un conjunto o lista, ya que son extensiones de ella

UNIVERSIDAD
DE CANTABRIA

- si queremos guardar elementos repetidos usar una lista

• O definir tu propia implementación
Los métodos que modifican la colección suelen retornar un
booleano:
• true, si se ha modificado
• false, si no se ha modificado

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

6

UNIVERSIDAD
DE CANTABRIA

La interfaz Collection
public interface Collection<E>
extends Iterable<E>
{
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional
boolean remove(Object element); //optional
Iterator<E> iterator();

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

7

UNIVERSIDAD
DE CANTABRIA

La interfaz Collection (cont.)
// Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
//optional
boolean removeAll(Collection<?> c);
//optional
boolean retainAll(Collection<?> c);
//optional
void clear();
//optional
// Array operations
Object[] toArray();
<T> T[] toArray(T[] a);
}

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

8

Parámetros genéricos comodín
El carácter ? en los parámetros genéricos se usa como comodín:

- ?: para indicar cualquier clase
- ? extends E: para indicar a E, o cualquier subclase de E

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

9

Notas:

UNIVERSIDAD
DE CANTABRIA

La relación entre los métodos de la interfaz Collection y las operaciones del ADT Colección son:

Interfaz Collection ADT Colección
size
isEmpty
contains
add
remove
iterator
clear

tamaño
estaVacia
pertenece
añade
borra
iterador
hazNula

El método add debe retornar true, o lanzar una excepción si no se inserta el elemento

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

10

Constructores de las colecciones
Aunque no aparece en la interfaz (las interfaces no tienen
constructores), las clases que implementan la colección disponen
de dos constructores
• constructor sin parámetros: crea la colección vacía
• constructor con un parámetro que es una colección: crea la
nueva colección con una copia de los valores del argumento

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

11

UNIVERSIDAD
DE CANTABRIA

Operaciones con colecciones
La clase Collections tiene muchas operaciones para manejar
colecciones
• singleton: retorna un conjunto no modificable de un solo
elemento
• singletonList: ídem, retornando una lista
• singletonMap: ídem, retornando un mapa
Dispone también de operaciones para obtener colecciones no
modificables vacías:
•emptySet
•emptyList
•emptyMap

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

12

Operaciones con múltiples datos

UNIVERSIDAD
DE CANTABRIA

Operación

Descripción

containsAll() Devuelve true si todos los elementos de c per-
tenecen a la colección
addAll()
Añade todos los elementos de c a la colección.
Retorna true si la colección ha cambiado
removeAll()
Elimina todos los elementos de c que existan en
la colección, incluyendo las repeticiones.
Retorna true si la colección ha cambiado
Elimina todos los elementos de la colección
excepto los que estén en c. Retorna true si la
colección ha cambiado
Equivale al hazNula

retainAll()

clear()

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

13

Operaciones con arrays

UNIVERSIDAD
DE CANTABRIA

Operación

Descripción

Object[] toArray()

Retorna un nuevo array de objetos de
la clase Object que contiene todos
los elementos de la colección
<T> T[] toArray(T[] a) Igual que el anterior, pero el array es
de objetos de la clase genérica <T>.
Si el resultado cabe en a se devuelve
ahí; si no, se devuelve un nuevo array

Se prefiere la segunda versión, por ser más segura
Ejemplos
String[] a= v.toArray(new String[v.size()]);
String[] a= v.toArray(new String[0]);

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

14

UNIVERSIDAD
DE CANTABRIA

Ejemplos de uso
Una aplicación de una colección es almacenar una lista de visitas
a un lugar
• una misma persona puede visitar el lugar varias veces
• no interesa el orden en el que se hacen
• interesa si alguien ha visitado el lugar o no, y cuántas veces
Ejercicio:
• Crear una clase capaz de almacenar en un atributo una

colección de nombres de personas (Strings)

• Escribir un método para añadir una visita
• Escribir un método para saber cuántas visitas ha hecho una

persona (que deje la colección igual que estaba)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

15

UNIVERSIDAD
DE CANTABRIA

Ejemplo: libro de visitas
import java.util.*;
public class LibroVisitas
{
// lista de visitas
private Collection<String> bolsa;
/**
* Constructor que deja el libro vacío
*/
public LibroVisitas()
{
bolsa=new LinkedList<String>();
}

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

16

UNIVERSIDAD
DE CANTABRIA

Ejemplo: libro de visitas
public void anadeVisita(String nombre)
{
bolsa.add(nombre);
}

public int numeroVisitas(String nombre) {
int contador=0;
for(String n: bolsa) {
if (n.equals(nombre)) {
contador++;
}
}
return contador;
}
}

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

17

UNIVERSIDAD
DE CANTABRIA

2.2 Conjuntos
Un conjunto es un ADT que permite almacenar grupos de objetos
llamados elementos de modo que
• no pueden estar repetidos
• no es preciso almacenar ninguna relación de orden o secuencia
Además suelen tener operaciones para operar con ellos
• intersección
• unión
• diferencia

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

18

Operaciones básicas de los conjuntos

UNIVERSIDAD
DE CANTABRIA

argumentos

retorna

errores

elemento
incompatible
elemento
incompatible

elemento
incompatible

operación
constructor
añade

elElemento

Conjunto
booleano

borra

elElemento

booleano

hazNulo
pertenece

estaVacio
tamaño
iterador

elElemento

booleano

booleano
entero
Iterador

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

19/oct/09

19

Notas:

UNIVERSIDAD
DE CANTABRIA

Las operaciones básicas son idénticas a las de las colecciones, con la excepción de añade:

• constructor: Crea el conjunto con cero elementos
• añade: Si elElemento ya pertenece al conjunto retorna false. En caso contrario, añade el
parámetro elElemento al conjunto y retorna true. Si elElemento es incompatible con los
elementos que se almacenan en este conjunto lanza una excepción
• borra: Si existe en el conjunto al menos una instancia de elElemento, la borra del conjunto y retorna
true. En otro caso, retorna false
• hazNulo: Elimina todos los elementos del conjunto, dejándolo vacío
• pertenece: Si existe en el conjunto al menos una instan