Lineare Datenstruktur

In diesem Kapitel stellen wir eine der grundlegendsten und am häufigsten verwendeten Arten von Datenstrukturen vor—lineare Datenstruktur。

Lineare DatenstrukturGenau wie eine Reihe von Menschen, die in einer Schlange stehen:

  • Jede Person (Element) hat eine klare Vorher-Nachher-Beziehung
  • Außer der ersten und der letzten hat jede Person einen Vorgänger und einen Nachfolger
  • Die Datenelemente haben eine lineare Eins-zu-eins-Beziehung

Stell dir vor, du stehst in der Schlange, um Kaffee zu kaufen, oder ordnest Bücher in einem Regal.

Diese Szenarien haben eine Gemeinsamkeit: Elemente sind hintereinander angeordnet und bilden eine Linie.

In der Informatik ist eine solche geordnete Sammlung von Daten eine lineare Datenstruktur.

Die Eigenschaft einer linearen Datenstruktur ist: Außer dem ersten und letzten Element hat jedes Element genau einenVorgängerund einenNachfolger。

Häufige lineare Datenstrukturen:

  1. Array: wie eine Reihe nummerierter Schließfächer, jedes Schließfach hat eine feste Position
  2. Verkettete Liste: wie eine Kette von Menschen, die sich an den Händen halten, jede Person erinnert sich nur an die Personen vor und hinter sich
  3. Stack: Wie ein Stapel Teller, Elemente können nur oben entnommen und abgelegt werden
  4. Queue: Wie beim Anstehen zum Ticketkauf, wer zuerst kommt, wird zuerst bedient

Die folgende Abbildung zeigt die Taxonomie linearer Datenstrukturen. Jede Struktur hat ihre spezifischen Anwendungsszenarien und Leistungsmerkmale:

Die folgende Abbildung zeigt den grundlegenden Operationsablauf eines Stacks, der dem LIFO-Prinzip (Last In, First Out) folgt:

Array

Statisches Array

Funktionen Beschreibung Zeitkomplexität
Zugriff auf Elemente Direkter Zugriff über den Index O(1)
Element einfügen Nachfolgende Elemente müssen verschoben werden O(n)
Element löschen Nachfolgende Elemente müssen verschoben werden O(n)
Speicherzuweisung Feste Größe, vorab zugewiesen O(1)

Dynamisches Array

Funktionen Beschreibung Zeitkomplexität
Zugriff auf Elemente Direkter Zugriff über den Index O(1)
Element einfügen Kann Größenänderung und Kopieren erfordern Durchschnittlich O(1), im schlimmsten Fall O(n)
Element löschen Nachfolgende Elemente müssen verschoben werden O(n)
Speicherzuweisung Automatische Größenänderung O(n) (bei Größenänderung)

Verkettete Liste

Einfach verkettete Liste

Aktion Beschreibung Zeitkomplexität
Zugriff auf Elemente Muss vom Anfang aus durchlaufen werden O(n)
Einfügen am Anfang Direkte Einfügung O(1)
Einfügen am Ende Muss bis zum Ende durchlaufen werden O(n)
Einfügung in der Mitte Position muss zuerst gefunden werden O(n)
Element löschen Position muss zuerst gefunden werden O(n)

Doppelt verkettete Liste

Aktion Beschreibung Zeitkomplexität
Zugriff auf Elemente Muss vom Kopf oder Ende aus durchlaufen werden O(n)
Einfügen am Anfang Direkte Einfügung O(1)
Einfügen am Ende Direktes Einfügen (falls ein Endzeiger vorhanden ist) O(1)
Einfügung in der Mitte Position muss zuerst gefunden werden O(n)
Element löschen Position muss zuerst gefunden werden O(n)

Stapel

Aktion Beschreibung Zeitkomplexität
push Ein Element oben auf dem Stack hinzufügen O(1)
pop Das oberste Element des Stacks entfernen O(1)
peek(Ansicht) Das oberste Element des Stacks anzeigen O(1)
isEmpty(Leerheitsprüfung) Prüfen, ob der Stack leer ist O(1)

Warteschlange

Aktion Beschreibung Zeitkomplexität
enqueue Ein Element am Ende der Warteschlange hinzufügen O(1)
dequeue Das Kopfelement der Warteschlange entfernen O(1)
front (vorderes Ende der Warteschlange anzeigen) Das Kopfelement der Warteschlange anzeigen O(1)
isEmpty(Leerheitsprüfung) Prüfen, ob die Warteschlange leer ist O(1)

Vergleichsdiagramm linearer Datenstrukturen


Array: ein festes Wohnhaus für Daten

Arrays sind die einfachste und geradlinigste lineare Datenstruktur.

Wir können es uns als ein Gebäude vorstellenEin Wohnhaus mit einer festen Anzahl von Stockwerken。

Grundlegende Konzepte und Eigenschaften

  • Zusammenhängende SpeicherungEin Array belegt einen zusammenhängenden Block im SpeicherZusammenhängendDer Speicherplatz ist wie Zimmer in einem Wohnhaus, die direkt nebeneinander liegen.
  • Feste Größe: Die Kapazität (Länge) eines Arrays muss bei der Erstellung festgelegt werden und kann danach normalerweise nicht geändert werden, so wie die Anzahl der Zimmer in einem Wohnhaus feststeht, sobald es gebaut ist.
  • Indexzugriff: Jedes Element (Zimmer) hat eine eindeutige Nummer, die manIndexnennt. In den meisten Programmiersprachen beginnt die Indizierung bei0Beginnend bei. Sie können direkt und schnell über seinen Index auf jedes Element zugreifen, mit einer Zeitkomplexität vonO(1)。

Kernoperationen und Codebeispiele

Lassen Sie uns Arrays mit Python demonstrieren (in Python verwenden wir normalerweiselistum zu simulieren, aber beachten Sie, dass Pythonslistdie dynamisch ist) Kernoperationen.

Beispiel

# 1. Ein Array erstellen
apartment_building = ['Zimmer 101 - Zhang San', 'Zimmer 102 - Li Si', 'Zimmer 103 - Wang Wu', 'Zimmer 104 - unbesetzt', 'Zimmer 105 - unbesetzt']
print("Bewohner des Apartmenthauses:", apartment_building)

# 2. Auf Elemente zugreifen (über Index)
# Auf Zimmer 102 zugreifen
tenant = apartment_building[1] # Index beginnt bei 0, daher entspricht 1 dem zweiten Element
print(f"Der Bewohner von Zimmer 102 ist: {tenant}")

# 3. Elemente aktualisieren
# Ein neuer Bewohner Zhao Liu ist in Zimmer 104 eingezogen
apartment_building[3] = 'Zimmer 104 - Zhao Liu'
print("Nachdem Zhao Liu eingezogen ist:", apartment_building)

# 4. Elemente einfügen (das Hinzufügen am Ende ist relativ effizient, simuliert "Erweiterung")
# Angenommen, wir dürfen am Ende ein Zimmer 106 hinzufügen
apartment_building.append('Zimmer 106 - Sun Qi')
print("Nach dem Hinzufügen von Zimmer 106:", apartment_building)

# 5. Elemente löschen
# Wang Wu ist aus Zimmer 103 ausgezogen
# Methode 1: Als frei markieren (logisches Löschen)
# apartment_building[2] = 'Zimmer 103 - frei'

# Methode 2: Das Element entfernen; nachfolgende Elemente müssen nach vorne verschoben werden (physisches Löschen, relativ ineffizient)
removed_tenant = apartment_building.pop(2) # Entferne das Element an Index 2
print(f"{removed_tenant} ist ausgezogen.")
print("Nachdem Wang Wu ausgezogen ist:", apartment_building)

Ausgabe:

寓楼住户情况: ['101室-张三', '102室-李四', '103室-王五', '104室-空置', '105室-空置']
102室的住户是:102室-李四
赵六入住后: ['101室-张三', '102室-李四', '103室-王五', '104室-赵六', '105室-空置']
加盖106室后: ['101室-张三', '102室-李四', '103室-王五', '104室-赵六', '105室-空置', '106室-孙七']
103室-王五 已搬走。
王五搬走后: ['101室-张三', '102室-李四', '104室-赵六', '105室-空置', '106室-孙七']

Vorteile und Nachteile

Vorteile Nachteile
Schneller wahlfreier Zugriff: Jedes Element kann in konstanter Zeit über seinen Index erreicht werden. Feste Größe: Sobald ein statisches Array erstellt wurde, ist seine Kapazität schwer zu ändern.
Hohe Speichereffizienz: Zusammenhängende Speicherung, kein zusätzlicher Speicherplatz zum Speichern von Beziehungen zwischen Elementen erforderlich. Hohe Einfüge-/Löschkosten: Das Einfügen oder Löschen von Elementen in der Mitte erfordert das Verschieben vieler nachfolgender Elemente, um die Zusammenhängigkeit zu erhalten.

Verkettete Liste: ein Schatzsuche-Zug für Daten

Wenn die feste Größe von Arrays und die Ineffizienz beim Einfügen/Löschen zum Problem werden, kommen verkettete Listen ins Spiel. Eine verkettete Liste ist wie ein ZugTrain, jeder Waggon (Knoten) trägt Fracht (Daten) und ist über eine Kupplung (Zeiger) mit dem nächsten Waggon verbunden.

Grundlegende Konzepte und Typen

Jeder Knoten der verketteten ListeKnotenenthält mindestens zwei Teile:

  1. DatenfeldSpeichert den tatsächlichen Datenwert.
  2. Zeigerfeld: Speichert die Adresse des nächsten Knotens im Speicher.

Die obige Abbildung zeigt eineeinfach verkettete ListeStruktur. Der Kopfzeiger zeigt auf den ersten Knoten, und jedes KnotensNextZeiger zeigt auf den nächsten Knoten, und der Zeiger des letzten KnotensNextZeigt aufNULLMarkiert das Ende der verketteten Liste.

Haupttypen von verketteten Listen:

  • Einfach verkettete ListeDer Knoten zeigt nur auf den nächsten Knoten.
  • Doppelt verkettete Liste: Knoten zeigen sowohl auf den vorherigen als auch auf den nächsten Knoten, was eine bidirektionale Traversierung ermöglicht.
  • Zirkuläre verkettete Liste: Der Endknoten zeigt auf den Kopfknoten und bildet einen Ring.

Kernoperationen und Codebeispiele

Lass uns eine einfache, einfach verkettete Liste implementieren.

Beispiel

class ListNode:
    """Definiere die Knotenklasse der verketteten Liste"""
    def __init__(self, data):
        self.data = data  # Datenfeld
        self.next = None  # Zeigerfeld, zeigt anfangs auf null

class LinkedList:
    """Definiere eine Klasse für eine einfach verkettete Liste"""
    def __init__(self):
        self.head = None  # Kopfzeiger der verketteten Liste

    def append(self, data):
        """Füge einen Knoten am Ende der verketteten Liste hinzu"""
        new_node = ListNode(data)
        if not self.head:  # Wenn die verkettete Liste leer ist, wird der neue Knoten zum Kopfknoten
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:  # Bis zum letzten Knoten durchlaufen
            last_node = last_node.next
        last_node.next = new_node  # Den neuen Knoten am Ende anhängen

    def prepend(self, data):
        """Fügt einen Knoten am Kopf der verketteten Liste hinzu"""
        new_node = ListNode(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, key):
        """Löscht den ersten Knoten mit dem Wert key"""
        current_node = self.head

        # Falls der zu löschende Knoten der Kopfknoten ist
        if current_node and current_node.data == key:
            self.head = current_node.next
            current_node = None
            return

        prev_node = None
        # Durchlaufen, um den zu löschenden Knoten zu finden
        while current_node and current_node.data != key:
            prev_node = current_node
            current_node = current_node.next

        if current_node is None:  # Nicht gefunden
            return

        # Sobald gefunden, den Knoten überspringen, um die Verbindung herzustellen
        prev_node.next = current_node.next
        current_node = None

    def print_list(self):
        """Alle Elemente der verketteten Liste ausgeben"""
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("NULL")

# Teste die verkettete Liste
print("=== Demo für Operationen mit einfach verketteter Liste ===")
train = LinkedList()
train.append("Wagen 1 - Kohle")
train.append("Wagen 2 - Holz")
train.prepend("Lokomotive")  # Am Kopf einfügen
train.append("Wagen 3 - Stahl")
print("Anfänglicher Zug:")
train.print_list()  # Ausgabe: Lokomotive -> Wagen 1 - Kohle -> Wagen 2 - Holz -> Wagen 3 - Stahl -> NULL

train.delete("Wagen 2 - Holz")
print("Nach dem Entladen des Holzes:")
train.print_list()  # Ausgabe: locomotive -> carriage1-coal -> carriage3-steel -> NULL

Ausgabe:

=== 单向链表操作演示 ===
初始列车:
车头 -> 车厢1-煤炭 -> 车厢2-木材 -> 车厢3-钢材 -> NULL
卸下木材后:
车头 -> 车厢1-煤炭 -> 车厢3-钢材 -> NULL

Vorteile und Nachteile

Vorteile Nachteile
Dynamische Größe: Kein Bedarf, festen Speicherplatz vorab zuzuweisen; sie kann flexibel wachsen und schrumpfen. Speicheraufwand: Jeder Knoten benötigt zusätzlichen Speicherplatz, um einen Zeiger zu speichern.
Effizientes Einfügen/Löschen: Wenn die Position eines Knotens bekannt ist, muss man nur Zeiger ändern, ohne viele Elemente zu verschieben. Sequenzieller Zugriff: Anders als bei Arrays kann nicht direkt über den Index auf Elemente zugegriffen werden; man muss vom Kopf aus durchlaufen.
Cache-unfreundlich: Knoten sind im Speicher verstreut, was dem CPU-Cache-Prefetching nicht förderlich ist.

Stack: Tellerstapel für Daten

Ein Stack ist eineLast-in, first-outDatenstruktur, wie gestapelte Teller in einem Restaurant, man nimmt immer den obersten (den zuletzt aufgelegten).

Grundlegende Konzepte und Operationen

Der Stack erlaubt Operationen nur an einem Ende (genanntStack-Spitze), um einzufügen (Push) und zu löschen (Pop) Operationen. Das andere Ende heißtStack-Boden。

Kernoperationen:

  • push(data)Daten oben auf den Stapel legen.
  • pop()Das oberste Element des Stapels entnehmen und zurückgeben.
  • peek() / top()Das oberste Element des Stapels anzeigen, ohne es zu entnehmen.
  • is_empty()Prüfen, ob der Stapel leer ist.

Anwendungsszenarien und Codebeispiele

Stapel werden in der Informatik äußerst häufig verwendet, z. B. Funktionsaufruf-Stapel, Vorwärts-/Rückwärtsnavigation im Browser, Auswertung von Ausdrücken, Klammerabgleich usw.

Beispiel

class Stack:
    """Liste verwenden, um Stapel zu implementieren"""
    def __init__(self):
        self.items = []

    def push(self, item):
        """Einfügen"""
        self.items.append(item)  # Das Ende der Liste als Stapeloberseite verwenden

    def pop(self):
        """Pop, gebe None zurück, wenn der Stack leer ist"""
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        """Peek auf das oberste Element"""
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        """Prüfe, ob der Stack leer ist"""
        return len(self.items) == 0

    def size(self):
        """Gib die Größe des Stacks zurück"""
        return len(self.items)

# Anwendungsbeispiel: Klammerpaarungsprüfung
def is_balanced_parentheses(expression):
    """
Prüfe, ob die Klammern im Ausdruck übereinstimmen
Zum Beispiel: (()) ist balanciert, (() ist unbalanciert
    """

    stack = Stack()
    # Zuordnung der Klammerpaare
    matching_bracket = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':  # Wenn es eine linke Klammer ist, auf den Stack legen
            stack.push(char)
        elif char in ')]}':  # Wenn es eine rechte Klammer ist
            if stack.is_empty():
                return False  # Stack ist leer, also gibt es zu viele schließende Klammern
            top_char = stack.pop()
            if matching_bracket[char] != top_char:  # Prüfen, ob sie übereinstimmen
                return False
    # Nach der Schleife sollte der Stack leer sein
    return stack.is_empty()

# Stack- und Klammerabgleich testen
print("\n=== Stack- und Klammerabgleich-Demo ===")
plate_stack = Stack()
plate_stack.push("Teller 1")
plate_stack.push("Teller 2")
plate_stack.push("Teller 3")
print(f"Nimm den obersten Teller heraus: {plate_stack.pop()}")  # Ausgabe: Teller 3
print(f"Jetzt ist der oberste Teller: {plate_stack.peek()}")  # Ausgabe: Teller 2

# Klammerabgleich testen
test_cases = ["((1+2)*3)", "({[ ]})", "((())", ")( )"]
for test in test_cases:
    result = ausgeglichen if is_balanced_parentheses(test) else unausgeglichen
    print(fDie Klammern im Ausdruck '{test}' sind {result}.)

Ausgabe:

=== 栈与括号匹配演示 ===
取出最上面的盘子: 盘子3
现在最上面的盘子是: 盘子2
表达式 '((1+2)*3)' 的括号是 平衡 的。
表达式 '({[ ]})' 的括号是 平衡 的。
表达式 '((())' 的括号是 不平衡 的。
表达式 ')( )' 的括号是 不平衡 的。

Warteschlange: ein Warteschlangenkanal für Daten

Eine Warteschlange ist eineFirst-In-First-OutDatenstruktur, wie an jedem Ort im Leben, an dem man anstehen muss (z. B. Supermarktkasse), werden die zuerst Ankommenden zuerst bedient.

Grundlegende Konzepte und Operationen

Die Warteschlange ermöglicht an einem Ende (genanntEnde) das Einfügen (Enqueue) von Operationen und am anderen Ende (genanntKopf) das Löschen (Dequeue) einer Operation.

Kernoperationen:

  • enqueue(data)Fügt Daten am Ende der Warteschlange hinzu.
  • dequeue()Entfernt Daten vom Kopf der Warteschlange und gibt sie zurück.
  • front() / peek()Zeigt die Daten am Kopf der Warteschlange an, ohne sie zu entfernen.
  • is_empty()Prüft, ob die Warteschlange leer ist.

Anwendungsszenarien und Codebeispiele

Warteschlangen werden häufig in Szenarien verwendet, in denen Aufgaben in der Reihenfolge verarbeitet werden müssen, z. B.: Warteschlangen für Druckaufträge, Nachrichtenwarteschlangen, Breitensuche usw.

Beispiel

from collections import deque  # Verwende Pythons deque, das effiziente Operationen am Kopf und am Ende bietet

class Queue:
    """Implementiere eine Warteschlange mit collections.deque"""
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        """Einreihen"""
        self.items.append(item)  # Von rechts hinzufügen (Ende)

    def dequeue(self):
        """Ausreihen, gibt None zurück, wenn die Warteschlange leer ist"""
        if not self.is_empty():
            return self.items.popleft()  # Von links entfernen (Kopf)
        return None

    def front(self):
        """Das vorderste Element ansehen"""
        if not self.is_empty():
            return self.items[0]
        return None

    def is_empty(self):
        """Prüfen, ob die Warteschlange leer ist"""
        return len(self.items) == 0

    def size(self):
        """Gibt die Größe der Warteschlange zurück"""
        return len(self.items)

# Anwendungsbeispiel: Simulieren von Druckaufträgen
print("\n=== Warteschlangen- und Druckauftragssimulation ===)
printer_queue = Queue()

# Simuliere das Eintreffen von drei Druckaufträgen
tasks = ["Alices Lebenslauf.pdf", "Bobs Bericht.doc", "Charlies Diagramm.png"]
for task in tasks:
    printer_queue.enqueue(task)
    print(f"Auftrag '{task}' wurde zur Druckwarteschlange hinzugefügt.")

# Druckaufträge verarbeiten
print("\nDruckvorgang starten...)
while not printer_queue.is_empty():
    current_task = printer_queue.dequeue()
    print(f"Druckvorgang: {current_task}")
    # Druckzeit simulieren
print("Alle Druckaufträge wurden abgeschlossen.")

Ausgabe:

=== 队列与打印任务模拟 ===
任务 'Alice的简历.pdf' 已加入打印队列。
任务 'Bob的报告.doc' 已加入打印队列。
任务 'Charlie的图表.png' 已加入打印队列。

开始打印...
正在打印: Alice的简历.pdf
正在打印: Bob的报告.doc
正在打印: Charlie的图表.png
所有打印任务已完成。

Zusammenfassung und Vergleich

Wir haben vier grundlegende lineare Datenstrukturen kennengelernt. Die folgende Tabelle hilft dir, ihre Kernmerkmale schnell zu überprüfen und zu vergleichen:

Funktionen array Verkettete Liste Stapel Warteschlange
Speichermethode Zusammenhängender Speicher Verstreuter Speicher, über Zeiger verbunden Implementiert auf Basis von Arrays oder verketteten Listen Implementiert auf Basis von Arrays oder verketteten Listen
Zugriffsmethode Wahlfreier Zugriff (über Index) Sequenzieller Zugriff (muss durchlaufen werden) Beschränkt auf die Spitze des Stapels (LIFO) Beschränkt auf den Kopf der Warteschlange (FIFO)
Effizienz beim Einfügen/Löschen Schnell am Ende, langsam in der Mitte/am Kopf (erfordert Verschieben von Elementen) Schnell, wenn die Position bekannt ist (nur Zeiger müssen geändert werden) Operationen an der Stapelspitze, O(1) Anfügen am Ende, Entfernen am Kopf, O(1)
Size Fest (statisches Array) Dynamisch Dynamisch Dynamisch
Hauptanwendungen Schnelles Nachschlagen, feste Sammlung Häufiges Einfügen/Löschen, unbestimmte Größe Funktionsaufrufe, Backtracking, Klammerabgleich Aufgabenplanung, Pufferung, BFS

Wie soll man wählen?

  • erfordertschnellen wahlfreien Zugriffund wenn die Datenmenge bekannt ist, wähleArray。
  • erforderthäufiges Einfügen oder Löschen an beliebigen Positionenvon Elementen, und wenn die Datenmenge stark variiert, wähleverkettete Liste。
  • Müssen Sie"Undo"-Funktion implementieren oderRückwärtsverarbeitungWenn Sie in Reihenfolge vorgehen, ziehen SieStack in Betracht。
  • Müssen Sie"First come, first served"bei der Verarbeitung von Aufgaben in Reihenfolge einhalten, verwenden SieQueue。
Weitere Erweiterungen