"Buch, um Programmierkenntnisse zu trainieren, um in der Welt zu kämpfen" Python-Code-Antwortbeispiel --2.4 Aufteilen der Liste
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(Kopf) -> 5 -> 8 -> 5 -> 10 -> 2 -> 1(letzte) -> 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)
chap2_function.py
#Knotenklasse
class Node:
#Konstrukteur
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
#Bidirektionale Listenklasse
class DoublyLinkedList:
#Konstrukteur
def __init__(self):
self.head = None
#Knoten vom ersten Knoten einfügen
def push(self, new_data):
#Knotengenerierung
new_node = Node(new_data)
#Machen Sie den nächsten Knoten des neuen Knotens zu dem, der an erster Stelle der Hauptknoten war
new_node.next = self.head
#Obwohl es sich in erster Linie um einen Kopfknoten handelte, wird der vorherige Knoten in einen neuen Knoten geändert
if self.head is not None:
self.head.prev = new_node
#Machen Sie den neuen Knoten zu einem Kopfknoten
self.head = new_node
#Einfügen eines Knotens an einem Zwischenpunkt
def insert(self, prev_node, new_data):
# prev_Geben Sie an, ob ein Knoten nach dem vom Knoten angegebenen Knoten eingefügt werden soll
#Wenn Keine, beenden Sie die Funktion
if prev_node is None:
print("the given previous node cannot be NULL")
return
#Knotengenerierung
new_node = Node(new_data)
#Zurück zum nächsten Knoten des neuen Knotens_Machen Sie es zum nächsten Knoten des vom Knoten angegebenen Knotens
new_node.next = prev_node.next
# prev_Macht den nächsten Knoten des vom Knoten angegebenen Knotens zu einem neuen Knoten
prev_node.next = new_node
#Zurück zum vorherigen Knoten des neuen Knotens_Machen Sie es zum Knoten, der vom Knoten angegeben wird
new_node.prev = prev_node
#Zurück zum nächsten Knoten des neuen Knotens_Ich habe es zum nächsten Knoten des in Knoten angegebenen Knotens gemacht, aber der vorherige Knoten dieses Knotens wird auch zu einem neuen Knoten gemacht
if new_node.next is not None:
new_node.next.prev = new_node
#Knoten vom letzten Knoten einfügen
def append(self, new_data):
#Knotengenerierung
new_node = Node(new_data)
#Keine Definition des nächsten Knotens des neuen Knotens
new_node.next = None
#Wenn kein Kopfknoten festgelegt ist (leere Liste), legen Sie einen neuen Knoten als Kopfknoten fest
if self.head is None:
new_node.prev = None
self.head = new_node
return
#Stellen Sie den endgültigen Knoten ein (Vorwärtsscannen)
last = self.head
while(last.next is not None):
last = last.next
#Legen Sie einen neuen Knoten als letzten Knoten fest
last.next = new_node
# 7.Machen Sie den vorherigen Knoten des neuen Knotens zum letzten Knoten an erster Stelle
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("Bidirektionale Liste: \n")
print("Vorwärtsscannen")
while(node is not None):
print(node.data,end="")
last = node
node = node.next
if node:
print(" -> ",end="")
else:
print("\n")
print("Reverse Scannen")
while(last is not None):
print(last.data,end="")
last = last.prev
if last:
print(" -> ",end="")
else:
print("\n")
if __name__ == '__main__':
#Generieren Sie eine leere bidirektionale Liste
# DLL: None
dll = DoublyLinkedList()
# DLL: None -> 6(Kopf/letzte) -> None
dll.append(6)
# DLL: None -> 7(Kopf) -> 6(letzte) -> None
dll.push(7)
# DLL: None -> 1(Kopf) -> 7 -> 6(letzte) -> None
dll.push(1)
# DLL: None -> 1(Kopf) -> 7 -> 6 -> 4(letzte) -> None
dll.append(4)
# DLL: None -> 1(Kopf) -> 7 -> 8 -> 6 -> 4(letzte) -> None
dll.insert(dll.head.next, 8)
# DLL: None -> 1(Kopf) -> 8 -> 6 -> 4(letzte) -> None
dll.delete(dll.head.next)
dll.printList(dll.head)
[1] GeeksforGeeks: Doubly Linked List | Set 1 (Introduction and Insertion) [2] GeeksforGeeks: Delete a node in a Doubly Linked List
Recommended Posts