Mi primer trabajo

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: ________________________ 13El 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 listascirculares _______________________________ 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 memoriadiná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. Paraesto 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. Enestas 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ógicopuede 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...