Estructuras de Datos Dinámicas

Objetivos

Las estructuras estáticas no pueden cambiar su tamaño durante la ejecución del programa.

Cambiar la disposición de los elementos dentro de la estructura estática es costoso.

Ejemplo: las posiciones de los elementos dentro de un array (no podemos redimensionar el array).

En tiempo de diseño no sabemos exactamente cuánta memoria necesitamos ni cómo se va a organizar.

Solución: definir y organizar esa memoria en tiempo de ejecución ==> utilización de estructuras de memoria dinámica

La gestión de memoria dinámica se realiza a través de los punteros

Memoria dinámica: memoria en la que se puede reservar espacio en tiempo de ejecución

Estructuras de memoria dinámica: colección de elementos (denominados nodos de la estructura) que están enlazados entre sí.

Variables Dinámicas: Posiciones de memoria reservadas en tiempo de ejecución

Def.: Es una variable que sirve para indicar cuál es la posición de memoria de otra variable.

Semántica: Declara un tipo de datos (Identificador) que es un puntero a otro tipo de datos (Tipo)

Punteros

1. Operaciones con punteros

New: procedimiento por el que se reserva un espacio de memoria dinámica

Sintáxis: new (Variable_puntero);

Semántica: reserva un espacio de memoria y la variable puntero que se pasa como parámetro se deja apuntando a dicho espacio

Dispose: procedimiento por el que se libera memoria dinámica

Sintáxis: dispose (Variable_puntero);

Semántica: Libera el espacio de memoria apuntado por la variable puntero que se pasa como parámetro

Acceso a los datos: operador ^ (circunflejo) (también llamado operador de desreferencia)

A partir del operador ^ la referencia se trata según el tipo de datos al que hace referencia el puntero

No siempre es obligatorio reservar memoria para utilizar un puntero

Obtención de la dirección de memoria de una variable: operador @ (referencia)

NIL (Puntero nulo) es una constante de tipo puntero

Un puntero NIL, indica que no apunta a ninguna posición de memoria

Cuidado con las posiciones que se dejan de apuntar, podemos perder memoria si no las liberamos antes

Sólo permite las operaciones de asignación (:=) y comparación con los operadores relacionales (= y )

Los operandos han de ser punteros a variables del mismo tipo o NIL

Procedimientos y Funciones

• Pueden ser parámetros, por valor y por referencia, de los subprogramas.
• Se pueden devolver como resultado de una función.
• Aunque f sea una función que devuelva un puntero a un registro, no se permite: f(parámetros reales)^.nombre; X varPuntero := f(parámetros reales); V

2. Observaciones

• Declarar una variable de tipo puntero no siempre es suficiente para poder utilizarla
• Para crear información dinámicamente se debe llamar al procedimiento new
• Después de llamar a new, el valor al que apunta el puntero es indefinido. Para definirlo es necesario asignarle un valor.

Variable_puntero ? Variable_puntero^

Es muy conveniente liberar el espacio de memoria mediante dispose cuando no se vaya a utilizar más un puntero

Listas Enlazadas

Una lista está formada por una colección de elementos llamados nodos tales que cada uno de ellos almacena dos valores:

• El elemento de la lista: todos son del mismo tipo de dato (también llamado campo de información)
• Un puntero que indica la posición del nodo que contiene el siguiente elemento de la lista

El enlace se realiza a través del puntero asociado a cada nodo.

Es necesario tener la referencia del nodo que contiene el primer elemento de la lista.

La lista enlazada es una estructura recursiva.

1. Listas enlazadas simples

• Estructura dinámica más sencilla: solo tiene un enlace.
• Un nodo se representa mediante un registro con dos campos: uno para los datos y el otro es un puntero a otro nodo.


TYPE
tDato =String[25] {tipo de los elementos de la lista}
tLista=^tNodoLista;
tNodoLista=RECORD
nombre:tDato;
sig:tLista {Estructura Recursiva}
END;
VAR
paux, aux, primer, anterior,lista:tLista;


Crear una lista vacía:

lista := NIL;

Comprobar si una lista está vacía:


IF (lista = NIL) THEN
{lista vacía}
ELSE
{hay uno o más elementos} (Ejemplos 10a, 10b)


Fin de una lista:


IF (lista.sig = NIL) THEN
{último elemento de la lista}


2. Listas doblemente enlazadas

Mantiene enlaces en ambas direcciones

• Necesita dos punteros:
• Ant: apunta al nodo anterior
• Sig: apunta al nodo siguiente

Desventaja: Operaciones como inserción y borrado son más complejas (necesita más punteros auxiliares)

Ventaja: acciones como ordenar una lista u obtener una lista inversa son fáciles de realizar.

Otras estructuras dinámicas

Pilas: Es una lista particularizada al caso en el cual sólo se insertan y eliminan elementos por uno de los extremos: Lista LIFO (Last In First Out)

Colas: Es una lista particularizada al caso en el cual se insertan los elementos por un extremo y se eliminan por el otro: Lista FIFO (First In First Out)

Observaciones estructuras dinámicas

• El concepto de lista puede implementarse de forma estática (array parcialmente lleno)
• La lista dinámica tiene desventajas frente al array: complejidad de acceso O(n) frente a O(1)
• Hay que tener especial cuidado de no perder el puntero que apunta a la cabeza de la lista, perderíamos toda la lista si no la tenemos apuntada por un auxiliar.
• Cuando borramos elementos de una lista no nos debemos olvidar de liberar el nodo que borramos (no basta con puentearlo)

Etiquetas: estructuras de datos, listas enlazadas, memoria dinámica, Programación, punteros