Clase Lista.Fila.ArbolBinario.c++

Análisis y Diseño de Algoritmos I
Trabajo Práctico Especial 2014
Primera Parte
Facultad de Ciencias Exactas – UNCPB
Ingeniería de Sistemas


Fecha de entrega: 21/05/2014
Grupo Numero: 16
Integrantes: Franco Gabriel Pérez, Hugo Avendaño
Ayudante Asignado: Federico Améndola
e-mail: francogabrielperez@gmail.com
hugo.avendano@hotmail.com.ar


INDICE




Introducción
Un Tipo dedato abstracto (TDA) es un conjunto de datos u objetos al cual se le asocian operaciones. El TDA provee de una interfaz con la cual es posible realizar las operaciones permitidas, abstrayéndose de la manera en como estén implementadas dichas operaciones. Esto quiere decir que un mismo TDA puede ser implementado utilizando distintas estructuras de datos y proveer la misma funcionalidad.
En estaprimera parte del trabajo práctico especial se tiene como propósito especificar algebraicamente en lenguaje Nereus e implementar en C++ los tipos de datos básicos Lista, Fila y Árbol binario.

Tipos de Datos Abstractos:
Especificación algebraica en Nereus

CLASS Lista [Elemento]
IMPORTS Boolean, Natural
BASICS CONSTRUCTORS InicLista, AgregarLista
EFFECTIVE
TYPES
FUNCTIONSInicLista: → Lista
AgregarLista: Lista x Elemento → Lista
VaciaLista: Lista → Boolean
LongitudLista: Lista → Natural
PertenceLista: Lista → Boolean
EliminarLista: Lista x Elemento → Lista
EliminarListaPosicion: Lista (l) x Natural (i) → Lista
Pre: 0 < i < longitud (l)
ObtenerElemento: Lista (l) → Elemento
Pre: not VaciaLista (l)
AXIOMS
…
END-CLASS


CLASS Fila[Elemento]
IMPORTS Lista
BASICS CONSTRUCTORS InicFila, AgregarFila
EFFECTIVE
TYPES
FUNCTIONS
InicFila: → Fila
AgregarFila: Lista x Elemento → Fila
VaciaFila: Fila → Boolean
LongitudLista: Fila → Natural
EliminarFila: Fila (f) → Fila
Pre: not VaciaFila (f)
RecuperarFila: Fila (f) → Elemento
Pre: not VaciaFila (f)
AXIOMS
…
END-CLASS

CLASS ArbolBinario [Elemento]
IMPORTSLista, Cadena
BASIC CONSTRUCTORS InicArbin, CrearArbin, CargarCadena
EFFECTIVE
TYPES ArbolBinario
OPERATIONS
InicArbin: → ArbolBinario
AgregarArbin: ArbolBinario x Elemento → ArbolBinario
CargarCadena: Cadena → ArbolBinario
VacioArbin: ArbolBinario → Boolean
Pertenece: ArbolBinario x Elemento → Boolean
CantElem: ArbolBinario → Natural
Profundidad: ArbolBinario → Natural
Frontera:ArbolBinario → Lista
ListarElementos: ArbolBinario → Lista
AXIOMS
…
END-CLASS


TDA Lista
+ Estructura de Datos Utilizadas:
Para la implementación de este TDA se utilizó una estructura dinámica, más precisamente una lista simplemente vinculada por su fácil utilización y en especial por ser la estructura más eficiente para la implementación.

+ Funciones de la implementación y suscomplejidades:
Lista (): Es el constructor de la clase, solamente inicializa a los miembros en cero. Su complejidad pertenece al orden de O (1).
void agregarPrincipio (const T &elemento): carga un nuevo nodo con el elemento que recibe por parámetro y lo inserta al principio de la lista. Su complejidad pertenece al orden O (1).
void agregarFinal(const T &elemento): carga un nuevo nodo con elelemento que recibe como parámetro y lo inserta al final de la lista. Su complejidad pertenece al orden de O (1).
void agregar(int pos, const T &elemento): carga un nuevo nodo con el elemento que recibe por parametro y lo inserta en la posición que también recibe por parametro. Su complejidad pertenece al orden de O (n).
unsigned int obtenerLongitud () const: este método devuelve el tamaño de lalista. Su complejidad pertenece al orden de O (1).
bool pertence (const T &elemento) const: este método devuelve true en caso de que el elemento recibido por parametro exista en la lista y en caso contrario false. Su complejidad pertenece al orden O (n).
bool listaVacia () const: este método devuelve true en caso que no existan elementos en la lista y false en caso contrario. Su complejidad...