Kurs:Algorithmen und Datenstrukturen/Vorlesung/Datenstrukturen vs Algorithmen
Datenstrukturen vs. Algorithmen
BearbeitenIm 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
Bearbeiten- 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
Bearbeiten| 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
BearbeitenDa 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.
