Tipo de Dato Abstracto
|
Tipo de Dato Abstracto (TDA)
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.
Un TDA se caracteriza por:
- Exportar un tipo (una clase lo es)
- 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).
- Utilizar la interfase como único mecanismo de acceso a la estructura de datos (encapsular, esconder el cómo).
Ejemplo:
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
TDA Lista
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.