Implementiere eine verkettete Liste, die Sortieren und Suchen in Python unterstützt

Document 对象参考手册Python3-Beispiele

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))

Code-Erklärung:

  1. NodeKlasse: repräsentiert einen Knoten in der verketteten Liste, der Daten enthältdataund einen Zeiger auf den nächsten Knotennext。
  2. LinkedListKlasse: repräsentiert die verkettete Liste und enthält einen Zeiger auf den Kopf der Listehead。
  3. appendMethode: fügt einen neuen Knoten am Ende der verketteten Liste hinzu.
  4. displayMethode: gibt alle Elemente in der verketteten Liste aus.
  5. 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.
  6. 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: False

Document 对象参考手册Python3-Beispiele

Weitere Erweiterungen