Breaking

Post Top Ad

Your Ad Spot

viernes, 14 de junio de 2019

Clasificación y fusión de una sola lista enlazada

En el último artículo, comenzamos nuestra discusión sobre la lista enlazada. Vimos lo que es la lista enlazada junto con sus ventajas y desventajas. También estudiamos algunos de los métodos de lista enlazada más utilizados, como recorrido, inserción, eliminación, búsqueda y conteo de un elemento. Finalmente, vimos cómo revertir una lista enlazada.
En este artículo, continuaremos desde donde lo dejamos en el último artículo y veremos cómo ordenar una lista enlazada utilizando la ordenación de burbuja y combinación, y cómo combinar dos listas enlazadas ordenadas.
Antes de continuar, es imperativo mencionar que debe crear Nodey las LinkedListclases que creamos en el último artículo.

Ordenar una lista enlazada usando Bubble Sort

Hay dos formas de ordenar una lista enlazada usando la ordenación de burbuja :
  1. Intercambio de datos entre nodos
  2. Modificando los enlaces entre nodos.
En esta sección, veremos cómo funcionan estos dos enfoques. Usaremos el algoritmo de clasificación de burbuja para primero ordenar la lista enlazada cambiando los datos, y luego veremos cómo podemos usar la clasificación de burbuja para cambiar los enlaces a fin de ordenar la lista enlazada.

Ordenar la lista enlazada intercambiando datos

Para ordenar una lista enlazada mediante el intercambio de datos, tenemos que declarar tres variables pqend.
La variable pse inicializará con el nodo de inicio, mientras endque se establecerá en None.
Es importante recordar que para ordenar la lista con nelementos usando la ordenación por burbuja, necesita n-1iteraciones.
Para implementar el ordenamiento de burbujas, necesitamos dos bucles while. El bucle while externo se ejecuta hasta que el valor de la variable endes igual al self.start_node.
El bucle while interno se ejecuta hasta que se pvuelve igual a la endvariable. Dentro del bucle while externo, el valor de pse establecerá en self.start_nodecuál es el primer nodo. Dentro del bucle while interno, el valor de qse establecerá en el p.linkcual se encuentra el nodo al lado qLuego, los valores de pqse compararán si pes mayor que qlos valores de ambas variables se intercambiarán y luego se pseñalarán p.ref, que es el siguiente nodo. Finalmente, endse le asignará el valor de pEste proceso continúa hasta que se ordena la lista enlazada.
Entendamos este proceso con la ayuda de un ejemplo. Supongamos que tenemos la siguiente lista:
8,7,1,6,9  
Vamos a implementar nuestro algoritmo para ordenar la lista. Veremos qué ocurrirá durante cada iteración. El propósito de la clasificación de burbuja es que durante cada iteración, el valor más grande se debe enviar al final, por lo tanto, al final de todas las iteraciones, la lista se ordenará automáticamente.
Antes de que se ejecute el bucle, el valor de endse establece en None.
En la primera iteración, pse establecerá en 8 y qse establecerá en 7Como pes mayor que q, los valores serán intercambiados y pse convertirán p.refEn este momento, la lista enlazada se verá así:
7,8,1,6,9  
Como en este momento pno es igual a end, el bucle continuará y ahora pse convertirá en 8 y qse convertirá en 1. Ya que nuevamente pes mayor que q, los valores se intercambiarán de nuevo y pse volverán a convertir p.refLa lista se verá así:
7,1,8,6,9  
Aquí nuevamente, pno es igual a end, el bucle continuará y ahora pse convertirá en 8 y qse convertirá en 6. Ya que nuevamente pes mayor que q, los valores se intercambiarán nuevamente y pse volverán a convertir p.refLa lista se verá así:
7,1,6,8,9  
Nuevamente pno es igual a end, el bucle continuará y ahora pse convertirá en 8 y qse convertirá en 9. Aquí, ya pque no es mayor que q, los valores no se intercambiarán y pse convertirán p.refEn este punto del tiempo, la referencia de papuntará a None, y endtambién apunta a NonePor lo tanto, el bucle while interno se romperá y endse establecerá en p.
En el siguiente conjunto de iteraciones, el bucle se ejecutará hasta 8, ya que 9 ya está al final. El proceso continúa hasta que la lista está completamente ordenada.
El código de Python para ordenar la lista enlazada usando la ordenación de burbuja al intercambiar los datos es el siguiente:
    def bub_sort_datachange(self):
        end = None
        while end != self.start_node:
            p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.item, q.item = q.item, p.item
                p = p.ref
            end = p
Agregue el bub_sort_dataexchange()método a la LinkedListclase que creó en el último artículo.
Una vez que agregue el método a la lista vinculada, cree cualquier conjunto de nodos usando la make_new_list()función y luego use bub_sort_dataexchange()para ordenar la lista. Debería ver la lista ordenada cuando ejecute la traverse_list()función.
La ordenación de burbujas también se puede usar para ordenar una lista vinculada modificando los enlaces en lugar de cambiar los datos. El proceso sigue siendo bastante similar a la clasificación de la lista mediante el intercambio de datos, sin embargo, en este caso, tenemos una variable adicional rque siempre corresponderá al nodo anterior al pnodo.
Tomemos un ejemplo simple de cómo intercambiaremos dos nodos modificando enlaces. Supongamos que tenemos una lista enlazada con los siguientes elementos:
10,45,65,35,1  
Y queremos intercambiar 65 y 35. En este punto en el tiempo pcorresponde al nodo 65, y qcorresponde al nodo 35. La variable rcorresponderá al nodo 45 (anterior al nodo p). Ahora, si el nodo pes mayor que el nodo q, que es el caso aquí, p.refse establecerá en q.refq.refse establecerá en pDel mismo modo, r.refse establecerá en qEsto intercambiará los nodos 65 y 35.
El siguiente método implementa la clasificación de burbujas para la lista enlazada modificando los enlaces:
    def bub_sort_linkchange(self):
        end = None
        while end != self.start_node:
            r = p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.ref = q.ref
                    q.ref = p
                    if p != self.start_node:
                        r.ref = q
                    else:
                        self.start_node = q
                    p,q = q,p
                r = p
                p = p.ref
            end = p
Agregue el bub_sort_linkchange()método a la LinkedListclase que creó en el último artículo.
Una vez que agregue el método a la lista vinculada, cree cualquier conjunto de nodos usando la make_new_list()función y luego use bub_sort_linkchange()para ordenar la lista. Debería ver la lista ordenada cuando ejecute la traverse_list()función.

Fusionar la lista enlazada ordenada

En esta sección veremos cómo podemos combinar dos listas enlazadas ordenadas de manera que la lista enlazada resultante también esté ordenada. Hay dos enfoques para lograr esto. Podemos crear una nueva lista enlazada que contiene listas ordenadas individualmente o simplemente podemos cambiar los enlaces de las dos listas vinculadas para unirlas a la lista enlazada ordenada. En el segundo caso, no tenemos que crear una nueva lista enlazada.
Primero veamos cómo podemos combinar dos listas vinculadas creando una nueva lista.

Fusionar listas enlazadas ordenadas creando una nueva lista

Primero ejecutemos el algoritmo para ver cómo podemos combinar dos listas vinculadas ordenadas con la ayuda de una nueva lista.
Supongamos que tenemos las siguientes dos listas enlazadas ordenadas:
lista1:
10,45,65,  
lista2:
5,15,35,68  
Estas son las dos listas que queremos fusionar. El algoritmo es sencillo. Todo lo que se necesita es tres variables, pq, y em, y una lista vacía newlist.
Al comienzo del algoritmo, papuntará al primer elemento del list1mientras que qapuntará al primer elemento del list2La variable emestará vacía. Al inicio del algoritmo, tendremos los siguientes valores:
p = 10  
q = 5  
em = none  
newlist = none  
A continuación, vamos a comparar el primer elemento de la list1con el primer elemento de list2, en otras palabras, vamos a comparar los valores de pqy el valor más pequeño será almacenado en la variable emque se convertirá en el primer nodo de la nueva lista. El valor de emse agregará al final del archivo newlist.
Después de la primera comparación tendremos los siguientes valores:
p = 10  
q = 15  
em = 5  
newlist = 5  
Dado que qera menos que p, por lo tanto, almacenamos el valor de qen el empasado 'q' un índice a la derecha. En la segunda pasada tendremos los siguientes valores:
p = 45  
q = 15  
em = 10  
newlist = 5, 10  
Aquí ya pera más pequeño, añadimos el valor de pnewlist, y pusimos empy luego se trasladó pun índice a la derecha. En la siguiente iteración tenemos:
p = 45  
q = 35  
em = 15  
newlist = 5, 10, 15  
Del mismo modo, en la siguiente iteración:
p = 45  
q = 68  
em = 35  
newlist = 5, 10, 15, 35  
Y en la próxima iteración, pserá nuevamente más pequeño que q, por lo tanto:
p = 65  
q = 68  
em = 45  
newlist = 5, 10, 15, 35, 45  
Finalmente,
p = None  
q = 68  
em = 65  
newlist = 5, 10, 15, 35, 45, 65  
Cuando una de las listas se convierte None, todos los elementos de la segunda lista se agregan al final de la nueva lista. Por lo tanto, la lista final será:
p = None  
q = None  
em = 68  
newlist = 5, 10, 15, 35, 45, 65, 68  
El script de Python para fusionar dos listas ordenadas es el siguiente:
    def merge_helper(self, list2):
        merged_list = LinkedList()
        merged_list.start_node = self.merge_by_newlist(self.start_node, list2.start_node)
        return merged_list

    def merge_by_newlist(self, p, q):
        if p.item <= q.item:
            startNode = Node(p.item)
            p = p.ref
        else:
            startNode = Node(q.item)
            q = q.ref

        em = startNode

        while p is not None and q is not None:
            if p.item <= q.item:
                em.ref = Node(p.item)
                p = p.ref
            else:
                em.ref = Node(q.item)
                q = q.ref
            em = em.ref

        while p is not None:
            em.ref = Node(p.item)
            p = p.ref
            em = em.ref

        while q is not None:
            em.ref = Node(q.item)
            q = q.ref
            em = em.ref

        return startNode
En el script anterior tenemos dos métodos: merge_helper()merge_by_newlist()El primer método merge_helper()toma una lista vinculada como parámetro y luego pasa la selfclase, que es una lista vinculada en sí misma y la lista vinculada que se le pasa como parámetro, al merge_by_newlist()método.
El merge_by_newlist()método combina los dos enlaces mediante la creación de una nueva lista vinculada y devuelve el nodo de inicio de la nueva lista vinculada. Agregue estos dos métodos a la LinkedListclase. Crear dos nuevas listas enlazadas, ordenarlos mediante el bub_sort_datachange()o los bub_sort_linkchange()métodos que se han creado en la última sección y luego usar el merge_by_newlist()para ver si se puede fusionar dos listas o no ordenados vinculados.
En este enfoque, una nueva lista vinculada no se utiliza para almacenar la fusión de dos listas vinculadas ordenadas. Más bien, los enlaces de las dos listas vinculadas se modifican de tal manera que dos listas vinculadas se combinan de una manera ordenada.
Veamos un ejemplo simple de cómo podemos hacer esto. Supongamos que tenemos las mismas dos listas list1list2:
lista1:
10,45,65,  
lista2:
5,15,35,68  
Queremos combinarlos de una manera ordenada reorganizando los enlaces. Para ello necesitamos variables pqemInicialmente, tendrán los siguientes valores:
p = 10  
q = 5  
em = none  
newlist = none  
A continuación, vamos a comparar el primer elemento de la list1con el primer elemento de list2, en otras palabras, vamos a comparar los valores de pqy el valor más pequeño será almacenado en la variable emque se convertirá en el primer nodo de la nueva lista.
Después de la primera comparación tendremos los siguientes valores:
p = 10  
q = 15  
start = 5  
em = start  
Después de la primera iteración, ya que qes menor que p, el nodo de inicio apuntará hacia qqse convertirá q.refEl emserá igual a empezar. El emsiempre se referirá al nodo recién insertado en la lista fusionada.
p = 45  
q = 15  
em = 10  
Aquí, dado que pera más pequeña que la q, la variable emahora apunta hacia el valor original de py se pconvierte en p.ref.
p = 45  
q = 35  
em = 15  
Aquí como qera más pequeño pemapunta hacia qy se qhace q.ref.
p = 45  
q = 68  
em = 35  
Del mismo modo emaquí apunta hacia q.
p = 65  
q = 68  
em = 45  
newlist = 5, 10, 15, 35, 45  
Y aquí emapunta hacia donde se hace p.
p = None  
q = 68  
em = 65  
newlist = 5, 10, 15, 35, 45, 65  
Cuando una de las listas se convierte None, los elementos de la segunda lista simplemente se agregan al final.
p = None  
q = None  
em = 68  
newlist = 5, 10, 15, 35, 45, 65, 68  
La secuencia de comandos que contiene funciones para fusionar dos listas sin crear una nueva lista es la siguiente:
    def merge_helper2(self, list2):
        merged_list = LinkedList()
        merged_list.start_node = self.merge_by_linkChange(self.start_node, list2.start_node)
        return merged_list

    def merge_by_linkChange(self, p, q):
        if p.item <= q.item:
            startNode = Node(p.item)
            p = p.ref
        else:
            startNode = Node(q.item)
            q = q.ref

        em = startNode

        while p is not None and q is not None:
            if p.item <= q.item:
                em.ref = Node(p.item)
                em = em.ref
                p = p.ref
            else:
                em.ref = Node(q.item)
                em = em.ref
                q = q.ref


        if p is None:
            em.ref = q
        else:
            em.ref = p

        return startNode
En el script anterior tenemos dos métodos: merge_helper2()merge_by_linkChange()El primer método merge_helper2()toma una lista vinculada como parámetro y luego pasa la autoclase, que es una lista vinculada en sí misma y la lista vinculada que se le pasa como parámetro, a la merge_by_linkChange()que combina los dos enlaces mediante la modificación de los enlaces y devuelve el nodo de inicio de la lista fusionada. Agregue estos dos métodos a la LinkedListclase. Crear dos nuevas listas enlazadas, ordenarlos mediante el bub_sort_datachange()o los bub_sort_linkchange()métodos que se han creado en la última sección y luego usar el merge_by_newlist()para ver si se puede fusionar dos listas o no ordenados vinculados. Veamos este proceso en acción.
Crea una nueva lista enlazada usando el siguiente script:
new_linked_list1 = LinkedList()  
new_linked_list1.make_new_list()  
El script le pedirá el número de nodos para ingresar. Ingrese tantos nodos como desee y luego agregue valores para cada nodo como se muestra a continuación:
How many nodes do you want to create: 4  
Enter the value for the node:12  
Enter the value for the node:45  
Enter the value for the node:32  
Enter the value for the node:61  
A continuación, cree otra lista vinculada repitiendo el proceso anterior:
new_linked_list2 = LinkedList()  
new_linked_list2.make_new_list()  
A continuación, agregue algunos nodos ficticios con la ayuda del siguiente script:
How many nodes do you want to create: 4  
Enter the value for the node:36  
Enter the value for the node:41  
Enter the value for the node:25  
Enter the value for the node:9  
El siguiente paso es ordenar ambas listas. Ejecuta el siguiente script:
new_linked_list1. bub_sort_datachange()  
new_linked_list2. bub_sort_datachange()  
Finalmente, el siguiente script combina las dos listas vinculadas:
list3 = new_linked_list1.merge_helper2(new_linked_list2)  
Para ver si las listas se han fusionado, ejecute el siguiente script:
list3.traverse_list()  
La salida se ve así:
9  
12  
25  
32  
36  
41  
45  
61  

Conclusión

En este artículo, continuamos desde donde lo dejamos en el artículo anterior . Vimos cómo podemos ordenar las listas de combinación cambiando los datos y luego modificando los enlaces. Finalmente, también estudiamos diferentes formas de fusionar dos listas enlazadas ordenadas.
En el siguiente artículo , veremos cómo construir y realizar operaciones en listas con enlaces dobles.

No hay comentarios.:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Post Top Ad

Your Ad Spot

Páginas