Wesentliche Begriffe und Definitionen

3.1 Operationen mit Daten: Einfügen, Löschen, Suchen

Einfügen (Insert):

Operation zum Hinzufügen eines neuen Elements in eine Datenstruktur. Das Einfügen kann am Anfang, am Ende oder an beliebiger Stelle der Datenstruktur erfolgen.

Löschen (Delete):

Operation zum Entfernen eines Elements aus einer Datenstruktur. Das Löschen kann anhand des Elementwertes, des Indexes oder der Position des Elements in der Datenstruktur erfolgen.

Suchen (Search):

Operation zum Auffinden eines Elements in einer Datenstruktur. Die Suche kann anhand des Wertes oder anderer Kriterien erfolgen.

Beispiele für Operationen:

• Arrays: Einfügen und Löschen erfordern das Verschieben von Elementen, was zeitaufwändig sein kann — O(n).
• Verkettete Listen: Einfügen und Löschen können in O(1) erfolgen, wenn die Position des Knotens bekannt ist.
• Hash-Tabellen: Suchen, Einfügen und Löschen werden normalerweise im Durchschnitt in O(1) ausgeführt.
• Bäume: Such-, Einfüge- und Löschoperationen können in ausgeglichenen Bäumen in O(log n) ausgeführt werden.

3.2 Grundlegende Konzepte: Array, Liste, Stack, Queue

Array

Array — eine Sequenz von Elementen eines Typs, auf die über einen Index zugegriffen werden kann.

Komplexität der Operationen: Zugriff nach Index — O(1), Einfügen und Löschen — O(n).

Beispiel: Erstellen eines Arrays, Ändern eines Elements und Ausgabe des Ergebnisses

# Erstellen eines Arrays von Zahlen
arr = [1, 2, 3, 4, 5]

# Ändern des Elements mit Index 2 (drittes Element, da die Indizierung bei 0 beginnt)
arr[2] = 10

# Ausgabe des geänderten Arrays
print(arr)  # Ausgabe: [1, 2, 10, 4, 5]

# Hinzufügen eines neuen Elements am Ende des Arrays
arr.append(6)
print(arr)  # Ausgabe: [1, 2, 10, 4, 5, 6]

# Löschen eines Elements nach Index
del arr[1]
print(arr)  # Ausgabe: [1, 10, 4, 5, 6]

Liste

Liste — eine Sammlung von Elementen, bei der jedes Element auf das nächste (singly linked list) oder auf das nächste und vorherige Element (doubly linked list) verweist.

Komplexität der Operationen: Einfügen und Löschen — O(1) bei bekannter Position, Suchen — O(n).

Beispiel: Erstellen einer einfachen einfach verketteten Liste und deren Durchlauf

# Definition der Struktur eines Listenknotens
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Erstellen einer einfach verketteten Liste
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")

# Verknüpfen der Knoten
node1.next = node2
node2.next = node3

# Setzen des Listenkopfes
list_head = node1

# Durchlaufen der Liste und Ausgabe der Daten
current = list_head
while current:
    print(current.data)
    current = current.next

# Ausgabe:
# 101
# 102
# 103

Stack

Stack — eine Sammlung von Elementen mit dem Prinzip LIFO (Last In, First Out): das letzte Element, das hinzugefügt wurde, wird zuerst entfernt.

Komplexität der Operationen: Einfügen (push) und Löschen (pop) — O(1).

Beispiel: Implementierung und Nutzung eines Stacks zur Überprüfung der Ausgewogenheit von Klammern

def is_balanced(expression):
    stack = []
    opening = "({["
    closing = ")}]"
    pairs = {")": "(", "}": "{", "]": "["}
    
    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or stack.pop() != pairs[char]:
                return False
    
    return len(stack) == 0

# Überprüfen verschiedener Ausdrücke
print(is_balanced("({[]})"))  # Ausgabe: True
print(is_balanced("([)]"))    # Ausgabe: False
print(is_balanced("(("))      # Ausgabe: False

Queue

Queue — eine Sammlung von Elementen mit dem Prinzip FIFO (First In, First Out): das erste Element, das hinzugefügt wurde, wird zuerst entfernt.

Komplexität der Operationen: Einfügen (enqueue) und Löschen (dequeue) — O(1).

Beispiel: Implementierung und Nutzung einer Queue zur Simulation der Aufgabenbearbeitung

from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)
        print(f"Aufgabe '{task}' zur Queue hinzugefügt")

    def process_task(self):
        if self.queue:
            task = self.queue.popleft()
            print(f"Bearbeitung der Aufgabe: '{task}'")
        else:
            print("Queue ist leer")

    def display_queue(self):
        print("Aktuelle Aufgaben-Queue:", list(self.queue))

# Erstellen und Nutzung der Aufgaben-Queue
task_queue = TaskQueue()

task_queue.add_task("Email senden")
task_queue.add_task("Datenbank aktualisieren")
task_queue.add_task("Bericht erstellen")

task_queue.display_queue()

task_queue.process_task()
task_queue.process_task()

task_queue.display_queue()

# Ausgabe:
# Aufgabe 'Email senden' zur Queue hinzugefügt
# Aufgabe 'Datenbank aktualisieren' zur Queue hinzugefügt
# Aufgabe 'Bericht erstellen' zur Queue hinzugefügt
# Aktuelle Aufgaben-Queue: ['Email senden', 'Datenbank aktualisieren', 'Bericht erstellen']
# Bearbeitung der Aufgabe: 'Email senden'
# Bearbeitung der Aufgabe: 'Datenbank aktualisieren'
# Aktuelle Aufgaben-Queue: ['Bericht erstellen']

3.3 Unterschiede zwischen verschiedenen Datentypen

Die wichtigsten Unterschiede zwischen verschiedenen Datentypen:

Arrays:

• Zugriff: Schneller Zugriff nach Index — O(1).
• Größenänderung: Feste Größe, Vergrößerung erfordert Kopieren aller Elemente — O(n).
• Geeignet für: Zufälligen Zugriff auf Elemente, wenn die Datenmenge im Voraus bekannt ist.

Verkettete Listen:

• Zugriff: Langsamer Zugriff nach Index — O(n).
• Größenänderung: Einfach anpassbare Größe, Einfügen und Löschen erfolgt in O(1).
• Geeignet für: Häufiges Hinzufügen und Entfernen von Elementen.

Stack:

• Arbeitsprinzip: LIFO.
• Operationen: Einfügen und Löschen nur an einem Ende — O(1).
• Geeignet für: Umgekehrte Reihenfolge der Aufgabenbearbeitung, Funktionsaufrufsteuerung.

Queue:

• Arbeitsprinzip: FIFO.
• Operationen: Einfügen und Löschen an verschiedenen Enden — O(1).
• Geeignet für: Aufgabenverwaltung in der Reihenfolge ihres Eingangs.

3.4 Anwendung verschiedener Datenstrukturen

Beispiele für die Anwendung verschiedener Datenstrukturen in der Praxis:

Arrays

Speicherung von Daten fester Länge, wie Wochentage oder Monate im Jahr.

Beispiel: Verwendung eines Arrays zur Arbeit mit Wochentagen

# Erstellen eines Arrays mit Wochentagen
days = ["Montag", "Dienstag", "Mittwoch", "Donnerstag", "Freitag", "Samstag", "Sonntag"]

# Wochentag nach Index abrufen (z.B. dritter Tag)
print(days[2])  # Ausgabe: Mittwoch

# Name des Tages ändern
days[0] = "Montag (Wochenbeginn)"
print(days[0])  # Ausgabe: Montag (Wochenbeginn)

# Alle Wochentage durchlaufen
for day in days:
    print(day)

# Ausgabe:
# Montag (Wochenbeginn)
# Dienstag
# Mittwoch
# Donnerstag
# Freitag
# Samstag
# Sonntag

Verkettete Listen

Implementierung dynamischer Sammlungen, bei denen Elemente hinzugefügt und aus der Mitte der Sammlung entfernt werden können.

Beispiel: Implementierung und Nutzung einer verketteten Liste zur Verwaltung einer Aufgabenliste

class TodoItem:
    def __init__(self, task):
        self.task = task
        self.next = None

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

    def add_task(self, task):
        new_item = TodoItem(task)
        if not self.head:
            self.head = new_item
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_item

    def display_tasks(self):
        current = self.head
        if not current:
            print("Aufgabenliste ist leer")
        else:
            while current:
                print(f"- {current.task}")
                current = current.next

# Erstellen und Nutzung der Aufgabenliste
todo = TodoList()
todo.add_task("Einkaufen")
todo.add_task("Mama anrufen")
todo.add_task("Präsentation vorbereiten")

print("Meine Aufgabenliste:")
todo.display_tasks()

# Ausgabe:
# Meine Aufgabenliste:
# - Einkaufen
# - Mama anrufen
# - Präsentation vorbereiten

Stack

Umgekehrte Reihenfolge der Aufgabenbearbeitung, z.B. Bearbeitung von Funktionsaufrufen in der Rekursion oder Rückgängig machen von Operationen (undo).

Beispiel: Verwendung eines Stacks, um eine Zeichenfolge umzukehren

def reverse_string(s):
    stack = []
    # Jeden Buchstaben der Zeichenfolge in den Stack legen
    for char in s:
        stack.append(char)
    
    reversed_s = ''
    # Buchstaben aus dem Stack herausholen, um die umgekehrte Zeichenfolge zu bilden
    while stack:
        reversed_s += stack.pop()
    
    return reversed_s

# Beispielanwendung
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Originale Zeichenfolge: {original}")
print(f"Umgekehrte Zeichenfolge: {reversed_str}")

# Ausgabe:
# Originale Zeichenfolge: Hello, World!
# Umgekehrte Zeichenfolge: !dlroW ,olleH

Queue

Verwaltung von Aufgaben in der Reihenfolge ihres Eingangs, z.B. Druckaufträge oder Kundenservice-Warteschlangen.

Beispiel: Simulation einer Druckerqueue

from collections import deque

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_document(self, document):
        self.queue.append(document)
        print(f"Dokument '{document}' zur Druckerqueue hinzugefügt")

    def print_document(self):
        if self.queue:
            document = self.queue.popleft()
            print(f"Drucken des Dokuments: '{document}'")
        else:
            print("Druckerqueue ist leer")

    def display_queue(self):
        print("Aktuelle Druckerqueue:", list(self.queue))

# Erstellen und Nutzung der Druckerqueue
printer = PrinterQueue()
printer.add_document("Bericht")
printer.add_document("Präsentation")
printer.add_document("Vertrag")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()

# Ausgabe:
# Dokument 'Bericht' zur Druckerqueue hinzugefügt
# Dokument 'Präsentation' zur Druckerqueue hinzugefügt
# Dokument 'Vertrag' zur Druckerqueue hinzugefügt
# Aktuelle Druckerqueue: ['Bericht', 'Präsentation', 'Vertrag']
# Drucken des Dokuments: 'Bericht'
# Drucken des Dokuments: 'Präsentation'
# Aktuelle Druckerqueue: ['Vertrag']

In diesem Beispiel haben wir eine einfache Simulation einer Druckerwarteschlange erstellt. Dokumente werden am Ende der Warteschlange hinzugefügt und in der Reihenfolge gedruckt, in der sie eingegangen sind, was das FIFO-Prinzip (First In, First Out) demonstriert.