Tipo de datos abstractos y estructura de datos

Es bastante difícil para mí entender estos términos. Busqué en Google y leí un poco en Wikipedia, pero todavía no estoy seguro. Hasta ahora he determinado que:

Abstract Data Type es una definición de nuevo tipo, describe sus propiedades y operaciones.

Estructura de datos es una implementación de ADT. Muchos ADT se pueden implementar como la misma Estructura de datos.

Si lo considero correcto, array como ADT significa una colección de elementos y como Data Structure, cómo se almacena en una memoria. Stack es ADT con operaciones push, pop, pero ¿podemos decir acerca de la estructura de datos de la pila si quiero decir que usé stack implementado como una matriz en mi algoritmo? ¿Y por qué el montón no es ADT? Se puede implementar como árbol o como matriz.

En pocas palabras, un ADT (tipo de datos abstractos) es más una descripción lógica, mientras que una estructura de datos es concreta.

Piense en un ADT como una imagen de los datos y las operaciones para manipularlo y cambiarlo.

Una estructura de datos es lo real y concreto . Se puede implementar y usar dentro de un algoritmo.

ADT es para una interfaz ( lo que hace ) lo que es una estructura de datos para una clase ( cómo lo hace ).

Algunos ejemplos:

ADT: List
DS:  ArrayList, LinkedList...

ADT: Map
DS:  HashMap, TreeMap...

Supongo que entiendes el punto.

Tipo de datos abstractos: ADT puede definirse como un conjunto de valores de datos y operaciones asociadas que se especifican con precisión independientemente de cualquier implementación particular. Por lo tanto, un tipo de datos abstractos es una recopilación organizada de información y un conjunto de operaciones utilizadas para administrar esa información. El conjunto de operaciones define la interfaz de ADT. Mientras el ADT cumpla con las condiciones de la interfaz, realmente no importa cómo se implemente el ADT. Dado que, en ADT, los valores de datos y las operaciones se definen con precisión matemática, en lugar de como una implementación en un lenguaje de computadora, podemos razonar sobre los efectos de las operaciones, las relaciones con otros tipos de datos abstractos si un programa implementa el tipo de datos, etc.

La diferencia básica entre el tipo de datos abstractos (ADT) y el tipo de datos concreto es que este último nos permite ver la representación concreta, mientras que el primero nos oculta la representación. Un ADT puede ser ADT puro o ADT actualizable. Un ADT puro es aquel en el que todas las operaciones son funciones puras. Esto significa que las operaciones no tienen efectos secundarios. En particular, no modifican ni actualizan sus argumentos de entrada. Solo usan estos argumentos para generar resultados, que son valores nuevos de ADT (o de otros tipos). La mayoría de los tipos de concreto son puros. Por ejemplo, ninguna operación en enteros en realidad modifica un entero. En cambio, todas las operaciones como '+' producen nuevos resultados.

Un ADT actualizable es aquel en el que algunas operaciones realmente cambian los valores del ADT. Por ejemplo, supongamos que tenemos una operación llamada 'pop' que toma una pila como argumento y la modifica. ("En el lugar", "destructivamente") eliminando el elemento de mayor prioridad. Esta operación se consideraría impura y todo el ADT también sería impuro. Un ADT puede ser un ADT definido por el usuario.

Sabemos que un tipo de datos abstractos es un tipo de datos que cumple las dos condiciones siguientes:

1. La representación, o definición, del tipo y las operaciones están contenidas en una sola unidad sintáctica.

2. La representación de los objetos del tipo está oculta de las unidades de programa que usan el tipo, por lo que solo las operaciones directas posibles en esos objetos son aquellas proporcionadas en la definición del tipo.

Un tipo de datos abstractos definido por el usuario debe proporcionar:

1. Una definición de tipo que permite a las unidades del programa declarar variables del tipo, pero oculta la representación de estas variables.

2. Un conjunto de operaciones para manipular objetos del tipo.

Un ejemplo de un tipo de datos abstracto definido por el usuario es la estructura. 'C' proporciona cuatro tipos básicos: int, char, float y double. Sin embargo, 'C' también proporciona al programador la capacidad de definir sus propios tipos. La estructura es uno de esos ejemplos. Una estructura es un agregado de diferentes partes, donde cada parte es de algún tipo existente.

struct abc

{int x;

float y;

};

La definición de estructura anterior no crea ninguna variable, sino que crea un nuevo tipo. Las variables de este tipo pueden crearse de manera similar a las variables de un tipo incorporado.

struct abc a;

La palabra clave typedef nos permite crear nuevos nombres de tipo para nuestros nuevos tipos.

Por ejemplo:

typedef struct abc AB;

donde AB es un nuevo nombre de tipo que ahora se puede usar para crear nuevos tipos.

AB b;

Estructuras de datos: Las siguientes son las características de las estructuras de datos:

1. Contiene elementos de datos de componentes, que pueden ser atómicos u otra estructura de datos (aún un dominio).

2. Un conjunto de operaciones en uno o más de los elementos componentes.

3. Define reglas sobre cómo los componentes se relacionan entre sí y con la estructura como un todo (aserciones).

Estructuras de datos:

Una estructura de datos puede ser estática o dinámica. Una estructura de datos estática tiene un tamaño fijo. Este significado es diferente del significado del modificador estático. Las matrices son estáticas; Una vez que definimos el número de elementos que puede contener, el número no cambia. Una estructura de datos dinámica crece y se reduce en el tiempo de ejecución según lo requiera su contenido. Una estructura de datos dinámica se implementa mediante enlaces.

Las estructuras de datos se pueden clasificar además en estructuras de datos lineales y estructuras de datos no lineales. En las estructuras de datos lineales, cada componente tiene un predecesor y sucesor único, excepto el primer y el último elemento, mientras que en el caso de las estructuras de datos no lineales, no existe tal restricción, ya que los elementos se pueden organizar de la forma deseada restringida por la forma en que usamos representar tales tipos.

En primer lugar, las terminologías en las estructuras de datos pueden ser muy confusas.

ADT es como teoría o modelo o directriz, etc., que indica cómo debe comportarse una estructura de datos, qué tipo de operaciones debe admitir, etc. Tres tipos de datos abstractos fundamentales son contenedores, diccionarios y colas de prioridad. Por ejemplo, el diccionario, nos dice que cada estructura de datos que implementa este ADT del diccionario debe admitir pares clave-valor, búsqueda basada en claves, inserción de elementos, búsqueda de sucesor y predecesor de una clave determinada, etc.

Ahora todo lo demás que implementa este ADT anterior es la Estructura de datos (DS) , la estructura de datos son cosas reales que implementa en sus problemas y encuentra dentro de las bibliotecas. En el caso del diccionario, puede optar por implementarlo a través de Array o Lista enlazada.

Creo que surge una verdadera confusión cuando alguien nombra su DS como ADT, por ejemplo, algunas personas llamarán a su DS mencionado anteriormente como 'Diccionario' en lugar de DictImplementation, que es perfectamente legal, solo causa cierta confusión.

Ref: Skiena: el manual de diseño de algoritmos