Datenstrukturen vs. Algorithmen

Im Folgenden werden wir uns hauptsächlich auf das imperative Programmierparadigma fokussieren. Dazu gibt es zunächst eine Übersicht über grundlegende Datenstrukturen. Datenstrukturen und Algorithmen sind stark verknüpft. Spezielle Datenstrukturen erlauben einfache und effiziente Algorithmen für gewisse Probleme. Ebenso können spezielle Datenstrukturen einige Probleme sehr schwer machen. Daraus folgt, dass je nach Problem ist die Wahl der Datenstruktur essentiell wichtig ist!

Beispiel Telefonbuch

Es wird eine Liste mit Namen und Nummern benutzt, die alphanumerisch sortiert ist.

101	121	123	314	456	789
Dave	Eva	Anna	Frank	Bob	Carl

Es wird eine Liste mit Namen und Nummern benutzt, die alphabetisch sortiert ist.

Anna	Bob	Carl	Dave	Eva	Frank
123	456	789	101	121	314

Es wird ein Binärbaum (Suchbaum, Index) für die Namen genutzt.

Beispiel Verkettung von Sequenzen

1	2	3	4	5	6

+

7	8	9

=

1	2	3	4	5	6	7	8	9

Bei der Verwendung von Arrays wird zunächst ein neues Array definiert und Speicher reserviert. Anschließend werden alle Elemente der Ursprungssequenzen kopiert. Danach müssen die Eingabearrays gelöscht werden (optional). Bei der Verwendung von verketteten Listen muss der “Nachfolger”-Zeiger von Element “6” auf Element “7” gesetzt werden.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 2.5 zu finden.