tarea compu

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
Estructurasenlazadas 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
Operacionesbá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. Comprendercomo 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 dedatos 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 irrecorriendo 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 puedenorganizarse 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...