Implementiere eine verkettete Liste, die Sortieren und Suchen in Python unterstützt
Wir werden Python verwenden, um eine einfache verkettete Liste zu implementieren und ihr Sortier- und Suchfunktionalität hinzuzufügen. Eine verkettete Liste ist eine übliche Datenstruktur, die aus einer Reihe von Knoten besteht, von denen jeder Daten und einen Zeiger auf den nächsten Knoten enthält.
Beispiel
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def sort(self):
if not self.head:
return
sorted_list = []
current = self.head
while current:
sorted_list.append(current.data)
current = current.next
sorted_list.sort()
self.head = None
for item in sorted_list:
self.append(item)
def search(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
# Beispielverwendung
ll = LinkedList()
ll.append(3)
ll.append(1)
ll.append(4)
ll.append(2)
print("Ursprüngliche verkettete Liste:")
ll.display()
ll.sort()
print("Sortierte verkettete Liste:")
ll.display()
print("Element 4 finden:", ll.search(4))
print("Element 5 finden:", ll.search(5))
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def sort(self):
if not self.head:
return
sorted_list = []
current = self.head
while current:
sorted_list.append(current.data)
current = current.next
sorted_list.sort()
self.head = None
for item in sorted_list:
self.append(item)
def search(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
# Beispielverwendung
ll = LinkedList()
ll.append(3)
ll.append(1)
ll.append(4)
ll.append(2)
print("Ursprüngliche verkettete Liste:")
ll.display()
ll.sort()
print("Sortierte verkettete Liste:")
ll.display()
print("Element 4 finden:", ll.search(4))
print("Element 5 finden:", ll.search(5))
Code-Erklärung:
NodeKlasse: repräsentiert einen Knoten in der verketteten Liste, der Daten enthältdataund einen Zeiger auf den nächsten Knotennext。LinkedListKlasse: repräsentiert die verkettete Liste und enthält einen Zeiger auf den Kopf der Listehead。appendMethode: fügt einen neuen Knoten am Ende der verketteten Liste hinzu.displayMethode: gibt alle Elemente in der verketteten Liste aus.sortMethode: sortiert die Elemente in der verketteten Liste. Zuerst werden die Daten aus der verketteten Liste in eine Liste extrahiert, dann wird die Liste sortiert und schließlich werden die sortierten Daten wieder in die verkettete Liste eingefügt.searchMethode: sucht nach dem angegebenen Element in der verketteten Liste und gibt es zurück, wenn es gefunden wird.True, andernfalls gibt sie zurückFalse。
Ausgabeergebnis:
原始链表: 3 -> 1 -> 4 -> 2 -> None 排序后的链表: 1 -> 2 -> 3 -> 4 -> None 查找元素 4: True 查找元素 5: FalseWeitere Erweiterungen
Python3-Beispiele