Cap2 Lineales 2en1

Estructuras de datos y algoritmos

UNIVERSIDAD
DE CANTABRIA

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

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

© Michael González Harbour
19/oct/09

1

UNIVERSIDAD
DE CANTABRIA

2. Estructuras dedatos 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

UNIVERSIDAD
DE CANTABRIA

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

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

© Michael González Harbour
19/oct/09

3

Operaciones básicas de las colecciones
operación

argumentos

retorna

UNIVERSIDAD
DE CANTABRIA

errores

constructor
añade

Colección
elElemento

borra

elElemento

booleano

elemento
incompatible

elElementobooleano

elemento
incompatible

elemento
incompatible

hazNula
pertenece
estaVacia

booleano

tamaño

entero

iterador

Iterador

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 incompatiblecon 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, retornafalse
• 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

Las colecciones en Java

5

UNIVERSIDAD
DECANTABRIA

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
- 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 nose ha modificado

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

© Michael González Harbour
19/oct/09

6

La interfaz Collection

UNIVERSIDAD
DE CANTABRIA

public interface Collection
extends Iterable
{
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element);
//optional
boolean remove(Object element); //optional
Iteratoriterator();

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

© Michael González Harbour
19/oct/09

La interfaz Collection (cont.)

7

UNIVERSIDAD
DE CANTABRIA

// Bulk operations
boolean containsAll(Collection c);
boolean addAll(Collection c);
//optional
boolean removeAll(Collection c);
//optional
boolean retainAll(Collection c);
//optional
void clear();
//optional
// Arrayoperations
Object[] toArray();
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

UNIVERSIDAD
DE CANTABRIA

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

© Michael González Harbour...

Leer documento completo

Regístrate para leer el documento completo.