Artikel pedia
| Home | Kontakt | Artikel einreichen | Oberseite 50 artikel | Oberseite 50 autors
 
 


Artikel kategorien
Letztes fugte hinzu
    Ms-access

   Instrumentation + schnittstellen

   Pc tuning - volle kraft voraus für ihr system

   Informatorische grundlagen

   Javascript

   Interne sortieralgorithmen - der kern der sache

   Plotter und sonstige drucker

   Frage 20 (rössl priska)

   Internet - programmierung

   Monitore

   Semesterarbeit und spezialgebiet für informatik

   Erörterungs zum thema

   Inhaltsverzeichnis

   Einführung in die entwicklung ganzheitlicher informationssysteme:

   Titel dokument
alle kategorien




  Dynamische datenstrukturen



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 und aus einem Zeiger auf das nächste Element. Deshalb kennt jedes Element nur seinen Nachfolger. Es wird ein Zeiger (panker) auf das erste Element der Liste gespeichert, um die einfach verkettete Liste durchlaufen zu können. Jenes Element das (noch) keinen Nachfolger 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=anf->next; d = hilf->dat; delete hilf; return d; } };   void main() { int i; Stack s; s.push(1); s.push(2); s.push(3); cout << s.pop(); //Ausgabe: 3 getch(); } * doppelt verkettete Listen Jedes Element der doppelt verketteten Liste besteht aus einem Datenteil, aus einem Zeiger auf das nächste Element und einem Zeiger auf das davorliegende Element.

Es wird ein Zeiger (panker) auf das erste Element der Liste gespeichert. Damit kann man durch die Liste prev- und rückwärtsnavigieren. Das erste Element der Liste hat als prev-Zeiger NULL. Das letzte Element der Liste hat als next-Zeiger NULL. Anwendung: Schlange oder auch Queue genannt |--|-----|--| |--|-----|--| |--|-----|--| panker +--->| | | +----->| | | +----->| | | +-----> NULL | | 1 | | | | 2 | | | | 3 | | NULL <-----+ | | |<-----+ | | |<-----+ | | | |--|-----|--| |--|-----|--| |--|-----|--| Bei der Schlange wird neben dem Zeiger auf das erste Element (panker oder head) auch ein Zeiger auf das letzte Element (tail) gespeichert.   |--|-----|--| |--|-----|--| |--|-----|--| head +--->| | | +----->| | | +----->| | | +-----> NULL | | 1 | | | | 2 | | | | 3 | | NULL <-----+ | | |<-----+ | | |<-----+ | | |<---+ tail |--|-----|--| |--|-----|--| |--|-----|--| - Schlange wächst: Bei neuer Eintragung wandert der Tail-Zeiger vom Head-Zeiger weg.

  - Head- und Tail-Zeiger sind gleich, wenn nur ein Element vorhanden ist   - die Schlange ist LEER, wenn beide Zeiger auf NULL zeigen     * zyklisch verkettete Listen Bei einfach verketteten Listen:    Im letzten Element der Liste wird statt einem next-Zeiger auf NULL ein Zeiger auf    das erste Element gespeichert. /------------------------------------------------\ | | \--->|-----|--| |-----|--| |-----|--| | | 1 | +----->| 2 | +----->| 3 | +-----/ panker +--->|-----|--| |-----|--| |-----|--| Bei doppelt verketteten Listen:    Im letzten Element der Liste wird statt einem next-Zeiger auf NULL ein Zeiger auf das erste Element gespeichert.    Im ersten Element der Liste wird statt einem prev-Zeiger auf NULL ein Zeiger auf das letzte Element gespeichert.   /---------------------------------------------------------\ | | | |--|-----|--| |--|-----|--| |--|-----|--| | \--->| | | +----->| | | +----->| | | +-----/ | | | | | | | | | | | | panker +--->| | 1 | | | | 2 | | | | 3 | | | | | | | | | | | | | | /-----+ | | |<-----+ | | |<-----+ | | |<---\ | |--|-----|--| |--|-----|--| |--|-----|--| | | | \---------------------------------------------------------/ 2.) Bäume   * jeder Baum besteht aus Knoten und Kanten   * jeder Knoten stellt einen Datensatz dar   * von jedem Knoten gehen ein oder mehrere Kanten aus, die zu anderen Knoten oder NULL führen   * jeder Knoten (außer die sogenannte Wurzel) hat genau einen Vorgänger.   * alle Knoten ohne Nachfolger heißen Endknoten oder Blätter.




  * alle anderen Knoten (außer die Wurzel) heißen innere Knoten.   * Die Anzahl der Kanten zwischen einem Knoten und der Wurzel nennt man "Niveau des Knoten"   * Das größte Niveaus des Baumes nennt man Tiefe oder Höhe des Baumes. Der Binärbaum Beim Binärbaum hat jeder Knoten maximal 2 Nachfolger. Beim geordneten (sortierten) Binärbäum ist jeder Schlüssel des linken Teilbaums kleiner als der eigene Schlüssel, jeder Schlüssel des rechten Teilbaumes ist größer linker Knoten: L rechter Knoten: R     /--- RR /--- R -| | \--- RL Wurzel -| | /--- LR \--- L -| /--- LLR \--- LL -| \--- LLL   Der AVL-Baum * Deim AVL-Baum unterscheidet sich die Tiefe des linken Teilbaumes von der der rechten um maximal 1 * Bei jedem Knoten wird die Balance mitgespeichert. (Tiefe des rechten minus Tiefe des linken)   Blätter haben deshalb immer Varianz 0 * Der AVL-Baum kann nicht degenerieren   + weniger Suchaufwand   - für jeden Knoten muß die Balance mitgespeichert werden   - jede Einfüge- und Löschoperation muß Balance kontrollieren => Rechts-, Links-, od. Rechts-Links-Rotation.

Beispiel:(Zahlen in Klammer stellen Balance dar)   Alter Baum:   /--- 5 (0) | 4 (-1) -| | \--- 3 (-1) -\ | \---2 (0)   Einfügen von "1":   /--- 5 (0) | 4 (-2) -| | \--- 3 (-2) -\ | \---2 (-1) -\ | \---1 (0)   Nach Einfügen ist Rotation notwendig. Ergebnis nach Rechtsrotation.   /--- 5 (0) | 4 (-1) -| /--- 2 (0) | | \--- 3 (0) -| | \--- 1 (0)   M-Wege-Suchbaum Jeder Knoten hat    - maximal m Nachfolger    - und maximal m-1 Datenelemente    - Die Knoten im Daten sind aufsteigend sortiert    - Jedes Datenelement kann einen linken und einen rechten Nachfolger haben, der rechte      Nachfolger eines Elements entspricht dem linken Nachfolger des nächsten Datenelements.    - Ein Binärbaum ist ein M-Wege-Suchbaum mit m=2 B(ayer)-Baum Der B-Baum ist ein spezieller M-Wege-Suchbaum mit zusätzlichen Einschränkungen. Ein B-Baum der Ordnung k muß folgende Kriterien erfüllen:    - jeder Knoten hat maximal (2*k)-1 Info-Komponenten und (2*k)+1 Nachfolger    - jeder Knoten (außer Wurzel) hat mindestens k Infokomponenten    - jeder Knoten (außer Wurzel und Blätter) hat mindestens n+1 Nachfolger (Söhne),      wobei n die Anzahl der Infokomponenten ist.    - Alle Blätter haben das selbe Niveau (Anzahl Kanten bis zur Wurzel).

/-----\ /---|-----|---|-----|---|-----|---|-----|---\ | +--------->| | 2 | | 3 | | 5 | | 9 | | |-----| \---|-----|---|-----|---|-----|---|-----|---/ | | | 10 | | | |-----| /---|-----|---|-----|---|-----|---|-----|---\ | +--------->| | 12 | | 17 | | | | | | |-----| \---|-----|---|-----|---|-----|---|-----|---/ | | | 20 | | | |-----| /---|-----|---|-----|---|-----|---|-----|---\ | +--------->| | 25 | | 27 | | 28 | | | | |-----| \---|-----|---|-----|---|-----|---|-----|---/ | | | 30 | | | |-----| /---|-----|---|-----|---|-----|---|-----|---\ | +--------->| | 35 | | 37 | | 38 | | 40 | | |-----| \---|-----|---|-----|---|-----|---|-----|---/ | | | | | | |-----| | | \-----/   Da es sich um einen Suchbaum (sortierte Schlüsselbäume) handelt

Suchen artikel im kategorien
Schlüsselwort
  
Kategorien
  
  
   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

© Copyright Artikelpedia.com