ED Icon

Estructuras de Datos

Definición e implementación de una colección

Definición e implementación de una colección

Definiendo la interfaz genérica colección.

* * *

TDA Colección

Definición del tipo de dato

  • Definición del TDA Coleccion

    Recuerde que para definir Tipos de Datos Abtractos (TDA) haremos uso de interfaces. En este caso, debemos definir una interfaz Coleccion. La interfaz Coleccion debe permitir las operaciones insertar, eliminar, consultar la existencia de un elemento, y el listado de todos los elementos dentro de la colección. Recordemos que los elementos serán genéricos, esto es, serán definidos en tiempo de ejecución.

  • Elementos genéricos

    Para que la interfaz permita modelar las operaciones por sobre elementos genéricos, haremos uso de generidad paramétrica. Recordemos que la genericidad paramétrica nos permite definir un tipo de dato genérico en tiempo de compilación que será instanciado luego en tiempo de ejecución. En el TDA Colección, el tipo de dato genérico lo nombraremos E.

  • ¿Importa con qué será implementada luego la interfaz?

    No. Justamente la finalidad que tiene la definición de un TDA mediante una interfaz, es abstraerse totalmente de las cuestiones particulares que existen cuando se implementan las operaciones. Un TDA define el conjunto de operaciones que se pueden aplicar por sobre un conjunto de datos. En este sentido, el TDA Colección define qué se puede hacer sobre sus datos: insertar, eliminar, consultar la existencia de un elemento, así como listar todos los elementos de la colección. Cómo estas operaciones luego estarán definidas, dependerá de las implementaciones particulares que surjan para este TDA.

  • Semántica de la colección

    Más allá de que a través de la interfaz no se puede explicitar, consideraremos a la colección como si fuese un conjunto, esto es, una colección infinita de elementos sin repeticiones.

TDA Colección

Definición del tipo de dato

A continuación se puede observar el código fuente utilizado para definir el TDA Colección, haciendo uso de una interfaz.

  • Package Colección

    Package Colección 
									
package Coleccion;

public interface Coleccion<E> {
	public void insertar(E elemento);
	public boolean pertenece (E elemento);
	public void eliminar (E elemento);
	public void mostrar();
}

Definición e implementación de una colección

Implementando el TDA Colección con un vector.

* * *

TDA Colección

Implementación mediante un Vector

  • Implementación mediante un Vector

    Para que el TDA Colección pueda ser utilizado, no alcanza simplemente con definir las operaciones aplicables sobre él, sino que hay que ofrecer una clase que se encargue de implementar el comportamiento a través de una Estructura de Datos y un conjunto de algoritmos. En este caso, daremos sustento a las operaciones del TDA Colección mediante un clase ColeccionConVector, que internamente manipulará un Vector para proveer de la funcionalidad requerida.

  • Clase Vector

    La clave Vector de Java provee de muchas funcionalidades que serán útiles a la hora de implementar las operaciones del TDA Coleccion. Por ejemplo, el Vector permite ser definido para un conjunto de elementos genéricos. En nuestro caso, el Vector contendrá elementos de tipo E, esto es, los elementos de un tipo genérico que luego el cliente de la clase definirá en tiempo de ejecución. Además de esto, la clase Vector provee de métodos tales como add(), remove(), contains(), a través de los cuales fácilmente se dará implementación a las operaciones contempladas en el TDA Coleccion.

TDA Colección

Implementación del tipo de dato

A continuación se puede observar el código fuente utilizado para implementar el TDA Colección, haciendo uso de un Vector como estructura de datos interna.

  • Package Colección

    Package Colección 
									
package Coleccion;

import java.util.Vector;

public class ColeccionConVector<E> implements Coleccion<E>{
	
	private Vector<E> vector;
	
	public ColeccionConVector(){
		vector = new Vector<E>();
	}
	
	public void insertar(E elemento) {
		if (! vector.contains(elemento) )
			vector.add(elemento);
	}

	public boolean pertenece(E elemento) {
		return vector.contains(elemento);
	}

	public void eliminar(E elemento) {
		vector.remove(elemento);
	}
	
	public void mostrar(){
		for(int i = 0; i<vector.size(); i++)
			System.out.println("Coleccion["+(i+1)+"]= " + vector.elementAt(i));
	}
}

Definición e implementación de una colección

Implementando el TDA Colección con un arreglo.

* * *

TDA Colección

Implementación mediante un arreglo

  • Implementación mediante un arreglo

    Para que el TDA Colección pueda ser utilizado, no alcanza simplemente con definir las operaciones aplicables sobre él, sino que hay que ofrecer una clase que se encargue de implementar el comportamiento a través de una Estructura de Datos y un conjunto de algoritmos. En este caso, daremos sustento a las operaciones del TDA Colección mediante una clase ColeccionConArreglo, que internamente manipulará un arreglo para proveer de la funcionalidad requerida.

  • Diferencia entre la implementación de la colección con Vector y con arreglo.

    Existe una diferencia notable entre la implementación del TDA Coleccion con un Vector frente a la que daremos con un arreglo. Como hemos notado, la implementación del TDA Coleccion con un Vector contaba con la facilidad que todas las operaciones del TDA fueron delegadas a la clase Vector, esto es, el comportamiento definido en la clase ColeccionConVector fue relativamente simple de resolver dado que para el acometido de una operación simplemente se tuvo que solicitar auxilio a una operación de la clase Vector que resolvía tal operatoria (por ejemplo, para resolver pertenece() se utilizó contains() de la clase Vector, así como para la operación insertar() se hizo uso de la operación add() de la clase Vector). Al manipular internamente un arreglo, deberemos hacernos cargo de:

    • - La creación y manipulación del arreglo y sus elementos.

    • - Garantizar que el arreglo tenga capacidad siempre que se desee insertar un elemento: como el arreglo tiene un tamaño fijo, al momento de que este se llene se deberá tomar los recaudos necesarios para redimensionar el mismo de forma tal de asegurar que el comportamiento del TDA Colección con la semántica de conjunto se mantenga.

TDA Colección

Implementación del tipo de dato

A continuación se puede observar el código fuente utilizado para implementar el TDA Colección, haciendo uso de un arreglo como estructura de datos interna.

  • Package Colección

    Package Colección 
									
package Coleccion;

public class ColeccionConArreglo<E> implements Coleccion<E>{

	private E [] arreglo;
	private int cantidad;
	private final int capacidad_inicial = 100;
	
	@SuppressWarnings("unchecked")
	public ColeccionConArreglo(){
		arreglo = (E[]) new Object[capacidad_inicial];
		cantidad = 0;
	}
	
	public void insertar(E elemento) {
		// Si el arreglo no tiene más capacidad, debe redimensionarse.
		if (cantidad == arreglo.length )
			resize();
		
		// Chequeo para evitar elementos duplicados.
		if (! pertenece(elemento) )
			arreglo[cantidad++] = elemento;
	}

	
	public boolean pertenece(E elemento) {
		boolean pertenece = false;
		for(int i=0; i<cantidad && !pertenece; i++)
			pertenece = (arreglo[i].equals(elemento));
		return pertenece;
	}

	
	public void eliminar(E elemento) {
		boolean encontre = false;
		
		for(int i=0; i<cantidad && !encontre; i++){
			if (arreglo[i].equals(elemento)) {
				desplazar_izquierda_desde(i);
				encontre = true;
				cantidad--;
			}
		}
	}
	
	public void mostrar(){
		for(int i = 0; i<cantidad; i++)
			System.out.println("Coleccion["+(i+1)+"]= " + arreglo[i]);
	}
	
	@SuppressWarnings("unchecked")
	private void resize(){
		E [] arreglo_aux = (E[]) new Object[arreglo.length * 2];
				
		for(int i=0; i<cantidad; i++)
			arreglo_aux[i] = arreglo[i];
		arreglo = arreglo_aux;
	}
	
	private void desplazar_izquierda_desde(int indice){
		while(indice+1 < arreglo.length){
			arreglo[indice] = arreglo[indice+1];
			indice++;
		}
		arreglo[indice] = null;
	}
}
Closing image
Photo by Helloquence on Unsplash

Fin de la presentación

Slides generadas mediante la herramienta Open Source @webslides.