Informatik an der RWTH Aachen

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

• Mehrdimensionaler Wertebereich

“Zahlen” mit 1-dim Wertebereich

Typen mit endlichem Wertebereich

z.B:

• “bool“ • { 0, 1 }

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

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

• 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

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

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

• Per Index (random access),  

• Get(i)

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

h: Nmin(h) = h+1

Nmax(h) = 2^(h+1)−1

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
}

Infix

Traverse(BinTree T)
if Leaf(T) then

        output(Value(T))
else 

        Traverse(Left(T))

        output(Value(T))

        Traverse(Right(T))

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