REFERAT-MenüDeutschGeographieGeschichteChemieBiographienElektronik
 EnglischEpochenFranzösischBiologieInformatikItalienisch
 KunstLateinLiteraturMathematikMusikPhilosophie
 PhysikPolitikPsychologieRechtSonstigeSpanisch
 SportTechnikWirtschaftWirtschaftskunde  



Listen

<!doctype html public '-//w3c//dtd html 4.0 transitional//en'>

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






Haupt | Fügen Sie Referat | Kontakt | Impressum | Nutzungsbedingungen