UNITEC SUR Prof. Ing. José Luis Lozoya Vázquez

2.1Definición.

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.

2.2Especificacion

Cuando se usa en un programa de computación, un TDA es representado por su interfaz, la cual sirve como cubierta a la correspondiente implementación. Los usuarios de un TDA tienen que preocuparse por la interfaz, pero no con la implementación, ya que esta puede cambiar en el tiempo y afectar a los programas que usan el TDA. Esto se basa en el concepto de Ocultación de información, una protección para el programa de decisiones de diseño que son objeto de cambio.

La solidez de un TDA reposa en la idea de que la implementación está escondida al usuario. Solo la interfaz es pública. Esto significa que el TDA puede ser implementado de diferentes formas, pero mientras se mantenga consistente con la interfaz, los programas que lo usan no se ven afectados.

2.3Implantación.

Hay una diferencia, aunque a veces sutil, entre el Tipo de Dato Abstracto y la Estructura de Dato usada en su implementación. Por ejemplo, un TDA de una lista puede ser implementado mediante un Arreglo o una Lista Enlazada o hasta un Árbol binario de búsqueda. Una lista es un Tipo de Dato Abstracto con operaciones bien definidas (agregar elemento, agregar al final, agregar al principio, recuperar, eliminar, etc) mientras una lista enlazada es una estructura de datos basada en punteros o referencias (dependiendo del lenguaje) que puede ser usada para crear una representación de una Lista. La Lista Enlazada es comúnmente usada para representar una TDA Lista, y a veces, hasta confundida. Un ejemplo es la clase Linked List de Java, la cual ofrece una gran cantidad de métodos que no corresponden a una Lista Enlazada "pura", sino a un fuerte TDA.

De forma similar, un TDA Árbol binario de búsqueda puede ser representado de muchas maneras: Árbol binario, Árbol AVL, Árbol rojo-negro, Arreglo, etc. A pesar de la implementación un Árbol binario siempre tiene las mismas operaciones (insertar, eliminar, encontrar, etc.)

Separar la interfaz de la implementación no siempre significa que el usuario ignora totalmente la implementación de la rutina, pero lo suficiente para no depender de ningún aspecto de la implementación. Por ejemplo, un TDA puede ser creado usando un script o cualquiera que pueda ser decompilado (como C).

En la terminología de Lenguaje Orientado a Objeto, un TDA es una clase; un instancia de un TDA o clase, es un objeto.

2.4Aplicaciones.

Algunos ejemplos de utilización de TDAs en programación son:

    * Conjuntos: Implementación de conjuntos con sus operaciones básicas (unión, intersección y diferencia), operaciones de inserción, borrado, búsqueda...
    * Árboles Binarios de Búsqueda: Implementación de árboles de elementos, utilizados para la representación interna de datos complejos. Aunque siempre se los toma como un TDA separado son parte de la familia de los grafos.
    * Pilas y Colas: Implementación de los algoritmos FIFO y LIFO.
    * Grafos: Implementación de grafos; una serie de vértices unidos mediante una serie de arcos o aristas.