Tipos Abstractos de Datos (TAD) y sus Implementaciones
Enviado por Chuletator online y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 11,8 KB
Tipos Abstractos de Datos (TAD)
Un Tipo Abstracto de Datos (TAD) es un conjunto de valores y operaciones especificados de forma precisa e independiente de su implementación. El objetivo principal de un TAD es separar la interfaz de la implementación.
La notación de un TAD se basa en el estado del TAD dado por una secuencia de operaciones sobre él.
TAD STRING
Un TAD STRING es una secuencia ordenada de caracteres definidos por un alfabeto. Se considera un tipo simple especial.
Las operaciones básicas de un TAD STRING incluyen:
- Creación
- Concatenación
- Extracción
- Inserción
- Búsqueda de subcadenas
Existen dos tipos de strings:
- Mutables: Su contenido interno puede ser modificado.
- Inmutables: Su contenido interno no puede ser modificado.
Las implementaciones más comunes de un TAD STRING son:
- Arrays
- Ropes
- Tries
- Árboles
TAD CONTENEDOR
Un TAD CONTENEDOR almacena información sobre varios elementos. No es necesario que el almacenamiento sea físico, ya que puede almacenar referencias a los elementos.
Los TAD CONTENEDOR se pueden clasificar según:
- Almacenamiento de elementos: Atómicos o en partes
- Manejo de elementos: Con o sin equivalencia/comparación
- Elementos repetidos: Permitidos o no permitidos
- Relación entre elementos: Con o sin relación
- Orden de los elementos: Orden externo o interno
Implementación de contenedores
Las implementaciones más comunes de un TAD CONTENEDOR son:
- Arrays
- Referencias a elementos (punteros, objetos, índices de posición en un array, nombre de fichero)
- Funciones de resumen o dispersión (traducen el valor de un elemento a un número)
Colección
Una colección es una fuente de datos de la que se obtiene un iterador para acceder a sus datos.
Iterador
Un iterador es un mecanismo que permite acceder a un elemento de una colección y pasar al siguiente. Su objetivo es proporcionar un mecanismo uniforme de acceso a una fuente de datos.
Las operaciones básicas de un iterador son:
- Comprobar si quedan elementos por recorrer
- Acceder al elemento actual
- Pasar al elemento siguiente
- Borrar el elemento actual
TAD CONJUNTO
Un TAD CONJUNTO es una colección de valores sin orden definido, donde no se permiten elementos repetidos. Los conjuntos sirven para clasificar valores en dos categorías: pertenecen o no pertenecen al conjunto.
Las operaciones básicas de un TAD CONJUNTO son:
- Pertenencia
- Inclusión
- Exclusión
- Unión
- Intersección
- Diferencia
- Recorrido
Implementación de conjuntos
Las implementaciones más comunes de un TAD CONJUNTO son:
- Arrays de bits indexados por valor
- Tablas de dispersión
- Contigua lineal
- Árboles binarios
- Opciones exóticas (tries, bloom)
TAD LISTA
Un TAD LISTA es una colección ordenada de entidades, donde existe una relación de orden y no se permiten elementos repetidos. Si el orden es interno, se denominan listas ordenadas.
Implementación de listas
Las implementaciones más comunes de un TAD LISTA son:
- Listas (contigua lineal, contigua circular, listas enlazadas)
- Listas ordenadas (contigua lineal ordenada, árboles binarios de búsqueda, ABB equilibrados, skip lists o splay trees)
- Colas de prioridad (montículos binarios, binomiales, fibonacci, treaps)
TAD MAPA
Un TAD MAPA es un TAD compuesto por un conjunto de claves y una colección de valores, donde cada clave tiene asociado un valor. Es una generalización de un conjunto, donde los elementos son pares (clave, valor). No se permiten claves repetidas y las claves no necesitan tener una relación de orden entre ellas.
Implementación de mapas
Las implementaciones de un TAD MAPA son las mismas que las de un TAD CONJUNTO.
TAD DICCIONARIO
Un TAD DICCIONARIO es un mapa con orden interno sobre las claves. Tiene operaciones asociadas tanto al TAD MAPA como al TAD LISTA ORDENADA.
Implementación de diccionarios
Las implementaciones de un TAD DICCIONARIO son las mismas que las de un TAD LISTA ORDENADA.
Tipos de Relaciones
Precedencia u Orden
Existe un orden total sobre los elementos, con dos extremos: primero y último. Todo elemento, salvo el primero, tiene un predecesor y todo elemento, salvo el último, tiene un sucesor. El orden puede ser interno o externo.
Parentesco o Jerarquía
Existe una estructura jerárquica con una raíz, padres e hijos. Hay más de una forma de recorrer los elementos. El orden es interno.
Vecindad o Grafo
No hay restricciones en la forma de la relación. Cada elemento puede relacionarse con 0 o más elementos. No hay elementos distinguidos ni un recorrido distinguido.
Clasificación de Operaciones Básicas
| TAD | Descripción |
|---|---|
| Conjunto | Acceso o borrado por valor del elemento (pertenencia), inserción según valor. |
| Mapa | Acceso o borrado por valor de la clave del dato asociado, inserción según valor. |
| Lista indexada | Acceso o borrado por posición (índice o iterador de la lista), inserción en posición (índice). |
| Pila | Acceso o borrado por posición (extremo cabeza), inserción en posición (extremo cabeza). |
| Cola | Acceso o borrado por posición (extremo cabeza), inserción en posición (extremo cola). |
| Bicola | Acceso o borrado por posición (extremo cabeza o cola), inserción en posición (extremo cabeza o cola). |
| Lista ordenada | Acceso o borrado por orden (i-ésimo menor), inserción según valor. |
| Cola de prioridad | Acceso o borrado por orden (extremo mínimo), inserción según valor. |
| Diccionario | Acceso o borrado por valor de la clave del dato asociado o por orden (i-ésimo menor), inserción según valor. |
Otros TADs
TAD DIRECTORIO
Un TAD DIRECTORIO es una colección de elementos con una relación de jerarquía, como por ejemplo un sistema de ficheros. Las operaciones de acceso se basan en un cursor. Las implementaciones más habituales son enlazadas (padre-hijo-hermano).
TAD GRAFO
Un TAD GRAFO es una colección de elementos sobre los que existe una relación de vecindad definida por aristas, como por ejemplo la World Wide Web. Las operaciones habituales son la inserción y borrado de aristas y nodos, recorridos, etc. Las implementaciones más comunes son listas de adyacencia y matrices de adyacencia.
TAD MULTICONJUNTO
Un TAD MULTICONJUNTO es un conjunto en el que se permiten elementos repetidos. La operación de acceso devuelve un entero con el número de veces que aparece un elemento en el multiconjunto. La operación de borrado disminuye en uno el número de veces que aparece un elemento en el multiconjunto.
TAD MULTIDICCIONARIO
Un TAD MULTIDICCIONARIO es un diccionario en el que se asocian múltiples valores (nunca uno solo) a cada clave. La operación de acceso por clave devuelve una lista de valores. La inserción de un par añade un nuevo valor a la lista de valores. La operación de borrado incluye un parámetro adicional que selecciona el valor concreto que se quiere borrar.
TAD ARRAY
Un TAD ARRAY tiene operaciones de acceso por índice y de reemplazo de elementos.
TAD DISJOINT-SET
Un TAD DISJOINT-SET representa elementos clasificados en categorías y establece una partición entre ellos.
Diferencia entre TAD y Representación
Un TAD define las operaciones fundamentales, la relación entre elementos y las restricciones, mientras que una representación define cómo se almacenan los elementos en memoria y puede establecer una relación de precedencia o jerarquía entre ellos y añadir restricciones.
Secuencias
Existen diferentes tipos de secuencias:
- Ordenadas (orden interno)
- No ordenadas (orden externo)
- Contiguas o enlazadas
- Lineales o circulares
Representaciones Contiguas
- Contigua lineal: Un array de capacidad m que almacena n elementos en sus primeras posiciones.
Eficiencia de TADs
Conjunto/Mapa
| Operación | Contigua | Contigua Ordenada | Enlazada | Enlazada Ordenada | Array de Bits |
|---|---|---|---|---|---|
| Pertenencia | O(n) | O(log n) | O(n) | O(n) | O(1) |
| Borrado (valor) | O(n) | O(n) | O(n) | O(n) | O(1) |
| Borrado (iterador) | O(n) | O(n) | O(1) | O(1) | O(1) |
| Inserción | O(1) | O(n) | O(1) | O(n) | O(1) |
| Unión | O(n) | O(n) | O(n^2) | O(n) | O(m) |
| Espacio | O(n) | O(n) | O(n) | O(n) | O(m) |
Lista
| Operación | Contigua | Enlazada Lineal | Enlazada Circular |
|---|---|---|---|
| Acceso (índice) | O(1) | O(n) | O(n) |
| Acceso (iterador) | O(1) | O(1) | O(1) |
| Borrado (índice) | O(n) | O(n) | O(n) |
| Borrado (iterador) | O(n) | O(1) | O(1) |
| Inserción (índice) | O(n) | O(n) | O(n) |
| Inserción (iterador) | O(n) | O(1) | O(1) |
| Búsqueda | O(n) | O(n) | O(n) |
| Concatenación | O(n) | O(n) | O(1) |
Pila/Cola/Bicola
| Operación | Contigua Lineal | Contigua Circular | Enlazada Simple Lineal | Enlazada Simple Circular | Enlazada Doble Circular |
|---|---|---|---|---|---|
| Acceso (primero) | O(1) | O(1) | O(1) | O(1) | O(1) |
| Acceso (último) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Borrado (primero) | O(n) | O(1) | O(1) | O(1) | O(1) |
| Borrado (último) | O(1) | O(1) | O(n) | O(n) | O(1) |
| Inserción (principio) | O(n) | O(1) | O(1) | O(1) | O(1) |
| Inserción (final) | O(1) | O(1) | O(n) | O(1) | O(1) |
Lista Ordenada/Cola de Prioridad
: 1acceso minimo 2acceso iesimo menor 3borrado minimo 4borrado iesimo menor 5borrado iterador 6insercion valor 7busqueda 8fusion: contigua ordenada->O1O1O1OnOnOnOlognOn enlazada ordenada O1OnO1OnO1OnOnOn contigua-> O1OnOnOn-O1OnOn Diccionario:1accesoclave 2accesoclaveiesimamenor 3accesoiterador 4borradoclave 5borradoclaveiesimamenor 6borradoriterador 7insercionvalor contigua ordenada-> OlognO1O1OnOnOnOn enlazada ordenada OnOnO1OnOnO1On