Estructuras de Datos: Tipos, Clasificación y Organización

Resumen

Este apunte introduce las estructuras de datos, que son conjuntos de elementos de información con una organización. Explica qué son los nodos y clasifica las estructuras según sus elementos, según la relación entre ellos (lineales, jerárquicas y multirrelacionales) y según la memoria utilizada. También distingue la estructura lógica de la estructura de representación. El estudiante aprenderá a identificar cada tipo y sus ejemplos.

Puntos clave

Una estructura de datos es un conjunto de elementos de información dotado de una organización.
Según sus elementos, una estructura puede ser homogénea (todos del mismo tipo) o heterogénea (de tipos diferentes).
Según la relación entre sus elementos, puede ser lineal (1:1), jerárquica o árbol (1:n) o multirrelacional (n:n).
Las estructuras estáticas tienen un número fijo de elementos contiguos, como el array. Las dinámicas tienen un número variable de elementos no contiguos relacionados por encadenamiento.
La estructura lógica describe cómo se relacionan los datos de forma conceptual. La de representación describe su implementación en un ordenador.
La estructura de representación influye en la eficiencia de los algoritmos que manipulan la estructura de datos.

Resumen generado con IA a partir del documento. Ponte a prueba

¿Qué es una estructura de datos?

Una estructura de datos es un conjunto de elementos de información dotado de una organización.

Tipos de estructuras de datos según sus elementos:

Homogéneas: Cuando todos los elementos que la forman son del mismo tipo.
Heterogéneas: Cuando son de tipos diferentes.

Elementos Individuales: Nodos

Los componentes de una estructura de datos reciben el nombre de nodos. El nodo es la unidad de referencia básica de la estructura. Conceptualmente, un nodo puede ser desde un elemento muy simple a uno muy complejo, con una elaborada estructura interna.

Ejemplo: Una página web puede ser un nodo de un hipertexto.

Clasificación de Estructuras de Datos por Componentes

Por el tipo de sus elementos, las estructuras de datos pueden ser:

Homogéneas: Cuando todos los elementos que la forman son del mismo tipo.
Heterogéneas: Cuando son de tipos diferentes.

Estructura Lógica vs. Estructura de Representación

La estructura lógica se refiere a cómo se relacionan los datos desde el punto de vista conceptual.

La estructura de representación trata de los mecanismos de implementación en un ordenador.

La estructura de representación influye fuertemente en la eficiencia de los algoritmos que manipulen la estructura de datos.

Ambos mecanismos de estructuración se pueden mezclar para formar conglomerados cada vez más complejos (arrays de records, record con campos array). A un nivel lógico superior se encuentra el concepto de encadenamiento, con el que se pueden formar estructuras más complejas al permitir que cada nodo pueda indicar su relación lógica con otros.

Las estructuras encadenadas como los arrays pueden representar colecciones de elementos de un mismo tipo, con la ventaja de que se puede añadir o quitar un nodo en cualquier punto de la estructura sólo con modificar algunos enlaces, sin que los demás nodos tengan que cambiar su ubicación física.

Criterios de Clasificación de Estructuras de Datos

Las estructuras de datos se clasifican según varios criterios:

Por el tipo de sus elementos:

Homogéneas: Cuando todos los elementos que la forman son del mismo tipo.
Heterogéneas: Cuando son de tipos diferentes.

Por el modo de organización y relación entre sus elementos:

Estructura Lineal: Cuando la relación entre sus componentes es de 1:1. Los elementos se encuentran “alineados”, cada uno tiene un sucesor que es único y un predecesor también único. Las relaciones sucesor y predecesor no están definidas para el último y el primer elemento. Ejemplos: Un vector, una lista encadenada.
Estructuras Jerárquicas: Generalmente conocidas como árboles. Las relaciones son 1:n (de uno a muchos). Cuando no están vacías, existe un nodo que es el punto de inicio o raíz de la jerarquía. El resto de los nodos se agrupan con respecto a él en subconjuntos que son a su vez árboles. Este tipo de estructura es típica del organigrama de muchas organizaciones.
Estructuras Multirelacionales: Las relaciones son n:n (de muchos a muchos). Cada nodo de la estructura se puede relacionar libremente con cualquier otro elemento, incluso consigo mismo. Es un tipo de estructura que se da frecuentemente en todo tipo de redes de comunicaciones.

Clasificación según la Enciclopedia of Computer Science:

ED Estáticas: Formada por un número fijo de elementos contiguos. Ej: array.
ED Dinámicas: Formada por un número variable de elementos no contiguos relacionados mediante encadenamiento.

Según la memoria utilizada:

Estructuras de datos en memoria interna.
Estructuras de datos en memoria externa, diseñadas teniendo en cuenta la lentitud de acceso a dispositivos externos --como, por ejemplo, un disco--, tratan de optimizar la transferencia de información.

Estas consideraciones conducen a la utilización de mecanismos como la paginación de la estructura, consistentes en agrupar varios elementos en una unidad de acceso -la página- de tamaño aproximado al de la unidad de transferencia con el disco.

Preguntas frecuentes

¿Qué son los nodos de una estructura de datos?

Los nodos son los componentes de una estructura de datos y su unidad de referencia básica. Pueden ser desde un elemento muy simple hasta uno muy complejo, como una página web en un hipertexto.

¿Qué diferencia hay entre estructura lógica y estructura de representación?

La estructura lógica describe cómo se relacionan los datos desde el punto de vista conceptual. La estructura de representación describe los mecanismos de implementación en un ordenador.

¿Qué es una estructura jerárquica?

Es una estructura con relaciones 1:n, generalmente conocida como árbol. Tiene una raíz y el resto de nodos se agrupan en subconjuntos que son a su vez árboles, como ocurre en un organigrama.