Tipo de Dato Abstracto

Tipo de dato abstracto

Tipo de Dato Abstracto (TDA). Es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo.

Caracterización

Un TDA se caracteriza por:

1. Exportar un tipo (una clase lo es)
2. Definir un conjunto de operaciones para la manipulación (la interfase, el conjunto de métodos tanto públicos como protegidos que pueden ser utilizados).
3. Utilizar la interfase como único mecanismo de acceso a la estructura de datos (encapsular, esconder el cómo).

Ejemplos

• TDA: entero es.
• Datos: una secuencia de dígitos que ocasionalmente presentan como prefijo un signo más(+)o menos(–). A esta secuencia le damos el nombre de n.

Operaciones

• Suma (entero K): crea un nuevo entero resultado de la suma de n y k.
• Resta (entero K): crea un nuevo entero resultado de la resta de n y k.
• Multiplicar(entero K): crea un nuevo entero resultado de la multiplicación n y k.
• Dividir(entero K): crea un nuevo entero resultado de la división n y k.
• Resto(entero K): crea un nuevo entero, el resto la división de n y k.
• Obtener: devuelve a n.
• Poner(entero K): pone en n el valor de k.

Lista TDA

Una lista se define como una n-tupla de elementos (donde li es el i-ésímo elemento de la lista) ordenados de forma consecutiva, o sea, el elemento li le precede al elemento li+1.

• L= ( l1, l2, … , ln ).

El valor de i representa la posición del elemento en la lista. Si la lista contiene 0 elementos se denomina lista vacía.

TDA Lista es

• Datos: una colección ordenada de elementos del mismo tipo. La llamaremos: 1
• Operaciones
• Constructor: crea una nueva lista, la crea vacía.
• Insertar(Tipo x, Entero i): insertar un nuevo elemento x, en la posición i de la lista.
• Adicionar (Tipo x): adiciona un elemento al final de la lista.
• Tipo Obtener (Entero i): devuelve el elemento que está en la posición 1 de la lista.
• Eliminar (Entero i): elimina el elemento que está en la posición 1 de la lista. Los elementos posteriores a partir de la posición i+1 pasan a tener la posición anterior inmediata es decir 1
• Entero Longitud: devuelve la cantidad de elementos de la lista. Si la lista es vacía devuelve el valor cero.
• Lógico vacía: devuelve un valor lógico verdadero si la lista tiene longitud cero, falso en caso contrario.

Fuentes

• Fundamentals of Data Structures in C++. E. Horowitz, S. Sanhi, D. Mchta. Computer Science Press, 1995.
• Data structures and algorithms. Aho .et al.