Tipos abstractos de datos (ADT) y estructuras de datos
Conceptos básicos sobre estructuras de datos
Definición
En un lenguaje de programación, un tipo de dato esta definido por el conjunto de valores que representa y por el conjunto de operaciones que se pueden realizar con dicho tipo de dato.
Por ejemplo, el tipo de dato entero en Java puede representar números en el rango de -2^31 a 2^31-1 y cuenta con operaciones como suma, resta, multiplicación, división, etc. En Python no existen tales limitaciones respecto a límites en valores, al menos en la versión 2, los enteros cambiarán automáticamente a Long, hacia la versión 3 desaparecieron cuando superen su límite y ya solo hay int o float, manteniendo precisión a pesar de la longitud.
Por otro lado, podemos decir que en la solución de un problema a ser procesado por un computador podemos encontrar dos grandes tipos de datos: datos simples y datos estructurados. Los datos simples son aquellos que, al ser representados por el computador, ocupan solo una casilla de memoria. Debido a esto, una variable de un tipo de dato simple hace referencia a
un único valor a la vez. Ejemplo de estos tipos de datos son los enteros, reales, caracteres y booleanos.
Asimismo, los datos estructurados se caracterizan por que su definición está compuesta de otros tipos de datos simples, así como de otros datos estructurados. En este caso, un nombre (identificador de la variable estructurada) hace referencia no solo a una casilla de memoria, sino a un grupo de casillas.
En programación, el término estructura de datos se utiliza para referirse a una forma de organizar un conjunto de datos que se relacionan entre si, sean estos simples o estructurados, con el objetivo de facilitar su manipulación y de operarlo como un todo. Por otro lado, tenemos el término Tipo de Dato Abstracto, o TDA, que es muy comúnmente utilizado como equivalente al término estructura de datos para referirse justamente a un tipo de dato estructurado que representa un concepto a través de la definición de sus características(datos que lo conforman) y de sus operaciones(algoritmos que manipulan los datos que lo conforman)
Operaciones usuales en TDA
Sobre una estructura de datos se puede efectuar diferentes tipos de operaciones, entre las más importantes dependiendo de la estructura de datos generalmente están:
- Inserción. Es aquella mediante la cual se incluye un nuevo elemento en la estructura.
- Modificación. Permite variar parcial o totalmente el contenido de la información de los elementos de la estructura.
- Eliminación. Como su nombre lo indica, es la que permite suprimir elementos de la estructura.
- Navegar por la estructura: Esta es una operación básica que garantiza que se puede recuperar información almacenada.
- Búsqueda. Permite determinar si un elemento se encuentra o no en la estructura.
- Consulta de la información. Permite obtener información de uno o más elementos de la estructura.
- Copia parcial o total: Mediante esta operación se puede obtener total o parcialmente una estructura con características similares a la original.
- Prueba. Permite determinar si uno o varios elementos cumplen determinadas condiciones.
- Verificar si es vacía. Permite determinar si existen o no elementos sobre la estructura
Clasificación
Una clasificación de estructuras de datos es según dónde residan: Internas y externas. Si una estructura de datos reside en la memoria central del computador se denomina estructura de datos interna. Recíprocamente, si reside en un soporte externo, se denomina estructura de datos externa.
Las estructuras de datos internas pueden ser de dos tipos:
- Estructuras de Datos Estáticas.
- Estructuras de Datos Dinámicas.
Estructuras de Datos Estáticas
Tienen un número fijo de elementos que queda determinado desde la declaración de la estructura en el comienzo del programa. Ejemplo los arreglos. Las estructuras de datos estáticas, presentan dos inconvenientes:
- La reorganización de sus elementos, si ésta implica mucho movimiento puede ser muy costosa. Ejemplo: insertar un dato en un arreglo ordenado.
- Son estructuras de datos estáticas, es decir, el tamaño ocupado en memoria es fijo, el arreglo podría llenarse y si se crea un arreglo de tamaño grande se estaría desperdiciando memoria.
Estructuras de Datos Dinámicas
Las estructuras de datos dinámicas nos permiten lograr un importante objetivo de la programación orientada a objetos: la reutilización de objetos. Al contrario de un arreglo, que contiene espacio para almacenar un número fijo de elementos, una estructura dinámica de datos se amplía y contrae durante la ejecución del programa.
A su vez, este tipo de estructuras se pueden dividir en dos grandes grupos según la forma en la cual se ordenan sus elementos.
- Lineales
- No lineales
Estructuras de Datos Lineales
En este tipo de estructuras los elementos se encuentran ubicados secuencialmente. Al ser dinámica, su composición varía a lo largo de la ejecución del programa que lo utiliza a través de operaciones de inserción y eliminación. Dependiendo del tipo de acceso a la secuencia, haremos la siguiente distinción:
- Listas: podemos acceder (insertar y eliminar) por cualquier lado.
- Pilas: sólo tienen un único punto de acceso fijo a través del cual se añaden, se eliminan o
se consultan elementos. - Colas: tienen dos puntos de acceso, uno para añadir y el otro para consultar o eliminar
elementos
Estructuras de Datos No Lineales
Dentro de las estructuras de datos no lineales tenemos los árboles y grafos. Este tipo de estructuras los datos no se encuentran ubicados secuencialmente. Permiten resolver problemas computacionales complejos.
A lo largo del curso veremos las semejanzas, diferencias y más importante aún las aplicaciones de los diversas estructuras anteriormente mencionadas.
Fuentes consultadas para este artículo:
– Fager, Pantoja Yépez, Villacrés, Páez Martínez, Ochoa, Cuadros-Vargas. (2014). Estructuras de Datos. Latinoamérica: Iniciativa Latinoamericana de Libros de Texto Abiertos (LATIn).