Algoritmo II Y Estructura de D.
Para insertar un dato d en una lista ligada hemos definido tres métodos en nuestra clase LSL: buscarDondeInsertar(d), insertar (d, y) y conectar (x, y). Analicemos cada uno de ellos. Es importante recordar que en este proceso de inserción se requiere que los datos de la lista se hallen ordenados en forma ascendente. Consideremos la siguiente lista y que se desea insertar el dato "g".
Lo primero que se debe hacer es determinar en qué sitio debe quedar la letra "g" para que se cumpla que los datos continúen ordenados en forma ascendente. Por observación, nos damos cuenta de que la "g" debe quedar entre la "f" y la "o", es decir, a continuación del nodo 9.
Nuestro primer método, buscaDondeInsertar(d), efectúa la tarea que determina a continuación de cual nodo debe
quedar el dato a insertar. El método para esta tarea es:
1. nodoSimple buscaDondeInsertar (Objeto d)
2. nodoSimple p, y
3. p = primerNodo ()
4. y = anterior(p)
5. while (no finDeRecorrido(p) and p. retornaDato () < d) do
6. y = p
7. p = p. retorna Liga ()
8. end(while)
9. return y
10. end(buscaDondeInsertar)
En este método se requieren dos variables auxiliares, las cuales llamamos p y y. con la variable p se recorre y a
medida que la vamos recorriendo se va comparando el dato de p (p. retornaDato ()) con el dato d que se desea
insertar. Mientras que el dato de p sea menor que d se avanza en la lista con p y con y. la variable y siempre estará
apuntando hacia a p. como inicialmente p es el primer nodo, inicialmente y es null. Fíjese que si el dato d a insertar
es menor que el dato del primer nodo de la lista simplemente ligada nuestro método retorna null. El hecho de que
nuestro método retorne null significa que el dato a insertar va a quedar de primero en la lista.
Veamos ahora como es el algoritmo para nuestro método Insertar (d, y):
1. void insertar (Objeto d, nodoSimple y)
2. nodoSimple x
3. x = nodoSimple(d)
4. conectar (x, y)
5. end(Método)
Nuestro método insertar consigue simplemente un nuevo nodo, lo carga con el dato d e invoca el método conectar. El parámetro y se refiere al nodo a continuación del cual habrá que conectar el nuevo x. Ocupémonos del método conectar (x, y):
Al ejecutar y = buscaDondeInsertar(d) con d = "g" en el objeto de la figura anterior y el método insertar (d, y), estamos en la situación mostrada en la figura siguiente:
Conectar el nodo x a continuación del nodo y implica que cuando lleguemos al nodo y debemos trasladarlo hacia el nodo x, o sea que el campo de liga del nodo y debe quedar valiendo 6, y cuando estemos en el nodo x debemos trasladarnos hacia el nodo 3, es decir, que el campo liga del nodo x debe quedar valiendo 3. O sea que, hay que modificar dos campos de liga: el campo de liga del nodo y y el campo de liga del nodo x. para lograr esto debemos ejecutar las siguientes instrucciones:
y. asigna Liga (y. retorna Liga ()) // modifica el campo de liga del nodo x
y. asigna Liga(x) // modifica el campo de liga del nodo y
y. asigna Liga (y. retorna Liga ()) // modifica el campo de liga del nodo x y. asigna Liga(x) // modifica el campo de liga del nodo y Y la lista queda así:
Conectar x a continuación de y se logra con las mismas instrucciones del caso 1, teniendo en cuenta que como el dato que se inserta queda de ultimo hay que actualizar la variable último. Lo anterior significa que las instrucciones para conectar x a continuación de y serán:
y. asigna Liga (y. retorna Liga ()) // modifica el campo de liga del nodo x
y. asigna Liga(x) // modifica el campo de liga del nodo y
if (y == ultimo)
then ultimo = x
end(if)
Presentemos a continuación un método que utiliza el método selección, el cual, se enuncia así: "de los datos que faltan por ordenar, determine cuál es el menor y colocarlo de primero en ese conjunto de datos".
1. void Ordena Ascendentemente ()
2. nodoSimple p, ap., menor, a menor, q, aq
3. p = primerNodo ()
4. ap. = anterior(p)
5. while (¡p! = ultimoNodo ())
6. menor = p
7. a menor = ap.
8. q = p. retorna Liga
9. aq =p
10. while (no finDeRecorrido(q))
11. if (q. retornaDato () < menor. RetornaDato ())
12. menor = q
13. a menor = aq
14. end(if) 15. aq =q
16. q = q. retorna Liga ()
17. end(while)
18. if (menor == p)
19. ap. = p
20. p = p. retorna Liga ()
21. else
22. desconectar (menor, a menor)
23. conectar (menor, ap.)
24. ap. = menor
25. end(if)
26. end(while)
27. end(Método)
3.4 TEMA 3 LISTA DOBLEMENTE LIGADAS:
Las listas doblemente ligadas son estructuras que permiten manejar la información de forma dinámica, donde el espacio donde se guarda la información es un nodo, que es una dirección de memoria dividida en tres partes, una parte para guardar la información, otra para la dirección al siguiente nodo y la otra para apuntar al nodo anterior, con estas listas se pueden realizar las operaciones de insertar, borrar, buscar, ordenar y todo bajo el concepto de memoria dinámica.
3.4.1 DEFINICIÓN DE CARACTERÍSTICAS :
Un nodo doble es un registro que tiene dos campos de liga: uno que llamaremos Li (Liga izquierda) y otro que llamaremos Ld (Liga derecha). Un dibujo para representar dicho nodo es:
IGA IZQUIERDA: ÁREA DE DATOS : LIGA DERECHA
Li: apunta hacia el nodo anterior.
Ld: apunta hacia el nodo siguiente.
Con base en esto vamos a definir una clase que llamaremos nodo Doble:
1. CLASE nodo Doble
2. Privado
3. Objeto dato
4. nodo Doble Li, Ld
5. publico
6. nodo Doble(objeto d) // constructor
7. void asigna Dato (objeto d)
8. void asignaLd (nodoDoble x)
9. void asignaLi (nodoDoble x)
10. objeto retornaDato ()
11. nodo Doble retornaLd ()
12. nodo Doble retornaLi ()
13. end(Clase)
Los algoritmos correspondientes a cada uno de estos métodos son los siguientes:
1. nodo Doble(objeto d) // constructor
2. dato = d
3. Ld = null
4. Li = null
5. end(nodo Doble)
1. void asigna Dato (objeto d)
2. dato = d
3. end(Método)
1. void asignaLd (nodo Doble x)
2. Ld. = x
3. end(asignaLd)
1. void asignaLi (nodoDoble x)
2. Li = x 3. end(asignaLi)
1. objeto retornaDato ()
2. return dato
3. end(retornaDato)
1. nodo Doble retorna(Li)
2. return Li
3. end(retornaLi)
1. nodo Doble Ld ()
2. return Ld
3. end(retornaLd)
Teniendo definida esta clase, procedemos a desarrollar un método en el cual hagamos uso de ella y de sus métodos. Consideremos que se tiene el conjunto de datos b, e, i, o, u, y que nuestro método los leerá en ese orden:
1. nodo Doble w, x, y, z
2. read(d)
3. w = new nodo Doble(d)
4. read(d)
5. x = new nodo Doble(d)
6. read(d)
7. y = new nodo Doble(d)
8. read(d)
9. z = new nodo Doble(d)
Continuemos nuestro algoritmo con estas instrucciones:
10. w. asignaLd(x)
11. x.asignaLi(w)
12. x.asignaLd(y)
13. y. asignaLi(x)
14. y. AsignaLd(z)
15. z. asignaLi(y)
Fíjese que el campo Ld del nodo w quedo valiendo 2, en virtud de la instrucción 10, lo cual indica que el nodo siguiente a w es el 2; el campo Li de x (el nodo 2) quedo valiendo 6, en virtud de la instrucción 11, lo cual significa
que el nodo anterior a x es el 6; el campo Ld del nodo x quedo valiendo 7, en virtud de la instrucción 12, lo cual quiere decir que el nodo siguiente a x es el 7. De una forma similar se han actualizado los campos Li y Ld de los nodos y y z. Asegúrese de entender bien el escenario actual.
Continuemos ejecutando las siguientes instrucciones:
16. w = null
17. y = null
18. z = null
Ahora ejecutemos estas otras instrucciones:
19. read(d)
20. y = new nodo Doble(d)
21. y. AsignaLd (x. retornaLd ())
22. y. asignaLi(x)
23. y. RetornaLd (). asignaLi(y)
24. x.asignaLd(y)
Ahora, al ejecutar esta instrucción:
25. y = null
26. x.retornaLi (). asignaLd (x. retornaLd ())
27. x.retornaLd (). asignaLi (x. retornaLi ())
