Ejemplos en pascal de una lista doblemente enlazada

Normalmente, un grupo de datos se asociará con una estructura de datos. Hablaremos de estructuras dinámicas cuando los elementos en ellas pueden cambiar con el tiempo en número.

Programas y memoria

Cuando el sistema operativo carga un programa para ejecutarlo y lo convierte en proceso, le asigna cuatro partes lógicas en memoria principal: texto (código del programa), datos (estáticos), pila y una zona libre o heap. Esta zona libre o heap es la que va a contener los datos dinámicos.

Memoria estática

La memoria de datos en un programa es la que se dedica a almacenar las variables correspondientes al programa.

Memoria dinámica

La memoria dinámica delimita una zona de memoria donde la reserva no se realiza definiendo variables, sino utilizando funciones específicas de reserva y liberación de memoria.

GESTIÓN DE LA MEMORIA DINÁMICA Para trabajar con datos dinámicos por tanto, necesitamos dos cosas:

a. Funciones predefinidas en el lenguaje que nos permitan gestionar la memoria de forma dinámica (asignación y liberación). B. Algún tipo de dato con el que podamos acceder a esos datos dinámicos como los punteros.

Función malloc()

Se utiliza para asignar memoria dinámica en tiempo de ejecución. Está en el archivo de cabecera <stdlib.H> y <alloc.H> o <malloc.H> y su prototipo es: void * malloc(int);

Estructuras autoreferenciadas

La forma más habitual de implementar los tipos de datos dinámicos es utilizando las estructuras de datos autorreferenciadas. Una estructura autorreferenciada es una estructura de C donde uno de sus elementos es un puntero a una estructura del mismo tipo.

Reserva de memoria para un nodo

Los nodos se crean de forma dinámica (cada vez que se necesitan) asignándoles en tiempo de ejecución posiciones de memoria no utilizadas. De esta forma, se pueden crear y utilizar nuevos nodos siempre que haya memoria libre disponible. p=(nodo*)malloc(sizeof(EST_DINAMICA))

Liberación de memoria

Tras usar la memoria asignada a un puntero, hay que liberarla para poder utilizarla con otros fines y no dejar datos inservibles en el mapa de la memoria dinámica. Se libera la memoria asignada a un puntero p, cuyo tipo ocupa t bytes, también dinámicamente, mediante la función free() que se encuentra en el archivo de cabecera <stdlib.H>: Su prototipo es: void free(void *);

LISTAS ENLAZADAS

Una lista puede definirse como una n-tupla dinámica ordenada: L=(l1, l2,l3,…, ln) donde li es el i-ésimo elemento de la lista.

Inserción de nodos

Podemos insertar nodos en distintos lugares de la lista, bien al principio o al final. También es frecuente una operación de inserción en cualquier lugar de la lista, así como la inserción ordenada de elementos en listas ordenadas.

Búsqueda de elementos o recorrido de una lista

Recorrer una lista supone ir accediendo a cada elemento de la misma desde el primero hasta el último, en el mismo orden en el que aparecen en la lista.

Lista circular

Si el puntero de último elemento de la lista apunta al principio de la lista, se dice que la lista es circular. En una lista circular cada nodo siempre tiene uno anterior y uno siguiente.

Lista doblemente enlazada

Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior, además de los datos. En las listas doblemente enlazadas se puede acceder a los elementos en cualquier sentido.

PILAS

Se denomina pila a un conjunto dinámico ordenado de elementos, generalmente del mismo tipo, en el que pueden insertarse y suprimirse elementos únicamente por un extremo. Dicho extremo recibe el nombre de cima (top) de la pila.

COLAS

Una cola es un conjunto dinámico ordenado de elementos, generalmente del mismo tipo, en el que pueden insertarse elementos únicamente por un mismo extremo, denominado cola, y en el que pueden suprimirse elementos únicamente por el otro extremo de la estructura, denominado cabeza.

ÁRBOLES

Un árbol es un conjunto de elementos llamados nudos o nodos, que forman una estructura jerárquica, derivada de una relación de paternidad existente entre ellos. Un árbol puede almacenar en sus nodos cualquier tipo de información. Los árboles están organizados por niveles. El primer nivel lo forma el nodo raíz. El segundo nivel los nodos referenciados por el nodo raíz, etc. Así sucesivamente hasta llegar a los nodos que no tienen hijos que se denominan hojas.

Recorrido en profundidad

Existen tres formas de recorrer un árbol binario en profundidad: en preorden, en orden simétrico (inorden) o en postorden.

Preorden

- Acceso al campo de datos.- Acceso al hijo izquierdo. - Acceso al hijo derecho.

Inorden

Acceso al hijo izquierdo.- Acceso al campo de datos. - Acceso al hijo derecho.

Postorden

Acceso al hijo izquierdo.- Acceso al hijo derecho.- Acceso al campo de datos.