Erweiterte Datenstrukturen wie Stacks, Queues, verlinkte Listen, Bäume und Graphen in Python

Python bietet eine Vielzahl von integrierten und erweiterten Datenstrukturen, die es ermöglichen, komplexe Daten effizient zu speichern und zu verarbeiten. In diesem Artikel werden wir die erweiterten Datenstrukturen und ihre Implementierungen in Python detailliert erläutern, einschließlich der Verwendung des collections-Moduls, Stacks und Queues, verlinkten Listen sowie Bäumen und Graphen.

1. Collections-Modul

Das collections-Modul in Python bietet mehrere nützliche Datenstrukturen, die über die Standard-Datenstrukturen hinausgehen. Dazu gehören namedtuple, deque, Counter, OrderedDict, defaultdict und ChainMap.

Beispiel für Counter:

from collections import Counter

# Zählen der Elemente in einer Liste
liste = ['Apfel', 'Banane', 'Apfel', 'Orange', 'Banane', 'Apfel']
zaehler = Counter(liste)

print(zaehler)

# Ausgabe:
# Counter({'Apfel': 3, 'Banane': 2, 'Orange': 1})

Beispiel für defaultdict:

from collections import defaultdict

# Erstellen eines defaultdicts mit Listen als Standardwert
standard_dict = defaultdict(list)

standard_dict['a'].append(1)
standard_dict['a'].append(2)
standard_dict['b'].append(3)

print(standard_dict)


# Ausgabe:
# defaultdict(<class 'list'>, {'a': [1, 2], 'b': [3]})

2. Stacks und Queues

Stacks und Queues sind grundlegende Datenstrukturen, die oft in Algorithmen und Anwendungen verwendet werden.

2.1 Stack (LIFO - Last In, First Out):

Ein Stack kann einfach mit einer Liste in Python implementiert werden, indem append() zum Hinzufügen und pop() zum Entfernen von Elementen verwendet wird.

Beispiel:

stack = []

# Hinzufügen von Elementen zum Stack
stack.append(1)
stack.append(2)
stack.append(3)

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

# Entfernen von Elementen vom Stack
print(stack.pop())  # Ausgabe: 3
print(stack.pop())  # Ausgabe: 2
print(stack.pop())  # Ausgabe: 1

2.2 Queue (FIFO - First In, First Out):

Eine Queue kann mit collections.deque implementiert werden, das effiziente O(1) Operationen für das Hinzufügen und Entfernen von Elementen an beiden Enden bietet.

Beispiel:

from collections import deque

queue = deque()

# Hinzufügen von Elementen zur Queue
queue.append('a')
queue.append('b')
queue.append('c')

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

# Entfernen von Elementen aus der Queue
print(queue.popleft())  # Ausgabe: 'a'
print(queue.popleft())  # Ausgabe: 'b'
print(queue.popleft())  # Ausgabe: 'c'

3. Verlinkte Listen

Verlinkte Listen bestehen aus Knoten, die jeweils ein Element und einen Verweis auf den nächsten Knoten enthalten. Verlinkte Listen sind flexibler als Arrays, aber das Durchlaufen ist langsamer.

Beispiel einer einfach verlinkten Liste:

class Node:
    def __init__(self, daten):
        self.daten = daten
        self.next = None

class VerlinkteListe:
    def __init__(self):
        self.head = None

    def einfuegen(self, daten):
        neuer_knoten = Node(daten)
        neuer_knoten.next = self.head
        self.head = neuer_knoten

    def anzeigen(self):
        aktuelle = self.head
        while aktuelle:
            print(aktuelle.daten, end=' -> ')
            aktuelle = aktuelle.next
        print(None)

# Verwendung der verlinkten Liste
liste = VerlinkteListe()
liste.einfuegen(3)
liste.einfuegen(2)
liste.einfuegen(1)

liste.anzeigen()  # Ausgabe: 1 -> 2 -> 3 -> None

4. Bäume und Graphen

Bäume und Graphen sind erweiterte Datenstrukturen, die in vielen Algorithmen und Anwendungen verwendet werden. Ein Baum besteht aus Knoten mit Kindknoten, während ein Graph aus Knoten und Kanten besteht, die die Knoten verbinden.

Beispiel eines binären Suchbaums:

class BaumKnoten:
    def __init__(self, daten):
        self.daten = daten
        self.links = None
        self.rechts = None

def einfuegen(root, daten):
    if root is None:
        return BaumKnoten(daten)
    else:
        if daten < root.daten:
            root.links = einfuegen(root.links, daten)
        else:
            root.rechts = einfuegen(root.rechts, daten)
    return root

def inorder(root):
    if root:
        inorder(root.links)
        print(root.daten, end=' ')
        inorder(root.rechts)

# Verwendung des binären Suchbaums
baum = BaumKnoten(10)
einfuegen(baum, 5)
einfuegen(baum, 15)
einfuegen(baum, 2)
einfuegen(baum, 7)
einfuegen(baum, 12)
einfuegen(baum, 20)

inorder(baum)  # Ausgabe: 2 5 7 10 12 15 20

Beispiel eines ungerichteten Graphen:

class Graph:
    def __init__(self):
        self.adjazenz_liste = {}

    def hinzufuegen_knoten(self, knoten):
        if knoten not in self.adjazenz_liste:
            self.adjazenz_liste[knoten] = []

    def hinzufuegen_kante(self, knoten1, knoten2):
        if knoten1 in self.adjazenz_liste and knoten2 in self.adjazenz_liste:
            self.adjazenz_liste[knoten1].append(knoten2)
            self.adjazenz_liste[knoten2].append(knoten1)

    def anzeigen(self):
        for knoten in self.adjazenz_liste:
            print(knoten, '->', ' -> '.join([str(n) for n in self.adjazenz_liste[knoten]]))

# Verwendung des Graphen
graph = Graph()
graph.hinzufuegen_knoten(1)
graph.hinzufuegen_knoten(2)
graph.hinzufuegen_knoten(3)
graph.hinzufuegen_knoten(4)

graph.hinzufuegen_kante(1, 2)
graph.hinzufuegen_kante(1, 3)
graph.hinzufuegen_kante(2, 4)

graph.anzeigen()

Ausgabe:

1 -> 2 -> 3
2 -> 1 -> 4
3 -> 1
4 -> 2

Zusammenfassung

Erweiterte Datenstrukturen wie Stacks, Queues, verlinkte Listen, Bäume und Graphen sind in Python unerlässlich, um komplexe Daten effizient zu speichern und zu verarbeiten. Das collections-Modul bietet zusätzliche Datenstrukturen wie Counter und defaultdict, die den Umgang mit Daten erleichtern. Durch das Verständnis und die Anwendung dieser Datenstrukturen können Sie die Effizienz und Lesbarkeit Ihres Codes erheblich verbessern.