Informatik an der RWTH Aachen

• Definierte Kombination von skalaren Typen oder zusammengesetzten Typen • K-dim Vektoren

• Mehrdimensionaler Wertebereich

Typen mit endlichem Wertebereich

z.B:

• “bool“ • { 0, 1 }

• „enum“ • { Mo, Di, Mi, Do, Fr, Sa, So }

“Zahlen” mit 1-dim Wertebereich

• Beliebige Sequenz von Basisobjekten (skalare / zusammengesetzte Typen) mit variabler Länge • Arrays • Listen (einfach/doppelt verkettet) • Queue (FIFO) • Stack (LIFO)

• Per Index (random access),  

• Get(i)

• Per Marker (sequential access)
• GetFirst()
• GetNext()
• GetPrevious()

• Implementierung durch Arrays L[ ]

• Nachteile
• Elemente löschen erzeugt Lücken oder alle Elemente mit höherem Index müssen
verschoben werden
•Statische Obergrenze für Listenlänge

• Implementierung durch Pointer • Marker auf aktuelle Position • Nachteil: Elementzugriff erfordert lineare Suche • Vorteil: beliebiges Erweitern und Löschen

Y.prev← Marker Y.next← Marker.next Y.prev.next← Y Y.next.prev← Y

Liste mit eingeschränkter Funktionalität • Einfügen nur am Ende • Auslesen/Entfernen nur am Anfang 

•„First in, first out“ (FIFO)

•Array-Implementierung

class Schlange
{
Datentyp S[Länge]
int front, back
}

• Es gibt keine Zyklen • Jeder normale Knoten hat genau einen Vorgänger • Es existiert genau ein Wurzelknoten, der keinen Vorgänger hat

• Die Tiefe eines Knotens ist gleich der Länge des zugehörigen Pfades von
der Wurzel.
• Die Höhe eines Baumes ist gleich der Tiefe des tiefsten Knotens.
• Der Grad eines Knotens ist die Anzahl seiner Nachfolger.

wi Nachfolger von vi:

height(subtree(𝑤𝑖)) ≥ height(subtree(𝑣))−2

-> Die Höhe der Subbäume unterscheidet sich max. um 1