Unidad 3 Listas Enlazadas

3.1.1 Simples.
Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene
un nico campo de enlace. Una variable de referencia contiene una referencia al
primer nodo, cada nodo (excepto el ltimo) enlaza con el nodo siguiente, y el
enlace del ltimo nodo contiene

para indicar el final de la lista.
Aunque normalmente a la variable de referencia se la suele llamar top, usted
puede elegir el nombre que quiera. La siguiente figura presenta una lista de enlace
simple de tres nodos, donde top referencia al nodo A, A conecta con B y B conecta
con C y C es el nodo final:



Un algoritmo comn de las listas de enlace simple es la insercin de nodos. Este
algoritmo est implicado de alguna forma por que tiene mucho que ver con cuatro
casos: cuando el nodo se debe insertar antes del primer nodo; cuando el nodo se
debe insertar despus del ltimo nodo; cuando el nodo se debe insertar entre dos
nodos; y cuando la lista de enlace simple no existe. Antes de estudiar cada caso
consideremos el siguiente pseudocdigo:
DECLARE CLASS Nodo
DECLARE STRING name
DECLARE Node next
END DECLARE
DECLARE Node top = NULL
Este pseudocdigo declara una clase auto-referenciada llamada Nod con un
campo no de enlace llamado name y un campo de enlace llamado next. Tambin
declara una variable de referencia top (del tipo Node) que contiene una referencia
al primer Node de una lista de enlace simple. Como la lista todava no existe, el
valor inicial de top es NULL. Cada uno de los siguientes cuatro casos asume las
declaraciones de Node y top: La lista de enlace simple no existe:: Este es el caso
ms simple. Se crea un Node, se asigna su referencia a top, se inicializa su campo
no de enlace, y se asigna NULL a su campo de enlace. El siguiente pseudocdigo
realiza estas tareas:
Top = NEW Node
top.name = "A"
top.next = NULL
En la siguiente imagen se puede ver la lista de enlace simple que emerge del
pseudocdigo anterior:

El nodo debe insertarse antes del primer nodo:
Se crea un Node, se inicializa su campo no de enlace, se asigna la referencia de
top al campo de enlace next, y se asigna la referencia del Node recin creado a
top. El siguiente pseudocdigo (que asume que se ha ejecutado el pseudocdigo
anterior) realiza estas tareas:
DECLARE Node temp
Temp = NEW Node
temp.name = "B"
temp.next = top
Top = temp

El resultado del listado anterior aparece en la siguiente imagen:

El nodo debe insertarse detrs del ltimo nodo:
Se crea un Node, se inicializa su campo no de enlace, se asigna NULL al campo
de enlace, se atraviesa la lista de enlace simple hasta el ltimo Node, y se asigna
la referencia del Node recien creado al campo next del ltimo nodo. El siguiente
pseudocdigo realiza estas tareas:
Temp = NEW Node
temp.name = "C"
temp.next = NULL
DECLARE Node temp2
temp2 = top
// we assume top (and temp2) are not NULL
// because of the previous pseudocode
WHILE temp2.next IS NOT NULL
temp2 = temp2.next
END WHILE
// temp2 now references the last node
temp2.next = temp
La siguiente imagen revela la lista despus de la insercin del nodo C despus del
nodo A.


http://sistemas.itlp.edu.mx/tutoriales/estru1/422.gif
http://sistemas.itlp.edu.mx/tutoriales/estru1/423.gif
3.1.2 Dobles.

Una lista doble, doblemente ligada es una coleccin de nodos en la cual cada
nodo tiene dos punteros, uno de ellos apuntando a su predecesor (li) y otro a su
sucesor (ld). Por medio de estos punteros se podr avanzar o retroceder a travs
de la lista, segn se tomen las direcciones de uno u otro puntero.
La estructura de un nodo en una lista doble es la siguiente:

Existen dos tipos de listas doblemente ligadas:
Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo
del primer nodo como el derecho del ltimo nodo apuntan a NIL.
Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del
primer nodo apunta al ltimo nodo de la lista, y el puntero derecho del
ltimo nodo apunta al primer nodo de la lista.
Debido a que las listas dobles circulares son ms eficientes, los algoritmos que en
esta seccin se traten sern sobre listas dobles circulares. En la figura siguiente
se muestra un ejemplo de una lista doblemente ligada lineal que almacena
nmeros:

En la figura siguiente se muestra un ejemplo de una lista doblemente ligada
circular que almacena nmeros:

A continuacin mostraremos algunos algoritmos sobre listas enlazadas. Como ya
se mencion, llamaremos li al puntero izquierdo y ld al puntero derecho, tambin
usaremos el apuntador top para hacer referencia al primer nodo en la lista, y p
para referenciar al nodo presente.
Ejercicio 1
Ejercicio 2
Algoritmo de creacin
Top<--NIL
Repite
Si top=NIL entonces
New (p)
Lee (p (dato))
P (ld) <--p
P (li)<--p
Top <--p
En caso contrario
New (p)
lee(p(dato))
P (l d) <--top
P (li) <--p
P (l d (li)) <--p
Mensaje (otro nodo?)
Lee (respuesta)
Hasta respuesta=no
Algoritmo para recorrer la lista
--RECORRIDO A LA DERECHA.
p<--top
repite
Escribe (p (dato))
p<--p (LD)
Hasta p=top
--RECORRIDO A LA IZQUIERDA.
p<--top
Repite
Escribe (p (dato))
p<--p (li)
Hasta p=top (li)
Algoritmo para insertar antes de 'X' informacin
p<--top
Mensaje (antes de?)
Lee(x)
Repite
Si p (dato)=x entonces
New (q)
Leer (q(dato))
Si p=top entonces
Top <--q
Q (LD) <--p
Q (li) <--p (li)
P (ld (li)) <--q
P (li) <--q
p<--top
En caso contrario
p<--p (ld)
hasta p=top


Algoritmo para insertar despus de 'X' informacin
p<--top
Mensaje (despus de?)
Lee (x)
Repite
Si p (dato)=x entonces
New (q)
Lee (q (dato))
Q (ld) <--p (ld)
Q (li) <--p
P (li (ld)) <--q
P (LD) <--q
p<--top
En caso contrario
p<--p (ld)
Hasta p=top

Algoritmo para borrar un nodo
p<--top
Mensaje (Valor a borrar)
Lee (valor_a_borrar)
Repite
Si p (dato)=valor_a_borrar entonces
P (LD (li)) <--p (ld)
P (li (LD)) <--p (li)
Si p=top entonces
Si p (ld)=p(li) entonces
Top <--nil
En caso contrario
Top<--top (ld)
Dispose (p)
p<--top
En caso contrario
p<--p (ld)
Hasta p=top
http://sistemas.itlp.edu.mx/tutoriales/estru1/431.gif
3.1.3 Circulares.


Las listas circulares tienen la caracterstica de que el ltimo elemento de la misma
apunta al primero. La siguiente figura es una representacin grfica de una lista
circular.
Enseguida se mostrarn los algoritmos ms comunes en listas circulares. Al igual
que en las secciones anteriores, utilizaremos el apuntador top para hacer
referencia al primer nodo en la lista.
Algoritmo de creacin
Repite
New (p)
Lee (p(dato))
Si top=nil entonces
Top <--p
q<--p
En caso contrario
Q (liga) <--p
q<--p
p (liga) <--top
Mensaje (otro nodo?)
Lee (respuesta)
Hasta respuesta=no
Algoritmo para recorrer la lista
p<--top
Repite
Escribe (p (dato))
p<--p (liga)
Hasta p=top
Algoritmo para insertar antes de 'X' informacin
New (p)
Lee (p (dato))
Si top=nil entonces
Top <--p
P (liga) <--top
En caso contrario
Mensaje (antes de?)
Lee (x)
q<--top
r<--top (liga)
repite
Si q (dato)=x entonces
P (liga) <--q
R (liga) <--p
Si p (liga)=top entonces
Top <--p
q<--q (liga)
r<--r (liga)
Hasta q=top

Algoritmo para insertar despus de 'X' informacin
New (p)
Lee (p (dato))
Mensaje (despus de?)
Lee (x)
q<--top
r<--top (liga)
Repite
Si q (dato)=x entonces
Q (liga) <--p
P (liga) <--r
Q <--q (liga)
r<--r (liga)
Hasta q=top
Algoritmo para borrar
Mensaje (valor a borrar)
Lee (valor_a_borrar)
q<--top
r<--top
p<--top
Mientras q (liga)<>top has
q<--q (liga)
Repite
Si p (dato)=valor_a_borrar entonces
Si p=top entonces
Si top (liga)=top entonces
Top <--NIL
En caso contrario
Top <--top (liga)
Q (liga) <--top
En caso contrario
R (liga) <--p (liga)
Dispose (p)
p<--top
En caso contrario
r<--p
p<--p (liga)
Hasta p=top
3.1.4 Multilistas
Conjunto de nodos en que algunos tienen ms de un puntero y pueden
estar en ms de una lista simultneamente.
Para cada tipo de nodo es importante distinguir los distintos campos
punteros para realizar los recorridos adecuados y evitar confusiones.
Estructura bsica para Sistemas de Bases de Datos en Red.
Ejercicio manejo de case

IMPLEMENTACIN DE MULTILISTAS
Dados dos tipos de entidades, TipoA y TipoB, se necesitan:
Dos nuevos tipos correspondientes a los nodos para cada clase de entidad,
que junto con la informacin propia de la entidad incluye los punteros
necesarios para mantener la estructura.
. Typedef struct NodoTipoA {
. TipoA Info;
. NodoRelacion *PrimerB;
. } NodoTipoA;
. Typedef struct NodoTipoB {
. TipoB Info;
. NodoRelacion *PrimerA;
. } NodoTipoB;
. Una estructura para agrupar los objetos de cada tipo de entidad (Array, Lista,
rbol, Tabla Hash,
...).
Un TDA Nodo Relacin que incluye un puntero por cada lista as como
informacin propia de la relacin.
. Typedef struct NodoRelacion {
. NodoTipoA *SiguienteA;
. NodoTipoB *SiguienteB;
. <tipo1> campo1;
. ........
. <Tipon> campo_n;
. } NodoRelacion;
Un nodo Multilista que engloba los distintos tipos de nodos (entidad A, entidad B y
relacin). El tipo de dato para construir esto es el registro variante:
. typedef enum {NODO_A, NODO_B, NODO_ML} TipoNodo;
.
. Typedef struct NodoMultilista {
. TipoNodo tipo;
. Union {
. NodoTipoA a;
. NodoTipoB b;
. NodoRelacion nr;
. } cont;
. } NodoMultilista;
CONSULTA SOBRE UNA ESTRUCTURA MULTILISTA.
Localizar todas las entidades de TipoA relacionadas con la entidad B de TipoB.
Void BuscarEntidadesA (EntidadB B){
NodoMultilista a, b, r;
b = Direccion (B);
/* Depende de como se agrupen los NodoTipoB. */
r = b.cont.b.PrimerA;
/* Mediante r se recorre el conjunto de entidades TipoA para B. */
While (r.tipo == NODO_ML) {
a = r;
do
a = a.cont.nr.SiguienteB;
While (a.tipo == NODO_ML)
Escribe (a.cont.a.Info);
r = r.cont.nr.SiguienteA;
};
};















3.1.5 Clases para la implementacin de listas.
Implementaciones son:
Insert (x, p), insert el elemento x en la posicion p
End (), va a la posicion final de datos.(No necesariamenta la del arreglo)
Locate (x), retorna la posicion del elemento x.
Retrieve (p), retorna el elemento en la posicion p.
Delete (p) Delete (x),Borra la posicin p. Borra el o los elementos x.
Next (), Next (p), Posicin siguiente o posicion siguiente a p. La posicion siguiente
esta dada por el valor de la posicion actual. Maquinal (), Hace la lista nula,
necesario para comenzar nuevamente.
PrintList (), Muestra los valores de la lista.
Adicionalmente pueden agregar los metodos que uds encuentren necesarios por
Ejemplo.
Para el manejo del arreglo:
Mover (p), dejara vaca la posicin p para poder insertar un dato.
Redimencionar (x), Agrega una cantidad de datos x al arreglo.
Borrar (p), borra el dato en p y dezplaza todos los valores una posicion.
Recuerden que basicamente estamos trabajando con 3 variables:
El arreglo.
Variable de posicion Actual.
Variable de posicion Final.
Recuerden que estas variables como su nombre lo dice, con la ejecucion del
Codigo iran cambiando. Las 2 ultimas noson necesarias, pero pueden hacer el
funcionamiento de la Lista mucho mas rapido, y servira para futuras
implementacion que usaremos.