Python3-Datenstrukturen

In diesem Kapitel kombinieren wir hauptsächlich die zuvor gelernten Kenntnisse, um Python-Datenstrukturen vorzustellen.

Listen

In Python sind Listen veränderlich, was das wichtigste Merkmal ist, das sie von Strings und Tupeln unterscheidet. In einem Satz: Listen können geändert werden, während Strings und Tupel nicht.

Im Folgenden werden die Methoden von Listen in Python aufgeführt:

Methode Beschreibung
list.append(x) Fügt ein Element am Ende der Liste hinzu, äquivalent zu a[len(a):] = [x].
list.extend(L) Erweitert die Liste, indem alle Elemente der angegebenen Liste hinzugefügt werden, äquivalent zu a[len(a):] = L.
list.insert(i, x) Fügt ein Element an einer angegebenen Position ein. Der erste Parameter ist der Index des Elements, vor dem eingefügt werden soll. Zum Beispiel fügt a.insert(0, x) am Anfang der gesamten Liste ein, und a.insert(len(a), x) ist äquivalent zu a.append(x).
list.remove(x) Entfernt das erste Element in der Liste, dessen Wert x ist. Wenn es kein solches Element gibt, wird ein Fehler zurückgegeben.
list.pop([i]) Entfernt das Element an der angegebenen Position aus der Liste und gibt es zurück. Wenn kein Index angegeben ist, gibt a.pop() das letzte Element zurück. Das Element wird sofort aus der Liste entfernt. (Die eckigen Klammern um i in der Methode zeigen an, dass dieser Parameter optional ist, und nicht, dass Sie ein Paar eckiger Klammern eingeben sollen. Diese Schreibweise werden Sie häufig im Python Library Reference Manual sehen.)
list.clear() Entfernt alle Elemente aus der Liste, äquivalent zu del a[:].
list.index(x) Gibt den Index des ersten Elements in der Liste zurück, dessen Wert x ist. Wenn kein passendes Element vorhanden ist, wird ein Fehler zurückgegeben.
list.count(x) Gibt die Anzahl zurück, wie oft x in der Liste vorkommt.
list.sort() Sortiert die Elemente in der Liste.
list.reverse() Kehrt die Reihenfolge der Elemente in der Liste um.
list.copy() Gibt eine flache Kopie der Liste zurück, äquivalent zu a[:].

Das folgende Beispiel veranschaulicht die meisten Methoden von Listen:

Beispiel

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print(a.count(333), a.count(66.25), a.count('x'))
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.25, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.entfernen(333)
>>> a
[66.25, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.25]
>>> a.sortieren()
>>> a
[-1, 1, 66.25, 333, 333, 1234.5]

Hinweis: Methoden wie insert, remove oder sort, die Listen verändern, geben keinen Wert zurück.

Listen als Stacks verwenden

In Python können Sie eine Liste verwenden, um Stack-Funktionalität zu implementieren. Ein Stack ist eine Last-In-First-Out-Datenstruktur (LIFO, Last-In-First-Out), das heißt, das zuletzt hinzugefügte Element wird zuerst entfernt. Listen bieten einige Methoden, die sie besonders für Stack-Operationen geeignet machen, insbesondereappend()undpop()Methoden.

Verwenden Sie die Methode append(), um ein Element oben auf den Stack zu legen, und die Methode pop() ohne Index, um ein Element von oben vom Stack zu entfernen.

Stack-Operationen

  • Push: Fügt ein Element oben auf den Stapel hinzu.
  • Pop: Entfernt das oberste Element des Stapels und gibt es zurück.
  • Peek/Top: Gibt das oberste Element des Stapels zurück, ohne es zu entfernen.
  • IsEmpty: Prüft, ob der Stapel leer ist.
  • Size: Ermittelt die Anzahl der Elemente im Stapel.

Das Folgende ist eine ausführliche Erklärung, wie diese Operationen mit Listen in Python implementiert werden:

1. Einen leeren Stapel erstellen

Beispiel

stack = []

2. Push-Operation

Verwenden Sie die append()-Methode, um ein Element oben auf den Stapel hinzuzufügen:

Beispiel

stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # Ausgabe: [1, 2, 3]

3. Pop-Operation

Verwenden Sie die pop()-Methode, um das oberste Element des Stacks zu entfernen und zurückzugeben:

Beispiel

top_element = stack.pop()
print(top_element)  # Ausgabe: 3
print(stack)        # Ausgabe: [1, 2]

4. Das oberste Element des Stacks anzeigen (Peek/Top)

Direkt auf das letzte Element der Liste zugreifen (ohne es zu entfernen):

Beispiel

top_element = stack[-1]
print(top_element)  # Ausgabe: 2

5. Prüfen, ob der Stack leer ist (IsEmpty)

Prüfen Sie, ob die Liste leer ist:

Beispiel

is_empty = len(stack) == 0
print(is_empty)  # Ausgabe: False

6. Die Größe des Stacks ermitteln (Size)

Verwenden Sie die Funktion len(), um die Anzahl der Elemente im Stack zu erhalten:

Beispiel

size = len(stack)
print(size)  # Ausgabe: 2

Beispiel

Das Folgende ist ein vollständiges Beispiel, das zeigt, wie die oben genannten Operationen verwendet werden, um einen einfachen Stack zu implementieren:

Beispiel

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("pop von leerem Stack")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("peek von leerem Stack")

    def is_empty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

# Verwendungsbeispiel
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Oberstes Element:", stack.peek())  # Ausgabe: Oberstes Element: 3
print("Stackgröße:", stack.size())    # Ausgabe: Stackgröße: 3

print("Entnommenes Element:", stack.pop())  # Ausgabe: Entnommenes Element: 3
print("Ist der Stack leer:", stack.is_empty())  # Ausgabe: Ist der Stack leer: False
print("Stack size:", stack.size())    # Ausgabe: Stack size: 2

Im obigen Code haben wir eine Stack-Klasse definiert, die eine Liste als zugrunde liegende Datenstruktur kapselt und die grundlegenden Operationen eines Stacks implementiert.

Die Ausgabe sieht wie folgt aus:

栈顶元素: 3
栈大小: 3
弹出元素: 3
栈是否为空: False
栈大小: 2

Verwendung von Listen als Warteschlangen

In Python kann eine Liste als Warteschlange verwendet werden, aber aufgrund der Eigenschaften von Listen ist die direkte Verwendung einer Liste zur Implementierung einer Warteschlange nicht die optimale Wahl.

Eine Warteschlange ist eine First-In-First-Out-Datenstruktur (FIFO, First-In-First-Out), was bedeutet, dass das zuerst hinzugefügte Element zuerst entfernt wird.

Wenn Sie eine Liste verwenden und häufig Elemente am Anfang der Liste einfügen oder löschen, wird die Leistung beeinträchtigt, da die Zeitkomplexität dieser Operationen O(n) beträgt. Um dieses Problem zu lösen, bietet Python collections.deque, eine doppelendige Warteschlange, die effizient Elemente an beiden Enden hinzufügen und entfernen kann.

Implementierung einer Warteschlange mit collections.deque

collections.deque ist Teil der Python-Standardbibliothek und eignet sich sehr gut für die Implementierung von Warteschlangen.

Das Folgende ist ein Beispiel für die Implementierung einer Warteschlange mit deque:

Beispiel

from collections import deque

# Eine leere Warteschlange erstellen
queue = deque()

# Elemente am Ende der Warteschlange hinzufügen
queue.append('a')
queue.append('b')
queue.append('c')

print("Warteschlangenstatus:", queue)  # Ausgabe: Warteschlangenstatus: deque(['a', 'b', 'c'])

# Ein Element vom Kopf der Warteschlange entfernen
first_element = queue.popleft()
print("Entferntes Element:", first_element)  # Ausgabe: Entferntes Element: a
print("Warteschlangenstatus:", queue)            # Ausgabe: Warteschlangenstatus: deque(['b', 'c'])

# Das Kopfelement anzeigen (ohne es zu entfernen)
front_element = queue[0]
print("Kopfelement:", front_element)    # Ausgabe: Kopfelement: b

# Prüfen, ob die Warteschlange leer ist
is_empty = len(queue) == 0
print("Ist die Warteschlange leer:", is_empty)     # Ausgabe: Ist die Warteschlange leer: False

# Größe der Warteschlange abrufen
size = len(queue)
print("Warteschlangengröße:", size)            # Ausgabe: Warteschlangengröße: 2
```

Implementieren einer Warteschlange mit Listen

Obwohl deque effizienter ist, kannst du, wenn du darauf bestehst, eine Liste zur Implementierung einer Warteschlange zu verwenden, dies trotzdem tun. Das folgende ist ein Beispiel dafür, wie man eine Liste zur Implementierung einer Warteschlange verwendet:

1. Eine Warteschlange erstellen

Beispiel

queue = []

2. Elemente am Ende der Warteschlange hinzufügen

Verwende die Methode append(), um Elemente am Ende der Warteschlange hinzuzufügen:

Beispiel

queue.append('a')
queue.append('b')
queue.append('c')
print("Warteschlangenstatus:", queue)  # Ausgabe: Warteschlangenstatus: ['a', 'b', 'c']

3. Elemente am Anfang der Warteschlange entfernen

Verwende die Methode pop(0), um Elemente am Anfang der Warteschlange zu entfernen:

Beispiel

first_element = queue.pop(0)
print("Entferntes Element:", first_element)  # Ausgabe: Entferntes Element: a
print("Warteschlangenstatus:", queue)            # Ausgabe: Warteschlangenstatus: ['b', 'c']

4. Vorderes Element der Warteschlange anzeigen (ohne es zu entfernen)

Direkt auf das erste Element der Liste zugreifen:

Beispiel

front_element = queue[0]
print("Front element:", front_element)    # Ausgabe: Front element: b

5. Prüfen, ob die Warteschlange leer ist

Prüfen Sie, ob die Liste leer ist:

Beispiel

is_empty = len(queue) == 0
print("Ist die Warteschlange leer:", is_empty)     # Ausgabe: Ist die Warteschlange leer: False

6. Größe der Warteschlange abrufen

Verwenden Sie die Funktion len(), um die Größe der Warteschlange zu ermitteln:

Beispiel

size = len(queue)
print("Warteschlangengröße:", size)            # Ausgabe: Warteschlangengröße: 2

Beispiel (Implementierung einer Warteschlange mit Listen)

Beispiel


class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("dequeue aus leerer Warteschlange")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("peek aus leerer Warteschlange")

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

# Verwendungsbeispiel
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')

print("Vorderes Element:", queue.peek())    # Ausgabe: Vorderes Element: a
print("Warteschlangengröße:", queue.size())    # Ausgabe: Warteschlangengröße: 3

print("Entferntes Element:", queue.dequeue())  # Ausgabe: Entferntes Element: a
print("Ist die Warteschlange leer:", queue.is_empty())  # Ausgabe: Ist die Warteschlange leer: False
print("Warteschlangengröße:", queue.size())    # Ausgabe: Warteschlangengröße: 2

Obwohl Sie eine Liste verwenden können, um eine Warteschlange zu implementieren, ist die Verwendung von collections.deque effizienter und prägnanter. Sie bietet eine Zeitkomplexität von O(1) für Hinzufügen- und Entfernen-Operationen, was sie sehr geeignet für eine Warteschlangen-Datenstruktur macht.

Listen-Comprehensions

Listen-Comprehensions bieten eine prägnante Möglichkeit, Listen aus Sequenzen zu erstellen. Normalerweise wendet eine Anwendung einige Operationen auf jedes Element einer Sequenz an, verwendet die Ergebnisse als Elemente einer neuen Liste oder erstellt Teilsequenzen basierend auf bestimmten Bedingungen.

Eine Listen-Comprehension besteht aus einem Ausdruck, gefolgt von einer for-Klausel, dann null oder mehr for- oder if-Klauseln. Das Ergebnis ist eine Liste, die aus dem Ausdruck im Kontext der folgenden for- und if-Klauseln generiert wird. Wenn der Ausdruck ein Tupel erzeugen soll, müssen Sie Klammern verwenden.

Hier multiplizieren wir jeden Wert in der Liste mit drei, um eine neue Liste zu erhalten:

>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]

Jetzt spielen wir mit ein paar Tricks:

>>> [[x, x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]

Hier rufen wir nacheinander für jedes Element der Sequenz eine Methode auf:

Beispiel

>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']

Wir können eine if-Klausel als Filter verwenden:

>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]

Im Folgenden werden einige Demonstrationen von Schleifen und anderen Techniken gezeigt:

>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

Listen-Comprehensions können komplexe Ausdrücke oder verschachtelte Funktionen verwenden:

>>> [str(round(355/113, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

Verschachtelte Listen-Comprehensions

Python-Listen können auch verschachtelt sein.

Das folgende Beispiel zeigt eine 3X4-Matrixliste:

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

Das folgende Beispiel wandelt die 3X4-Matrixliste in eine 4X3-Liste um:

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Das obige Beispiel kann auch mit der folgenden Methode implementiert werden:

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Eine andere Implementierungsmethode:

>>> transposed = []
>>> for i in range(4):
...     # Die folgenden 3 Zeilen implementieren die verschachtelte Listcomp
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Die del-Anweisung

Die del-Anweisung kann verwendet werden, um ein Element anhand des Index statt anhand des Werts aus einer Liste zu entfernen. Dies unterscheidet sich von der Verwendung von pop(), das einen Wert zurückgibt. Die del-Anweisung kann verwendet werden, um einen Slice aus einer Liste zu entfernen oder die gesamte Liste zu leeren (die Methode, die wir zuvor vorgestellt haben, besteht darin, dem Slice eine leere Liste zuzuweisen). Zum Beispiel:

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

Sie können del auch verwenden, um Variablen zu löschen:

>>> del a

Tupel und Sequenzen

Ein Tupel besteht aus einer Anzahl von Werten, die durch Kommas getrennt sind, zum Beispiel:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tupel können verschachtelt sein:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

Wie Sie sehen, werden Tupel in der Ausgabe immer in Klammern eingeschlossen, damit verschachtelte Strukturen korrekt dargestellt werden. Sie können mit oder ohne Klammern eingegeben werden, obwohl Klammern normalerweise notwendig sind, wenn das Tupel Teil eines größeren Ausdrucks ist.

Mengen

Eine Menge ist eine ungeordnete Sammlung eindeutiger Elemente. Zu den grundlegenden Funktionen gehören Zugehörigkeitstests und das Entfernen doppelter Elemente.

Mengen können mit geschweiften Klammern ({}) erstellt werden. Hinweis: Um eine leere Menge zu erstellen, müssen Sie set() anstelle von {} verwenden; Letzteres erzeugt ein leeres Wörterbuch, eine Datenstruktur, die wir im nächsten Abschnitt vorstellen werden.

Das Folgende ist eine einfache Demonstration:

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # Duplikate entfernen
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # Zugehörigkeit prüfen
True
>>> 'crabgrass' in basket
False

>>> # Das Folgende demonstriert Operationen an zwei Mengen
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # Eindeutige Buchstaben in a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # Buchstaben in a, aber nicht in b
{'r', 'd', 'b'}
>>> a | b                              # Buchstaben in a oder b
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # Buchstaben sowohl in a als auch in b
{'a', 'c'}
>>> a ^ b                              # Buchstaben in a oder b, aber nicht in beiden
{'r', 'd', 'b', 'm', 'z', 'l'}

Mengen unterstützen auch Comprehensions:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

Wörterbücher

Ein weiterer sehr nützlicher integrierter Datentyp in Python ist das Dictionary.

Sequenzen werden durch aufeinanderfolgende ganze Zahlen indiziert; im Gegensatz dazu werden Dictionaries durch Schlüssel indiziert, die von beliebigem unveränderlichem Typ sein können, normalerweise Zeichenketten oder Zahlen.

Der beste Weg, ein Dictionary zu verstehen, ist, es als eine ungeordnete Sammlung von Schlüssel=>Wert-Paaren zu betrachten. Innerhalb desselben Dictionaries müssen die Schlüssel voneinander verschieden sein.

Ein Paar geschweifter Klammern erzeugt ein leeres Dictionary: {}.

Dies ist ein einfaches Beispiel für die Verwendung eines Dictionarys:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> list(tel.keys())
['irv', 'guido', 'jack']
>>> sorted(tel.keys())
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

Der dict()-Konstruktor erstellt Dictionaries direkt aus einer Liste von Schlüssel-Wert-Paaren. Wenn ein festes Muster vorliegt, können Listen-Comprehensions bestimmte Schlüssel-Wert-Paare angeben:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}

Darüber hinaus können Dictionary-Comprehensions verwendet werden, um Dictionaries mit beliebigen Schlüssel- und Wertausdrücken zu erstellen:

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

Wenn die Schlüssel einfache Zeichenketten sind, ist es manchmal bequemer, Schlüssel-Wert-Paare mithilfe von Schlüsselwortargumenten anzugeben:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'jack': 4098, 'guido': 4127}

Techniken zum Durchlaufen

Beim Durchlaufen eines Dictionaries können die Schlüssel und die zugehörigen Werte gleichzeitig mit der Methode items() abgerufen werden:

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

Beim Durchlaufen einer Sequenz können die Indexposition und der entsprechende Wert gleichzeitig mit der Funktion enumerate() ermittelt werden:

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

Um zwei oder mehr Sequenzen gleichzeitig zu durchlaufen, verwenden Sie zip(), um sie zu kombinieren:

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('Was ist dein {0}? Es ist {1}.'.format(q, a))
...
Was ist dein Name? Es ist lancelot.
Was ist deine Aufgabe? Es ist der heilige Gral.
Was ist deine Lieblingsfarbe? Es ist blau.

Um eine Sequenz in umgekehrter Reihenfolge zu durchlaufen, geben Sie zuerst die Sequenz an und rufen Sie dann die Funktion reversed() auf:

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

Um eine Sequenz der Reihe nach zu durchlaufen, verwenden Sie die Funktion sorted(), die eine sortierte Sequenz zurückgibt, ohne das Original zu verändern:

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
Apfel
Banane
Orange
pear

Referenzdokumentation

Andere Erweiterungen