SERIOUS-PLAYGROUND.DE/blog/

Elementare Datenstrukturen:

Lineare Listen:

(Implementierung durch Arrays)

Operationen: insert/remove (Elemente einfügen/entfernen), movetofront/next (Bewegung in der Liste), Statustest (ist die Liste leer, ist das Ende der Liste erreicht?), Werte lesen/schreiben, Element suchen, Konkatenation, entferne alle Elemente links/rechts vom aktuellen Element

Modifikationen: modifiziere insert so, dass Elemente sortiert eingefügt werden können, modifiziere search so, dass eine erfolglose Suche schnell abgebrochen werden kann (z.B. mit binärer Suche)

Kosten: alle Funktionen können in konstanter Zeit durchgeführt werden. Ausnahme: search()

Beispiel: Addition dünnbesetzter Matrizen

Dequeues, Queues, Stacks:

Stack (Stapelspeicher):

Operationen: pop/push (entferne jüngsten Schlüssel/füge einen Schlüssel ein)

Kosten: konstant

Queue (Warteschlange):

Operationen: enqueue/dequeue (füge einen Schlüssel ein, entfernen ältesten Schlüssel)

Kosten: konstant

Dequeue:

Verallgemeinerung von Stacks und Queues

Operationen: insertleft/insertright, removeleft, removeright

Kosten: konstant

Bäume:

Implementierung als:

• Vater-Array (optimal für Operationenmenge {Vater, Tiefe} wegen Speicherplatzeffizienz: O(n)): speichere für jeden Knoten den Namen seines Vaters
• Adjazenzliste:  speichere für jeden Knoten die Liste seiner Kinder
• Binärbaum (1. Wahl für binäre Bäume): jeder Knoten besitzt je einen Zeiger auf die Struktur seiner Kinder, der Zeiger wurzel zeigt stets auf die Struktur der Wurzel des Baums
• Kind-Geschwister (1. Wahl für allgemeine Bäume): jeder Knoten besitzt einen Zeiger auf das erste (linkeste) Kind und einen Zeiger auf den nächsten Geschwister-Knoten

Suche in Bäumen:

Postorder (t1, …, tn, Wurzel), Präoder (Wurzel, t1, …, tn), Inorder (t1, Wurzel, t2, …, tn)

Graphen:

Implementierung als Adjazenzliste

Anwendungen: Topologisches Sortieren, Eulerkreis

Tiefensuche, Breitensuche

Prioritätswarteschlangen:

Verallgemeinerung des Queues: jedes Element besitzt eine Priorität, das Element mit der höchsten Priorität kann entfernt werden

Implementierung durch Heap

Operationen: insert(priority), delet_max, change_priority(wo, neue_priorität), remove(wo)

Datenstrukturen und Algorithmen:

Dijkstras SSSP Algorithmus (Visualisierung), Prims Algorithmus für MSP, Kruskals Algorithmus für MSP

Dieser Beitrag wurde vor am Mittwoch, 10. März 2010 um 10:35 Uhr veröffentlicht und unter algorithmen, datenstrukturen, theoretische informatik gespeichert. Sie können Kommentare zu diesem Eintrag über den RSS-2.0-Feed verfolgen. Sie können einen Kommentar hinterlassen oder einen Trackback von Ihrer Website hierher setzen.