Fundamentos de Estructuras de Datos y Tipos Abstractos para Programadores

Clasificación de Estructuras de Datos

Una estructura de datos es un conjunto de datos en los que se pueden llevar a cabo diversas operaciones.

Estructuras Lógicas de Datos

En un programa, cada variable pertenece a un conjunto definido por las operaciones que se pueden llevar a cabo sobre ella.

Estructuras Primitivas

Son aquellas estructuras de datos básicas, por ejemplo, los enteros, fraccionarios, booleanos y los caracteres. A partir de ellas se construyen estructuras más complejas como los arrays, cadenas y registros.

Estructuras Lineales y No Lineales

Las estructuras de datos simples se pueden combinar de distintas formas para dar lugar a estructuras de datos más complejas. Entre las lineales, destacan las pilas, las colas, las listas enlazadas y las listas circulares.

El último nodo de una lista enlazada, que no almacena más que su propia dirección, puede apuntar a null.

Entre las estructuras no lineales, destacan dos grandes técnicas: los grafos y los árboles.

Nota: En los árboles, normalmente se parte del nodo raíz.

Tipos de Datos según su Gestión de Memoria

Datos Estáticos

Su tamaño y forma son constantes durante su ejecución, por lo tanto, se determina su longitud o reserva de espacio en memoria en tiempo de compilación. De tal manera, estas estructuras pueden presentar un problema al dimensionar su tamaño.

Datos Dinámicos

Su tamaño y forma suelen ser variables a lo largo de la ejecución de un programa, por lo que comúnmente se crean o se destruyen en tiempo de ejecución.

Tipos de Datos Abstractos (TDA)

Son todos aquellos tipos de datos que son definidos o declarados por el propio usuario (es decir, todos aquellos que no son predeterminados por el sistema).

Los Tipos de Datos Abstractos se componen de dos partes principales: la interfaz y la implementación. En la interfaz se declaran las operaciones disponibles.

La implementación contiene el código fuente de dichas operaciones y los detalles internos de los datos, manteniéndolos ocultos al usuario.

Ventajas de los Tipos de Datos Abstractos

• Hacen el sistema más robusto.
• Reducen los tiempos de compilación.
• Permiten modificar la implementación sin afectar la interfaz.
• Facilitan la extensibilidad.

Ejemplo de Tipo de Dato Abstracto

Un ejemplo es el tipo de dato booleano, formado por los valores true o false.

¿Qué es la Abstracción?

Es la capacidad de manejar un objeto como un concepto general, ocultando los detalles de su implementación interna.

Tipos de Datos Abstractos Compuestos Básicos

Conjunto

Colección de elementos tratados con las operaciones de unión, intersección y diferencia de conjuntos.

Arreglo (Array)

Colección homogénea de longitud fija, tal que cada uno de sus componentes puede ser accedido individualmente mediante un índice.

Registro

Tipo de dato heterogéneo compuesto por un número fijo de componentes denominados campos, a los que se accede mediante un selector de campo.

Matriz

Tiene como tipo el conjunto de matrices definido por las matemáticas y los operadores asociados a las mismas: obtener elemento, asignar elemento.

Lista o Secuencia

Colección homogénea de datos ordenados según su posición en ella, tal que cada elemento tiene un predecesor (excepto el primero) y un sucesor (excepto el último). Sus operadores típicos son: insertar, localizar, recuperar, suprimir (elementos), suprimir dato (todas las ocurrencias).

En general, el término "lista" se usa cuando el TDA se implementa sobre la memoria principal.