Dynamische datenstrukturen

 Listen  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

Suchen artikel im kategorien
Schlüsselwort    Kategorien    - kategorien - astronomiebiographienbiologiechemiedeutschenglischfranzosischgeographiegeschichtehauswirtschaftinformatikitalienischkunstlateinliteraturmathematikmusikphilosophiephysikpolitikpsychologierechtsozialkundesporttechnikwirtschaft	•  Zusammenfassung Der Vorleser  •  sachtextanalyse  •  interpretation zwist  •  Fabel interpretation  •  literarische charakteristik  •  interpretation bender heimkehr  •  felix lateinbuch  •  interpretation der taucher von schiller  •  textbeschreibung  •  charakterisierung eduard selicke

Anmerkungen: * Name: * Email: URL: * Diskussion: (NO HTML)

| impressum | datenschutz