Estructura de datos

1.2 ESTRUCTURA DE DATOS

1.2.1 DEFINICIÓN

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales (un dato elemental es la mínima información que se tiene en el sistema) con el objetivo de facilitar la manipulación de estos datos como un todo o individualmente.

Una estructura de datos define la organización e interrelacionamiento de estos, y unconjunto de operaciones que se pueden realizar sobre él. Las operaciones básicas son:

Alta, adicionar un nuevo valor a la estructura.

Baja, borrar un valor de la estructura.

Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma SECUENCIAL o BINARIO (siempre y cuando los datos estén ordenados)…

Otras operaciones que se puedenrealizar son:

Ordenamiento, de los elementos pertenecientes a la estructura.

Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factorescomo la frecuencia y el orden en que se realiza cada operación sobre los datos.

1.2.2. Clasificación
1.2.2.1 Lineales y No Lineales

Las estructuras de datos simples se pueden combinar de varias maneras para formar estructuras más complejas. Las dos cases principales de estructuras de datos son las lineales y las no lineales, dependiendo de la complejidad de las relaciones lógicas querepresentan. Las estructuras de datos lineales incluyen pilas, colas y listas ligadas lineales. Las estructuras de datos no lineales incluyen grafos y árboles.

Estructura de datos lineales

En este tema se estudia la primera gran familia de TADs, todos ellos derivados del concepto de secuencia. Primero se definen las secuencias como conjuntos de elementos entre los que se establece una relación depredecesor y sucesor. Los diferentes TADs basados en este concepto se diferenciaran por las operaciones de acceso a los elementos y manipulación de la estructura. Desde el punto de vista de la informática, existen tres estructuras lineales especialmente importantes: las pilas, las colas y las listas. Su importancia radica en que son muy frecuentes en los esquemas algorítmicos.
Las operacionesbásicas para dichas estructuras son:
• crear la secuencia vacía
• añadir un elemento a la secuencia
• borrar un elemento a la secuencia
• consultar un elemento de la secuencia
• comprobar si la secuencia está vacía
La diferencia entre las tres estructuras que se estudiarán vendrá dada por la posición del elemento a añadir, borrar y consultar:
• Pilas: las tresoperaciones actúan sobre el final de la secuencia
• Colas: se añade por el final y se borra y consulta por el principio
• Listas: las tres operaciones se realizan sobre una posición privilegiada de la secuencia, la cual puede desplazarse
Se presenta el TAD de las pilas de elementos arbitrarios. Tras especificarlo, se muestra su implementación en vector (posteriormente se verá su implementacióncon memoria dinámica) y se discuten sus ventajas y desventajas.
Después se muestran las colas siguiendo un proceso idéntico al del subtema anterior. Se presenta y discute la implementación en vector circular (también posteriormente se verá su implementación en memoria dinámica).
Respecto a las listas, dado que hay muchas versiones diferentes se escoge una como base. Concretamente las listas conpunto de interés, donde existe un elemento que sirve de referencia a las operaciones de inserción, supresión y consulta. Estas listas tienen el interés añadido de que son equivalentes a la noción de secuencia que los estudiantes conocen de Programación. Se da una especificación formal de estas listas y se discuten las diferentes implementaciones. Tras considerar una implementación secuencial,...