SiguienteAnteriorContenido

0.1. El TAD Lista 

Una lista es una estructura que tiene una cabeza y una cola, gráficamente puede representarse así:

Representacion de una Lista

en  la cabeza de la lista hay información, la cola es otra lista (así que a su vez podrá tener cabeza y cola).   Existe además una lista vacía que no tiene cabeza ni cola.   Supongamos que denotamos la lista vacia como [], y una lista no vacia como [cabeza,cola].   Una lista que contenga los elementos 1,2 y 3 se representa como: [1,[2,[3,[]]]].  La cabeza de la lista tiene el 1 y la cola es una lista cuya cabeza es el dos, la cola de esta segunda lista es una tercera lista cuya cabeza tiene el tres y cuya cola es la lista vacía.
 

La lista completa vista como TAD podría ser:
Nombre del TAD
Información 
Operaciones
Lista Cabeza de la lista Nueva Lista 
Agregar un nodo 
Información de un nodo 
Eliminar un nodo

Cada nodo a su vez podría ser un TAD (inclusive el mismo TAD Lista).

Suelen clasificarse las operaciones de un TAD según su función.   Las operaciones en ManTa se clasifican en:

Si conoce algo de TADs notará que no hay destructoras (ManTa maneja la memoria con un recolector de basura).

Veamos el TAD Lista con sus operaciones clasificadas:

TAD Lst [X]

Inicializadoras inicLst: -> Lst Retorna una lista vacia
Constructoras adicLst:Lst x X -> Lst Agrega el elemento a la lista que recibe y retorna la nueva lista asi formada
Selectoras elimLst: Lst -> Lst Devuelve la lista recibida sólo que sin su primer elemento 
infoLst: Lst -> X Devuelve el primer elemento de la lista que recibe

La información de cada nodo de esta lista es un objeto del TAD X.   X es como siempre indefinido, así que esta lista es bastante "abstracta" y podrá usarse para hacer Listas de Naturales o Listas de Cadenas o Listas de Listas de Caracteres, o cualquier estructura que pueda imaginar y que requiera una lista.

Cada una de las operaciones del TAD es una función, que por tanto tiene  un dominio y un codominio.   En el caso de la inicializadora inicLst, el dominio es vacío y el codominio es el TAD (inicList puede pensarse como una constante del TAD: la lista vacía).  La constructora adicLst, recibe una lista y un elemento por adicionar y retorna otra lista (la original con el elemento adicionado).

El dominio y codominio de cada operación de un TAD, son importantes en ManTa, porque los necesitaremos cuando definamos un nuevo TAD.

La teoría de TADs es más completa (y compleja) de lo que se ha expuesto aquí, sin embargo esto por ahora bastará para que continúe estudiando este tutorial y haciendo los ejemplos propuestos con ManTa.  Si desea conocer más sobre TADs puede consultar [Vil96], si le gustaría ver una exposición formal le recomendamos [Car93].

En la siguiente sección, mostramos como emplear ManTa para definir, demostrar propiedades y generar un prototipo en C, del TAD Pila.



SiguienteAnteriorContenido