tipo de dato asbtracto

Tipo de dato abstracto (TAD)

Un tipo de dato abstracto (TDA) o Tipo abstracto de datos (TAD) es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo.

TAD Lista

*Tenemos que definir las operaciones que queremos para manipular una lista.
* Por ejemplo, podemos querer ver los elementos de una lista, borrar todos sus elementos,insertar un elemento, eliminar el elemento que se encuentra en una determinada posicion.
*Vamos a definir el TAD lista de forma paramétrica, es decir, sin especificar de que tipo son los elementos de la lista.
*La ventaja de esto es que definiendo el TAD una única vez podemos contar con listas que contengan distintos tipos.
*Si bien no especificamos el tipo, podemos necesitar que estecumpla algunas Condiciones

TAD LISTA

Constructores:

LISTA listaVacia()
insertar(ENTSAL LISTA lalista, ENT ELEMENTO elem)

Observadores basicos:

entero tamaño(LISTA lalista)
ELEMENTO elemento(LISTA lalista, entero i )

Otras operaciones:

borrarLista(ENTSAL LISTA lalista)
insertarEn(ENTSAL LISTA lalista, ENT ELEMENTO elem, ENT
entero i )
borrarEl(ENTSAL LISTA lalista, ENTentero i)





TAD Lista
Según el uso, podemos necesitar una lista con mas funcionalidad, por ejemplo que pueda saber si un determinado elemento se encuentra en la lista o borrar un elemento particular. Para esto, necesitamos pedir que ELEMENTO tenga definida la igualdad
entre dos expresiones del tipo.


TAD SLISTA

ELEMENTO con igualdad

Otras operaciones:

entero buscar(SLISTAlalista, ELEMENTO elem)

Postcondicion: Retorna la primera posicion de la lista que contiene
a elem si existe y tamaño(lalista) en caso contrario.

borrar(ENTSAL SLISTA lalista, ENT ELEMENTO elem)

Postcondicion: Elimina de lalista la primera aparicion del elemento
elem si _este existe. En caso positivo, el tama~no de la lista
disminuye en 1 y los elementos que se encontraban en lasposiciones posteriores se desplazan un lugar hacia adelante


TAD Lista: ejemplo de uso

LISTA mispolinomios

POLI2 elnuevo
elnuevo - suma(crearPoli(),crearPoli(2.5))
insertar(mispolinomios,elnuevo)






















Definición del TAD Lista Ordenada

El siguiente listado muestra las operaciones que se pueden realizar sobre una lista ordenada, y los parámetrosde entrada y salida de cada una. Se puede observar que todas reciben como entrada la lista sobre la que se realiza la operación. Exceptuando ElemActual y ListaLlena, todas las operaciones realizan cambios en el estado interno de la lista, y por lo tanto devuelven la lista modificada, por eso utilizan un paso por variable.

procedure Inicializar(var L: TListaOrd; fMenorIgual: TFuncComp);procedure Destruir(var L: TListaOrd);
function ListaLlena(L: TListaOrd) : boolean;
function ElemActual(L: TListaOrd) : pointer;
procedure IrAInicio(var L: TListaOrd);
procedure IrASiguiente(var L: TListaOrd);
procedure Buscar(var L: TListaOrd; Elem: pointer);
procedure Insertar(var L: TListaOrd; Elem: pointer);
procedure Reordenar(var L: TListaOrd; fMenorIgual: TFuncComp);


A continuaciónse muestra una tabla con las precondiciones y postcondiciones de cada operación. En principio, se puede asumir que las precondiciones representan los requisitos que se deben cumplir antes de llamar a esa operación, y por lo tanto son condiciones que debe garantizar el programa que desee utilizar esa operación. Las postcondiciones representan, en cierto modo, el propósito u objetivo de laoperación, y son condiciones que la unidad que implementa el TAD garantiza que se van a cumplir tras la ejecución de la operación (siempre que se hallan cumplido las precondiciones).
En el tema 5 (Verificación) se verá una descripción más formal de las precondiciones y las postcondiciones, y de cómo se derivan de la técnica de programación bajo contrato










Operaciones Precondiciones...