ESTRUCTURA DE DATOS Y ARCHIVOS

3.2 Estructura de datos y archivos

3.2.1 Estructura de datos

Una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.

Una estructura de datos define la organización e interrelación de éstos y un conjunto de operaciones que se pueden realizar sobre ellos. 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 pueden realizar 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 factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

Listas.

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por elemento. Este enlace apunta al siguiente elemento en la lista, o al valor nulo a la lista vacía, si es el último elemento.

Una lista enlazada simple contiene dos valores: el valor actual del elemento y un enlace al siguiente elemento

UNIDAD DE APRENDIZAJE: TECNOLOGÍA INFORMÁTICA

UNIDAD III. TECNOLOGÍAS INFORMÁTICAS DE ALMACENAMIENTO

ELECTRÓNICO DE INFORMACIÓN

SEMA, GOMA, COAT

Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada elemento tiene dos enlaces: uno apunta al elemento anterior, o apunta al valor NULO si es el primer elemento; y otro que apunta al elemento siguiente, o apunta al valor NULO si es el último elemento. Una lista doblemente enlazada contiene tres valores: el valor, el link al elemento siguiente, y el link al anterior

Matriz.

Desde el punto de vista lógico una matriz se puede ver como un conjunto de elementos ordenados en fila (o filas y columnas si tuviera dos dimensiones). En principio, se puede considerar que todas las matrices son de una dimensión, la dimensión principal, pero los elementos de dicha fila pueden ser a su vez matrices, lo que nos permite hablar de la existencia de matrices multidimensionales, aunque las más fáciles de imaginar son los de una, dos y tres dimensiones.

Estas estructuras de datos son adecuadas para situaciones en las que el acceso a los datos se realice de forma aleatoria e impredecible. La forma de acceder a los elementos de la matriz es directa; esto significa que el elemento deseado es obtenido a partir de su índice y no hay que ir buscándolo elemento por elemento (en contraposición, en el caso de una lista, para llegar, por ejemplo, al tercer elemento hay que acceder a los dos anteriores.

Pilas.

Una pila es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es último en entrar, primero en salir, que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar, que coloca un objeto en la pila, y su operación inversa, retirar, que retira el último elemento apilado.

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado. La operación retirar permite la obtención de este elemento,

UNIDAD DE APRENDIZAJE: TECNOLOGÍA INFORMÁTICA

UNIDAD III. TECNOLOGÍAS INFORMÁTICAS DE ALMACENAMIENTO

ELECTRÓNICO DE INFORMACIÓN

SEMA, GOMA, COAT

que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo último elemento de la pila. Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo el que se encuentra hasta arriba.

Colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción se realiza por un extremo y la operación de extracción por el otro. El primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento.

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, etc. La idea esencial es que son todas líneas de espera.

UNIDAD DE APRENDIZAJE: TECNOLOGÍA INFORMÁTICA

UNIDAD III. TECNOLOGÍAS INFORMÁTICAS DE ALMACENAMIENTO

ELECTRÓNICO DE INFORMACIÓN

SEMA, GOMA, COAT

En estos casos, el primer elemento de la lista realiza su función (pagar comida, pagar entrada para el partido o para el cine) y deja la cola. Este movimiento está representado en la cola por la función desencolar. Cada vez que otro elemento se añade a la lista de espera se añaden al final de la cola representando la función encolar. Hay otras funciones auxiliares para ver el tamaño de la cola, para ver si está vacía en el caso de que no haya nadie esperando o para ver el primer elemento de la cola.

Árbol.

Un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de elementos conectados). Un elemento es la unidad sobre la que se construye el árbol y puede tener cero o más elementos hijos conectados a él. Se dice que un elemento a es padre de un elemento b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único elemento sin padres, que llamaremos raíz. Un elemento que no tiene hijos se conoce como hoja. Los demás elementos (tienen padre y uno o varios hijos) se les conoce como rama.

Las operaciones comunes en árboles son: Enumerar todos los elementos. Buscar un elemento. Dado un elemento, listar los hijos (si los hay). Borrar

...