Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Informatik Kurs an der RWTH Aachen zu.
Zusammengesetzte Typen
• Definierte Kombination von skalaren Typen oder zusammengesetzten Typen • K-dim Vektoren
• Mehrdimensionaler Wertebereich
Skalare Typen
“Zahlen” mit 1-dim Wertebereich
z.B Integer, Float, DoubleAufzählungstypen
Typen mit endlichem Wertebereich
z.B:
• “bool“ • { 0, 1 }
• „enum“ • { Mo, Di, Mi, Do, Fr, Sa, So }
Lineare Strukturen
• Beliebige Sequenz von Basisobjekten (skalare / zusammengesetzte Typen) mit variabler Länge • Arrays • Listen (einfach/doppelt verkettet) • Queue (FIFO) • Stack (LIFO)
Listen
• Zugriff auf beliebige Elemente 𝑥_i
• Per Index (random access),
• Get(i)
• Per Marker (sequential access)
• GetFirst()
• GetNext()
• GetPrevious()
Random Access:
Implementierung
Nachteile• 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
Sequential Access
Vorteil
Nachteil
• Implementierung durch Pointer • Marker auf aktuelle Position • Nachteil: Elementzugriff erfordert lineare Suche • Vorteil: beliebiges Erweitern und Löschen
Doppelt verkettete Listen
• Insert(Y)
Y.prev← Marker Y.next← Marker.next Y.prev.next← Y Y.next.prev← Y
Warteschlange
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
}
Anzahl der Knoten
• Minimale Anzahl von Knoten in einem Binärbaum der Höhe h
• Maximale Anzahl:
h: Nmin(h) = h+1
Nmax(h) = 2^(h+1)−1
Infix
Traverse(BinTree T)
if Leaf(T) then
output(Value(T))
else
Traverse(Left(T))
output(Value(T))
Traverse(Right(T))
output(')')• Es gibt keine Zyklen • Jeder normale Knoten hat genau einen Vorgänger • Es existiert genau ein Wurzelknoten, der keinen Vorgänger hat
Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.
Jetzt loslegenFür deinen Studiengang Informatik an der RWTH Aachen gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!