Datenstrukturen Flashcards
Queue (Schlange)
Eine Queue ist eine lineare Datenstruktur, die das Prinzip First-In-First-Out (FiFo) verwendet, bei dem das zuerst eingefügte Element auch zuerst entfernt wird.
- FiFo-Prinzip: Erstes rein, erstes raus.
- Operationen an beiden Enden:
- Put: Element am Ende hinzufügen.
- Get: Element vom Anfang entfernen.
- Anwendungen: Schieberegister, Warteschlangen in Prozessen und Systemen.
Hash
Ein Hash ist eine Datenstruktur, die eine Schlüssel-Wert-Paar-Zuordnung verwendet, um schnellen Zugriff auf Daten zu ermöglichen.
- Schneller Zugriff: Basierend auf berechneten Schlüsselwerten.
- Hash-Funktion: Wandelt Schlüssel in einen Index um.
- Kollision: Wenn zwei Schlüssel denselben Index erzeugen.
- Anwendungen: Datenbanken, Caching, Symboltabellen.
- Effiziente Speicherung und Abruf großer Datenmengen.
Hash-Funktion
Eine Hash-Funktion wandelt Eingabedaten (oftmals groß und komplex) in einen einzigartigen und festen Index oder Hash-Wert um, der die Speicherung und den Zugriff erleichtert.
- Eindeutigkeit: Strebt an, unterschiedliche Eingaben in einzigartige Hash-Werte umzuwandeln.
- Komplexe Schlüssel: Oft als Polynom in einem Stellenwertsystem (Basis b) dargestellt.
- Mathematische Auswertung: Schlüssel k als k = \sum_{i=0}^{n} k_i b^i .
- Hash-Funktion Beispiel: Verwenden von modulo-Operation, ( j = h(k) = k mod M ).
- Anwendungen: Effektive Datenorganisation und -suche.
Horner-Schema
Das Horner-Schema ist ein effizientes Verfahren zur Berechnung von Polynomen, bei dem die Berechnung durch schrittweises Ausklammern vereinfacht wird.
- Effiziente Polynomberechnung: Reduziert die Anzahl der Multiplikationen.
- Verschachteltes Ausklammern: Berechnet Polynome der Form:
- Numerische Stabilität: Vorteilhaft bei der Berechnung mit großen oder kleinen Zahlen.
- Anwendungen: Computerarithmetik und Algorithmusoptimierung.
- Einfachheit: Klarer und weniger fehleranfällig in der Implementierung.
Bäume
Heap
Ein Heap (Halde) ist eine Baumstruktur, die als effiziente Implementierung einer Prioritätswarteschlange dient.
Grundstruktur:
- Vollständiger Binärbaum (alle Ebenen außer evtl. der letzten sind vollständig gefüllt)
- Kann effizient als Array implementiert werden: Element an Position i hat Kinder an 2i+1 und 2i+2, Elternteil an ⌊(i-1)/2⌋
- Zwei Hauptvarianten: Min-Heap (kleinster Wert an der Wurzel) und Max-Heap (größter Wert an der Wurzel)
Heap-Eigenschaft:
- Bei Max-Heap: Jeder Knoten ist größer oder gleich seinen Kindern
- Bei Min-Heap: Jeder Knoten ist kleiner oder gleich seinen Kindern
- Folge: Die Wurzel enthält immer das Maximum bzw. Minimum
Operationen:
- Einfügen (insert): O(log n) - Füge am Ende ein, “sift-up” bis Heap-Eigenschaft erfüllt
- Entfernen des Wurzelelements (extract-max/min): O(log n) - Ersetze Wurzel durch letztes Element, “sift-down” bis Heap-Eigenschaft erfüllt
- Erstellen (heapify): O(n) - Umwandlung eines beliebigen Arrays in einen Heap
Anwendungen:
- Prioritätswarteschlangen
- Heapsort (Sortieralgorithmus mit O(n log n) Zeitkomplexität)
- Dijkstra-Algorithmus für kürzeste Pfade
- Huffman-Kodierung
