|
Definition: Menge von sequentiell organisierten Elementen
VT: variable Größe
hohe Flexibilität
Einfügen u. Löschen sehr einfach
NT: nur sequentielle Zugriffe möglich
Verschiedene Arten von Listen
einfach verkettet
Die einzelnen Elemente nur in eine Richtung verkettet - jedes Element kennt seinen Nachfolger, aber nicht seinen Vorgänger.
doppelt verkettet
Die einzelnen Elemente sind in beide Richtungen verkettet - jedes Element kennt seinen Nachfolger und seinen Vorgänger.
zyklisch verkettet
Wie doppelt verkettete Liste, nur kennt das erste Element das letzte als seinen Vorgänger und das letzte Element das erste als seinen Nachfolger.
Bäume
. Ein Baum besteht aus Knoten und Kanten
. Jeder Knoten stellt einen Datensatz dar
. Von jedem Knoten gehen eine oder mehrere Kanten aus, die entweder auf andere Knoten, oder auf NULL zeigen
. Es gibt genau einen Knoten ohne Vorgänger, dieser heißt Wurzel
. Die Anzahl der Knoten zwischen einem Knoten und der Wurzel nennt man Niveau des Knotens
. Das größte vorkommende Niveau in einem Baum nennt man die Tiefe des Baumes
Verschiedene Arten von Bäumen
Binärbaum
Jeder Knoten hat maximal 2 Nachfolger
2 Arten:
. geordnete (sortierte) Binärbaume: Die Daten sind nach einem Schlüsselbegriff sortiert. Für jeden Knoten gilt, daß jeder Schlüssel in seinem linken Teilbaum kleiner ist als sein eigener und alle Schlüssel im rechten Teilbaum größer sind als sein eigener Schlüssel.
. voller Binärbaum: Jede ebene ist völlig mit inneren Knoten ausgefüllt.
VT: schnelles Suchen
für rekursive Verarbeitung geeignet
Einfügen und löschen relativ einfach
NT: Wenn oft eingefügt und gelöscht wird besteht Gefahr des degenerierens zu einer Liste
Adelson-Velski-Landis - Baum
Für jeden Knoten gilt: Die Tiefe des linken Teilbaumes unterscheidet sich von der Tiefe des rechten Teilbaumes maximal um 1.
Balance = Tiefe des rechten Teilbaumes - Tiefe des linken Teilbaumes (zuläßige Werte: -1,0,1)
VT: geringerer Suchaufwand, da dieser Baum nicht degenerieren kann
NT: für jeden Knoten Balance mitspeichern
Nach jeder Einfüge- u. Löschoperation muß Balance wieder stimmen, dies geschieht mit Hilfe von Rechts-, Links- od.
Rechts-Links-Rotation.
Bayer-Baum
Ein spezieller M-Wege-Suchbaum
. Jeder Knoten hat maximal m Nachfolger und maximal m-1 Datenelemente
. Die Daten im Knoten sind aufsteigend sortiert
. Jedes Element kann einen linken und einen rechten Nachfolger haben, der rechte Nachfolger eines Elements entspricht dem linken Nachfolger des nächsten Datenelements.
. Es handelt sich um einen Verallgemeinerung des Binärbaumes, der ein M-Wege-Suchbaum mit m=2 ist
mit zusätzlichen Einschränkungen:
. Jeder Knoten enthält maximal 2*k Info - Komponenten und 2*k+1 Nachfolger
. Jeder Knoten (außer der Wurzel) hat mindestens k-Info-Komponenten
. Jeder Knoten (außer Wurzel und Blätter) hat mindestens n+1 Nachfolger, wobei n die Anzahl der Info-Komponenten ist
. Alle Blätter haben das selbe Niveau
VT: geringe Tiefe
Häufigkeit der Navigation verringert sich durch große Seiten
Beispiel: k = 2
Container
Definition: Objekt, das andere Objekte \"enthält\"
Container - Arten werden durch mehrere \"Koordinaten\" festgelegt:
1. durch die Zugriffsart aus \"logischer Sicht\":
STACK LIFO - Prinzip
QUEUE FIFA - Prinzip
BAG Irgendwie gespeichert
2. durch ihre \"physikalische\" Realisierung:
A) Array, Liste, Baum
B) Element selber gespeichert
Zeiger auf Kopie der Elemente:
mittels Templates universell verwendbare Klasse
Zeiger auf ursprüngliches Element:
wird häufig in C verwendet (mit void-Zeigern)
VT: auch unterschiedliche Objekte pro Container
NT: sehr fehleranfällig
|
