estructuras lineales : listas
TRANSCRIPT
![Page 1: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/1.jpg)
Estructuras Lineales : LISTAS
Prof. Masun Nabhan Homsi
![Page 2: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/2.jpg)
Definiciones y Conceptos Básicos
• Una Lista: Es una secuencia de cero o más elementos de un mismo tipo.
<e1, e2, . . ., en>• e1: Primer elemento• en: último elemento• Longitud : se define como el número de
elementos que la componen.• Lista vacía : < >• Una posición de un elemento es el lugar
ocupado por dicho elemento.• ei, elemento e ocupa posición i.
![Page 3: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/3.jpg)
Definiciones y Conceptos Básicos
• Sucesor: Ocupa la siguiente posición.• Antecesor: Ocupa la posición anterior.• El último no tiene sucesor y el primero no
tiene anterior.
![Page 4: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/4.jpg)
Definiciones y Conceptos Básicos
• lst1 y lst2 son iguales, si ambas tienen el mismo número de componentes y, además sus elementos son iguales uno a uno. Dos listas vacías son iguales.
• lst1 y lst2 son semejantes: si ambas tienen los elementos aunque en diferente orden. Si hay un elemento repetido en lst1, debe aparecer el mismo de veces en lst2.
![Page 5: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/5.jpg)
Definiciones y Conceptos Básicos
![Page 6: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/6.jpg)
Definiciones y Conceptos Básicos
• lst es ORDENADA: lst= <e1, e2, . . ., en>Si ei ≤ ei | 1 ≤ i < n
• lst2 es una SUBLISTA de una lst1 si todos los elementos de lst2 se encuentran en lst consecutivos y en el mismo orden.
• lst2 está CONTENIDA en una lista lst1, si todos los elementos de lst2 están en lst1, aunque sean en diferente orden
![Page 7: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/7.jpg)
Definiciones y Conceptos Básicos
• Cada elemento de la lista enlazada (cajita) se denomina NODO.• Un nodo contiene dos campos: uno de información (datos del
estudiante, datos del pasajero, valores, etc.) llamado inf. y otro que contiene la dirección del siguiente nodo, llamado sig. Note que este último es un apuntador a NODO.
![Page 8: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/8.jpg)
Definiciones y Conceptos Básicos
• Existe un apuntador externo, llamado “Lista” que apunta al primer nodo, a través del cual tenemos acceso a la lista enlazada. Este apuntador no esta incluido en ningún nodo. Los demás apuntadores son internos de la lista.
![Page 9: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/9.jpg)
Definiciones y Conceptos Básicos
• El último nodo de la lista contiene un valor especial, llamado “NULL”, en el campo siguiente, el cual representa un apuntador vacío. Esto indica el fin de la lista.
• Si una lista no contiene nodos, se dice que es una lista vacía o nula. En este caso el apuntador externo vale “NULL”.
![Page 10: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/10.jpg)
Ejemplos
![Page 11: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/11.jpg)
Operaciones de las listas enlazadas
![Page 12: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/12.jpg)
Operaciones de las listas enlazadas
![Page 13: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/13.jpg)
Operaciones de las listas enlazadas
![Page 14: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/14.jpg)
Operaciones de las listas enlazadas
![Page 15: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/15.jpg)
Implementaciones de las listas enlazadas
![Page 16: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/16.jpg)
Implementaciones de las listas enlazadas
![Page 17: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/17.jpg)
Implementaciones de las listas enlazadas
![Page 18: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/18.jpg)
![Page 19: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/19.jpg)
El TAD LISTA
![Page 20: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/20.jpg)
El TAD LISTA
![Page 21: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/21.jpg)
El TAD LISTA
![Page 22: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/22.jpg)
El TAD LISTA• Modificadoras
![Page 23: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/23.jpg)
El TAD LISTA• Modificadoras
![Page 24: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/24.jpg)
El TAD LISTA•
![Page 25: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/25.jpg)
El TAD LISTA
![Page 26: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/26.jpg)
El TAD LISTA• Implementación
![Page 27: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/27.jpg)
El TAD LISTA• Implementación
![Page 28: Estructuras Lineales : LISTAS](https://reader036.vdocumento.com/reader036/viewer/2022071604/62d0acdbc3aaec31956a44a2/html5/thumbnails/28.jpg)
El TAD LISTA