Estructuras de Datos: Tipos, Clasificación y Tipos Abstractos (TADs)

Estructuras de Datos: Definición y Organización

Una estructura de datos es un conjunto de elementos de información dotado de una organización. Esta organización se basa en criterios conceptuales y prácticos:

• Criterios Conceptuales:
  • Estructura orgánica de una empresa.
  • Estructura molecular de una proteína.
  • Datos personales de un individuo.
• Criterios Prácticos:
  • Optimización de los recursos usados para representar la estructura.
  • Facilidad para utilizar o actualizar la información.
  • Eficiencia de los algoritmos de manipulación.

Ejemplos de estructuras de datos:

• Lista simplemente encadenada
• Lista doblemente enlazada
• Lista multienlazada

Clasificación de las Estructuras de Datos

Las estructuras de datos se pueden clasificar según:

Tipo de Elementos

• Homogéneas: Todos los elementos son del mismo tipo.
• Heterogéneas: Los elementos son de tipos diferentes.

Modo de Organización y Relación

• Estructuras Lineales
• Estructuras Jerárquicas
• Estructuras Multirrelacionales

Estructuras Lineales

La relación entre sus componentes es de 1:1. Los elementos se encuentran alineados, donde cada uno tiene un sucesor ú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). 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 Multirrelacionales

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.

La Enciclopedia of Computer Science distingue:

• Estructuras de Datos Estáticas: Formadas por un número fijo de elementos contiguos. Ejemplo: array.
• Estructuras de Datos Dinámicas: Formadas por un número variable de elementos no contiguos relacionados mediante encadenamiento.

Tipos Abstractos de Datos (TADs)

La abstracción es un mecanismo básico de conocimiento. Es la acción y efecto de separar por medio de una operación intelectual las cualidades de un objeto para considerarlas aisladamente o para considerar el mismo objeto en su pura esencia o noción.

Un tipo de datos es un modelo que designa un conjunto de valores y un conjunto de operaciones aplicables a los mismos. Todo tipo de dato sería un TAD.

El término TAD suele reservarse a los tipos no primitivos, en cuyo diseño se han tenido en cuenta tres principios básicos: separación, encapsulamiento y ocultamiento de información.

En la realización de un TAD existen dos aspectos:

• El externo: que se describe como se usa el tipo por medio de una interfaz en la que se especifican el nombre, las propiedades visibles y las operaciones que se le pueden aplicar.
• El interno o implementación: Que sustenta el comportamiento visible y comprende las estructuras de representación de los datos y los algoritmos mediante los que se realizan las operaciones.

Encapsular consiste en poner juntos y aislar todos los elementos relacionados con una entidad o proceso.

• Por ejemplo: Un subprograma encapsula un conjunto de declaraciones e instrucciones necesarios para la realización de un proceso. Un registro encapsula campos de información.

En Resumen:

• Un TAD es un conjunto de valores con su propia estructura lógica y de operaciones que establecen las reglas de manipulación de esos valores, diseñado siguiendo principios que refuerzan la abstracción.
• La diferencia fundamental entre un tipo abstracto y uno concreto es que el abstracto oculta su implementación. Por ejemplo: En ADA existen tres tipos para manipular ristras de caracteres: String, Bounded_String y Unbounded_String; el tipo String no es un TAD ya que el usuario tiene acceso a su representación como array of character y puede usarla; sin embargo, los tipos Bounded_String y Unbounded_String sí son TAD ya que no se tiene acceso a su representación, que ni siquiera está especificada en el lenguaje.