Estructuras Enlazadas

Programación y

Algoritmia

Un enfoque práctico y didáctico

para el diseño de algoritmos

4 Estructuras Enlazadas

Lic. Oscar Ricardo Bruno, MDU

Contenido

Estructuras Enlazadas__________________________________________________ 3

Introducción _______________________________________________________ 3

Estructuras enlazadas vs. estructuras indexadas _________________________ 3

Estructuras enlazadas con asignación dinámica en memoria _______________ 3

El tipo de dato Puntero_______________________________________________ 5

Acceso a datos mediante apuntadores __________________________________ 7

Tipos de datos autorreferenciados o recursivos___________________________ 8

Estructuras de datos dinámicas lineales_________________________________ 9

El tipo pila _________________________________________________________ 9

Insertar elemento en una pila:________________________________________ 11

Desapilar: leer y eliminar un elemento ________________________________ 11

El tipo cola________________________________________________________ 12

Añadir un elemento Encolar: ________________________________________ 12

Leer un elemento de una cola Eliminar primero: ________________________ 13

El tipo lista________________________________________________________ 13

Listas simplemente enlazadas ________________________________________ 13

Eliminar elementos en una lista ______________________________________ 14

Algoritmo de inserción______________________________________________ 16

Listas circulares ___________________________________________________ 18

Operaciones básicas con listas circulares _______________________________ 19

Añadir un elemento ________________________________________________ 19

Eliminar un elemento de una lista circular _____________________________ 20

Listas doblemente enlazadas _________________________________________ 24

Operaciones básicas con listas doblemente enlazadas ____________________ 24

Añadir un elemento ________________________________________________ 24

Eliminar un elemento de una lista doblemente enlazada __________________ 27

A modo de síntesis con estructuras enlazadas ___________________________ 30

Estructuras Enlazadas

Objetivos de aprendizaje

Dominando los temas del presente capitulo Usted podrá.

1. Manejar estructuras complejas.

2. Introducirse a la semántica de direcciones

3. Comprender como se asigna memoria dinámicamente en tiempo de ejecución.

4. Conocer estructuras enlazadas lineales

5. Diferenciar entre estructuras indexadas y estructuras enlazadas

Introducción:

En el presente trabajo se incorpora el concepto de asignación dinámica en memoria.

Esto permite romper con la limitación de tamaño fijo que proporcionan las tablas

cuando es necesario trabajar con colección de datos el mismo tipo en memoria.

Para esto se incorporan los conceptos de estructuras enlazadas, punteros y asignación

dinámica en memoria.

Estructuras enlazadas vs. estructuras indexadas

Como vimos una tabla es una secuencia de datos del mismo tipo donde a cada elemento

se puede acceder a través de un índice. En esta estructura las posiciones de memoria son

contiguas y se las puede ir recorriendo con solo incrementar el índice. En estas

estructuras el primer elemento lógico coincide con el primero físico, es decir se

comienza desde la primera posición, y el siguiente lógico coincide con el siguiente

físico, es decir al próximo elemento se accede incrementando en uno el índice. Estas

estructuras, con esta organización son estructuras indexadas. Las estructuras pueden

organizarse de forma diferente. El primer elemento lógico puede no coincidir con el

primero físico, en ese caso, para conocer donde comienza lógicamente se debe saber la

posición de ese primero. El siguiente elemento lógico no necesariamente debe estar en

la posición contigua, para saber donde esta será necesario tener algo que referencie la

posición del siguiente elemento. Una estructura con esta organización es una estructura

enlazada. Las estructuras enlazadas tienen la particularidad que se necesita conocer la

posición del primer elemento y en cada posición se tiene un registro, llamado nodo, con

al menos dos campos, uno que contenga la información y otro que indique o referencie

donde se encuentra el siguiente que no necesariamente debe ser el contiguo.

Por otro lado vimos que si se quiere definir en memoria una colección de datos del

mismo tipo mediante una tabla esta requiere establecer una capacidad máxima. Estas

son estructuras con tamaño fijo, el mismo no puede ser modificado en tiempo de

ejecución. Existe entonces riesgo que la cantidad de posiciones definidas en tiempo de

declaración no alcancen, o, que se utilicen muy pocas de las posiciones definidas

haciendo un uso poco eficiente de los recursos.

Estructuras enlazadas con asignación dinámica en memoria

Una estructura con asignación dinámica es un conjunto de elementos de tipo

homogéneo donde los mismos no ocupan posiciones contiguas de memoria, pueden

aparecer físicamente dispersos manteniendo un orden lógico y son instanciados y/o

liberados en tiempo de ejecución.

Operaciones con listas

1. Crear una estructura

2. Recorrerla, parcial o totalmente

3. Agregar o insertar nuevos elementos o nodos en distintos lugres y con criterio

variado.

4. Localizar un elemento en particular en la estructura

5. Borrar un elemento de posicion particular o previamente desconocida

La mayor facilidad de las listas es el “enlace dinámico” a través de punteros que

permiten intercalar o eliminar valores sin un movimiento masivo de memoria, con solo

pedir memoria o liberarla y hacer simplemente los enlaces de los nodos involucraos.

Punteros

Es posible definir estructuras de datos complejas cuyo tamaño puede cambiar en tiempo

de ejecución, por lo que son denominadas estructuras de datos dinámicas. Se instancias

a través de punteros.

Mediante la utilización de tablas se puede definir una secuencia de valores como:

TipoSecuencia = TIPO Tabla [1, LongitudMaxima] de elemento;

Con esta definición se reserva espacio en tiempo de ejecución para una cantidad fija de

elementos. Esta cantidad esta dada por el valor de LongitudMaxima.

Otra forma de definir una secuencia de valores seria por inducción o recursion:

La secuencia vacía es una secuencia

Un elemento concatenado a una secuencia es otra secuencia

De esta forma se declara el tipo sin especificar ninguna capacidad máxima, se define en

forma recursiva.

En esta definición es necesario que cada elemento referencie con precisión el siguiente

elemento si es que este existe.

Una secuencia, con esta organización, como ya dijimos es una concatenación de

registros llamados nodos de dos campos: uno para la información y otro para un

indicador al siguiente elemento. El siguiente elemento al que se referencia es un registro

del mismo tipo del actual, por referenciar a una estructura de su mismo tipo estas

estructuras se conocen como estructuras autoreferenciadas.

Para la asignación dinámica en memoria, los elementos se enlazan a través de un

determinado tipo de dato que disponen la mayoría de lenguajes de programación y que

se denominan puntero o apuntador, cuyos valores son referencias o punteros a variables

de un tipo.

TipoPunteroEntero = TIPO Apuntador a Entero;

Se hace una definición de un tipo de dato con la particularidad que tendrá como valor

una dirección de memoria. Se dirá entonces que es un puntero al tipo de dato o que

apunta a determinado tipo de dato

Si de define

PunteroEntero = TipoPunteroEntero

Los posibles valores de PunteroEntero no serán enteros, sino referencias a enteros; esto

sería la dirección del espacio de memoria en la que se almacena el entero.

Ya se definió variable como un identificador que denota un espacio de memoria en el

que se almacena un valor del tipo asociado en la dirección.

Un valor apuntador es la dirección de una variable “anónima”, se le asigna la dirección

a se crea en tiempo de ejecución.

Para indicar que una variable puntero no referencia o apunta a ninguna a otra variable

se le debe asignar el valor NULO.

TipoInfo = TIPO Entero

//define la información que tendrá el campo dato del nodo//

TipoPuntero = TIPO Apuntador a TipoNodo;

//Define un puntero que en cada instancia generara un nodo.

TipoNodo = TIPO < dato : TipoInfo; sgte : TipoPuntero >;

//Define un nodo con la información y la referencia al siguiente que es un puntero a la

siguiente dirección de memoria de la secuencia definida//

Se trata de una definición recursiva o autorreferenciada siguiendo la definición

inductiva de secuencia.

Una estructura enlazada utilizando punteros debe tener una variable que controle la

estructura, en general debe contener la dirección de memoria del primer nodo

...