"Livre pour former des compétences en programmation pour combattre dans le monde" Exemple de réponse de code Python --2.4 Fractionnement de la liste

CHAP2. Liste concaténée

Exemple de solution de code Python

`python`



from chap2_function import* 

def partition(node,x):
    
    beforeStart = None
    beforeEnd = None

    afterStart = None
    afterEnd = None

    while node:

        next_node = node.next
        node.next = None
        node.prev = None

        if node.data < x:

            if beforeStart == None:
                beforeStart = node
                beforeEnd = beforeStart
            else:
                prev_node = beforeEnd
                beforeEnd.next = node
                beforeEnd = node
                beforeEnd.prev = prev_node

        else:

            if afterStart == None:
                afterStart = node
                afterEnd = afterStart
            else:
                prev_node = afterEnd
                afterEnd.next = node
                afterEnd = node
                afterEnd.prev = prev_node

        node = next_node

    if beforeStart == None:
        return afterStart

    afterStart.prev = beforeEnd
    beforeEnd.next = afterStart

    return beforeStart

dll = DoublyLinkedList() 

# DLL: None -> 3(tête) -> 5 -> 8 -> 5 -> 10 -> 2 -> 1(dernier) -> None 
dll.append(3)  
dll.append(5) 
dll.append(8) 
dll.append(5) 
dll.append(10) 
dll.append(2) 
dll.append(1) 

dll.printList(dll.head) 

partition(dll.head,5)

dll.printList(dll.head)

Fonctions Python (classe de nœuds, classe de liste bidirectionnelle)

`chap2_function.py`


#Classe de nœud
class Node: 
  
    #constructeur
    def __init__(self, data): 
        self.data = data 
        self.next = None
        self.prev = None
  
#Classe de liste bidirectionnelle
class DoublyLinkedList: 
  
    #constructeur
    def __init__(self): 
        self.head = None
  
    #Insérer un nœud à partir du premier nœud
    def push(self, new_data): 
  
        #Génération de nœuds
        new_node = Node(new_data) 
  
        #Faites du nœud suivant du nouveau nœud le nœud principal en premier lieu
        new_node.next = self.head 
  
        #Bien qu'il s'agisse d'un nœud principal au départ, le nœud précédent est remplacé par un nouveau nœud
        if self.head is not None: 
            self.head.prev = new_node 
  
        #Faire du nouveau nœud un nœud principal
        self.head = new_node 
  
    #Insérer un nœud à un point intermédiaire
    def insert(self, prev_node, new_data): 
  
        # prev_Spécifiez s'il faut insérer un nœud après le nœud spécifié par nœud
        #Si aucun, quitte la fonction
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
  
        #Génération de nœuds
        new_node = Node(new_data) 
  
        #Précédente le nœud suivant du nouveau nœud_Faites-en le nœud suivant du nœud spécifié par nœud
        new_node.next = prev_node.next
  
        # prev_Fait du nœud suivant du nœud spécifié par nœud un nouveau nœud
        prev_node.next = new_node 
  
        #Précédent le nœud précédent du nouveau nœud_Faites-en le nœud spécifié par nœud
        new_node.prev = prev_node 
  
        #Précédente le nœud suivant du nouveau nœud_J'en ai fait le nœud suivant du nœud spécifié dans node, mais le nœud précédent de ce nœud est également transformé en nouveau nœud
        if new_node.next is not None: 
            new_node.next.prev = new_node 
  
    #Insérer le nœud du dernier nœud
    def append(self, new_data): 
  
        #Génération de nœuds
        new_node = Node(new_data) 
  
        #Aucune définition du nœud suivant du nouveau nœud
        new_node.next = None
  
        #Si aucun nœud principal n'est défini (liste vide), définissez un nouveau nœud comme nœud principal
        if self.head is None: 
            new_node.prev = None
            self.head = new_node 
            return 
  
        #Définir le nœud final (scan avant)
        last = self.head 
        while(last.next is not None): 
            last = last.next
  
        #Désignez un nouveau nœud comme dernier nœud
        last.next = new_node 
  
        # 7.Faire du nœud précédent du nouveau nœud le dernier nœud en premier lieu
        new_node.prev = last 
  
        return
  
    def delete(self,del_node):

        if self.head == None or del_node == None: 
            return 

        if self.head == del_node: 
            self.head = del_node.next

        if del_node.next != None: 
            del_node.next.prev = del_node.prev 

        if del_node.prev != None: 
            del_node.prev.next = del_node.next

    def printList(self, node): 
  
        print("Liste bidirectionnelle: \n") 

        print("Balayage avant")
        while(node is not None): 
            print(node.data,end="") 
            last = node 
            node = node.next
            if node:
                print(" -> ",end="")
            else:
                print("\n")
  
        print("Balayage inversé")
        while(last is not None): 
            print(last.data,end="")
            last = last.prev 
            if last:
                print(" -> ",end="")
            else:
                print("\n")
  
if __name__ == '__main__':
    #Générer une liste bidirectionnelle vide
    # DLL: None
    dll = DoublyLinkedList() 
    # DLL: None -> 6(tête/dernier) -> None
    dll.append(6) 
    # DLL: None -> 7(tête) -> 6(dernier) -> None 
    dll.push(7) 
    # DLL: None -> 1(tête) -> 7 -> 6(dernier) -> None 
    dll.push(1) 
    # DLL: None -> 1(tête) -> 7 -> 6 -> 4(dernier) -> None 
    dll.append(4) 
    # DLL: None -> 1(tête) -> 7 -> 8 -> 6 -> 4(dernier) -> None 
    dll.insert(dll.head.next, 8) 
    # DLL: None -> 1(tête) -> 8 -> 6 -> 4(dernier) -> None 
    dll.delete(dll.head.next) 
    dll.printList(dll.head)

Les références

[1] GeeksforGeeks: Doubly Linked List | Set 1 (Introduction and Insertion) [2] GeeksforGeeks: Delete a node in a Doubly Linked List