Listas

Listas Enlazadas
Una lista es una colección lineal de elementos que se llaman nodos. El
término colección lineal debe entenderse de la siguiente manera: tenemos
un primer y un último nodo, de tal manera que a cada nodo, salvo el último, le
corresponde un único sucesor, y a cada nodo, salvo el primero, le
corresponde un único predecesor. Se trata, pues, de una estructura de datos
cuyoselementos están situados secuencialmente.
Una definición del tipo listas se puede realizar usando punteros y registros.
Para ello se considera que cada nodo de la lista es un registro con dos
componentes: la primera almacena el contenido del nodo de la lista y, la
segunda un puntero que señala al siguiente elemento de la lista, si éste
existe, o con el valor nil (nulo) en caso de ser el último.Esta construcción de
las listas recibe el nombre de lista enlazada dinámica.
Esencialmente, una lista será representada como un puntero que señala al
principio (o cabeza) de la lista. La definición del tipo Lista de elementos de
tipo entero se presenta a continuación, junto con la declaración de una
variable del tipo lista:
Declaración
Lista: *Nodo
Nodo: Registro
Info: Entero
Sig: ListaFin Reg
L1: Lista
Operaciones con Lista
1. Limpiar

Procedimiento Inicializar (E/S L: Lista)
Inicio
L ← Nulo
Fin Procedimiento
2. Inserción de un nuevo elemento en la lista

Por el principio de la lista
Procedimiento Insertar_P.(E/S L:Lista; E dato:Entero)
Inicio
Crear (Nuevo)
Nuevo*.Info ← dato
Nuevo*.Sig ← L
L ← Nuevo
Fin Procedimiento
Por el final de la lista
ProcedimientoInsertar_F (E/S L: Lista; E dato: Entero)
Inicio
Crear (Nuevo)
Nuevo*.Info ← dato
Si (L = Nulo) entonces
Nuevo*.Sig ← Nulo
L ← Nuevo
Sino
Aux ← L
Mientras (Aux*.Sig Nulo) hacer
Aux ← Aux*.Sig
Fin mientras
Nuevo*.Sig ← Aux*.Sig
Aux*.Sig ← Nuevo
Fin Si
Fin Procedimiento
Antes de un dato referencia:
Procedimiento Insertar_Ant (E/S L:Lista; E dato, Ref : Entero)
Inicio
Crear (Nuevo)Nuevo*.Info ← dato
Aux ← L
Si (Aux*.Info = Ref) entonces
Nuevo*.Sig ← Aux
L ← Nuevo
Sino
Mientras (Aux Nulo and Aux*.Info Ref) hacer

Ant ← Aux
Aux ← Aux*.Sig
Fin mientras
Si (Aux*.Info = Ref) entonces
Nuevo*.Sig ← Aux
Ant*.Sig ← Nuevo
Sino
Imprimir “Dato referencia no encontrado”
Fin Si
Fin Si
Fin Procedimiento
Después de una dato referencia
Procedimiento Insertar_Des(E/S L: Lista; E dato, Ref : Entero)
Inicio
Crear (Nuevo)
Nuevo*.Info ← dato
Aux ← L
Mientras (Aux Nulo and Aux*.Info Ref) hacer
Aux ←Aux*.Sig
Fin mientras
Si (Aux*.Info = Ref) entonces
Nuevo*.Sig ← Aux*.Sig
Aux*.Sig ← Nuevo
Sino
Imprimir “Dato referencia no encontrado”
Fin Si
Fin Procedimiento
3.- Suprimir un elemento en la lista
El primer nodo de la lista
ProcedimientoEliminar_Pincipio (E/S L: Lista)
Inicio
Aux ← L
Si (Aux*.Sig = Nulo) entonces
L← Nulo
Sino
L ← Aux*.Sig

Fin Si
Liberar (Aux)
Fin Procedimiento
El último nodo de la lista
Procedimiento Eliminar_Final (E/S L: Lista)
Inicio
Aux ← L
Ant ← L
Si (Aux*.Sig = Nulo) entonces
L ← Nulo
Sino
Mientras (Aux Nulo) hacer
Ant ← Aux
Aux ← Aux*.Sig
Fin mientras
Ant*.Sig ← Nulo
Fin Si
Liberar (Aux)Liberar (Ant)
Fin Procedimiento
Un dato referencia:
Procedimiento Eliminar_Ref (E/S L: Lista; E Ref : Entero)
Inicio
Aux ← L
Si (Aux*.Info = Ref) entonces
L ← Aux*.Sig
Sino
Mientras (Aux Nulo and Aux*.Info Ref) hacer
Ant ← Aux
Aux ← Aux*.Sig
Fin mientras
Si (Aux*.Info = Ref) entonces
Ant*.Sig ← Aux*.Sig
Fin Si
Fin Si
Liberar (Aux)
Liberar (Ant)

Fin Procedimiento
4.-Verificar el estado de la lista
Lógica función vacía (E/S L: Lista)
Inicio
Si (L = Nulo) entonces
Devolver verdadero
Sino
Devolver falso
Fin Si
Fin función
Ejercicios Listas Enlazadas
Ejercicios
1.- Diseñe un algoritmo que almacene en una lista enlazada el promedio de
2 notas de un grupo de estudiantes, además determine e imprima el
promedio del grupo y muestre los promedios de los...