Dynamische Datenstrukturen

Beschreibung / Inhalt
Das vorliegende Dokument beschäftigt sich mit dynamischen Datenstrukturen. Einen wichtigen Teil nehmen dabei Listen ein. Es werden verschiedene Arten von Listen beschrieben, wie einfach verkettete, doppelt verkettete und zyklisch verkettete Listen, sowie ihre Anwendungen wie zum Beispiel der Stack oder die Schlange. Auch der Begriff Baum wird erläutert und der Binärbaum, der AVL-Baum, der M-Wege-Suchbaum und der B(ayer)-Baum werden beschrieben. Es wird erklärt, dass jeder Baum aus Knoten besteht und dass jeder Knoten maximal zwei Nachfolger hat und jeweils einen Vorgänger, außer die Wurzel, welche keinen Vorgänger hat. Die Kanten führen entweder zu anderen Knoten oder zu NULL und die Endknoten oder Blätter haben keine Nachfolger. Die Tiefe des linken Teilbaumes sollte sich beim AVL-Baum immer nur um maximal eins von der des rechten Teilbaumes unterscheiden, weshalb für jeden Knoten die Balance mitgespeichert werden muss. Auch beim B-Baum müssen bestimmte Kriterien erfüllt werden, wie dass jeder Knoten maximal (2*k)-1 Info-Komponenten hat und -(2*k)+1 Nachfolger. Blätter hingegen haben immer das selbe Niveau. Ziel dieser Datenstrukturen ist es, den Aufwand der Suche, des Einfügens und Löschens von Daten zu minimieren.
Direkt das Referat aufrufen

Auszug aus Referat
Dynamische Datenstrukturen (Florian Schimpf) 1.) Listen Allgemeines Eine verkettete Liste ist eine Menge von Elementen, die wie in einem Feld sequentiell organisiert sind. Bei Verwendung von Listen ist genau zu überlegen, welche Art man verwendet. Wenn nicht unbedingt notwendig, dann sollte man auf die doppelt bzw. zyklisch verketteten Listen verzichten, da diese mit mehr Aufwand verbunden sind. es muß keine maximale Größe angegeben werden (anders als beim Array) hohe Flexibilität, da Elemente recht leicht umgeordnet werden können relativ einfache Operationen (Einfügen, Löschen). Bei Arrays müßte das ganze Feld verschoben werden. Verschiedene Arten von Listen einfach verkettete Listen Jedes Element der einfach verketteten Liste besteht aus einem Datenteil undaus einem Zeiger auf das nächste Element. Deshalb kennt jedes Element nur seinenNachfolger. Es wird ein Zeiger (panker) auf das erste Element der Liste gespeichert, umdie einfach verkettete Liste durchlaufen zu können. Jenes Element das (noch) keinenNachfolger hat, hat als Wert im next-Zeiger NULL. ----- -- ----- -- ----- -- panker -- 1 ----- 2 ----- 3 ----- NULL ----- -- ----- -- ----- -- Anwendung der einfach verketteten Listen z. B. Stack (LIFO)Ein Beispiel in C : class STACK struct ELEMENT ELEMENT next; int dat; anf, hilf; public: STACK () anf new ELEMENT; anf- next NULL; STACK () delete(anf); void push(int i) hilf anf; anf new ELEMENT; anf- next hilf; anf- dat i; int pop () int d; hilf anf; if(anf- next NULL) anf ...
Direkt das Referat aufrufen