es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Insertar un entero en una lista simplemente enlazada en orden ascendente.

06 Aug, 2023 Programación

Necesito definir el método insert_in_ascending_order() y no tengo idea de lo que estoy haciendo. Lo que necesito que haga el código es tomar la entrada:
Ejemplo:

8 3 6 2 5 9 4 1 7

y producir la salida:

1 2 3 4 5 6 7 8 9

class LinkedList:
    def <strong>init</strong>(self):
        self.head = None
        self.tail = None

def append(self, new_node):
    if self.head == None:
        self.head = new_node
        self.tail = new_node
    else:
        self.tail.next = new_node
        self.tail = new_node

def prepend(self, new_node):
    if self.head == None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head = new_node

def insert_after(self, current_node, new_node):
    if self.head == None:
        self.head = new_node
        self.tail = new_node
    elif current_node is self.tail:
        self.tail.next = new_node
        self.tail = new_node
    else:
        new_node.next = current_node.next
        current_node.next = new_node

# TODO: Escribir el método insert_in_ascending_order()
def insert_in_ascending_order(self, new_node):
    if self.head is None:
        new_node.next = self.head
        self.head = new_node
    elif self.head.data >= new_node.data:
        new_node.next = self.head
        self.head = new_node
    else :
        current = self.head

    current = self.head
    while current is not None:
        print (current.data)
        current = current.next
    new_node = current
    current = new_node

“`

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para definir el método insertar_en_orden_ascendente(), puedes comenzar iterando a través de la lista enlazada para encontrar la posición correcta donde insertar el nuevo nodo. Puedes comparar los datos de cada nodo con los datos del nuevo nodo y, cuando encuentres un nodo con datos mayores que el nuevo nodo, puedes insertar el nuevo nodo antes de ese nodo.

    Aquí tienes un ejemplo de cómo puedes implementar el método insertar_en_orden_ascendente():

    def insertar_en_orden_ascendente(self, nuevo_nodo):
    # si la lista enlazada está vacía, el nuevo_nodo se convierte en la cabeza
    if self.cabeza is None:
        self.cabeza = nuevo_nodo
        return

    # si los datos del nuevo_nodo son menores que los datos de la cabeza, el nuevo_nodo se convierte en la nueva cabeza
    if nuevo_nodo.dato < self.cabeza.dato:
        nuevo_nodo.siguiente = self.cabeza
        self.cabeza = nuevo_nodo
        return

    # encontrar la posición correcta para insertar el nuevo nodo
    actual = self.cabeza
    while actual.siguiente is not None and actual.siguiente.dato < nuevo_nodo.dato:
        actual = actual.siguiente

    # insertar el nuevo nodo
    nuevo_nodo.siguiente = actual.siguiente
    actual.siguiente = nuevo_nodo

    En esta implementación, el método primero verifica si la lista enlazada está vacía, en cuyo caso el nuevo nodo se convierte en la cabeza. Luego verifica si los datos del nuevo nodo son menores que los datos de la cabeza, en cuyo caso el nuevo nodo se convierte en la nueva cabeza.

    Después, itera a través de la lista enlazada para encontrar la posición correcta donde insertar el nuevo nodo. Se detiene cuando encuentra un nodo con datos mayores que el nuevo nodo o cuando llega al final de la lista enlazada.

    Finalmente, inserta el nuevo nodo antes del nodo encontrado o al final de la lista enlazada si el nuevo nodo tiene el valor de datos más grande.

    Para usar este método en la entrada 8 3 6 2 5 9 4 1 7, primero puedes crear una lista enlazada y agregar cada número a ella:

    lista_enlazada = ListaEnlazada()
for num in [8, 3, 6, 2, 5, 9, 4, 1, 7]:
    nuevo_nodo = Nodo(num)
    lista_enlazada.agregar(nuevo_nodo)

    Luego puedes llamar al método insertar_en_orden_ascendente() para cada nodo de la lista enlazada y ordenarla:

    actual = lista_enlazada.cabeza
while actual is not None:
    lista_enlazada.insertar_en_orden_ascendente(actual)
    actual = actual.siguiente

    Después de este bucle, la lista enlazada estará ordenada con la salida 1 2 3 4 5 6 7 8 9.

Comments are closed.