Kurs:Algorithmen und Datenstrukturen/Vorlesung/Lineare Datenstrukturen

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Lineare Datenstrukturen

In diesem Kapitel behandeln wir die linearen Datenstrukturen.

Definition

Eine lineare Datenstruktur L ist eine Sequenz $L=(a_{1}...,a_{n})$. Die lineare Datenstruktur ordnet Elemente (entweder primitive Datentypen oder komplexere Datenstrukturen) in einer linearen Anordnung an.

Beispiel

Zahlenfolgen

1

2

3

4

5

6

Strings

L

I

N

E

A

R

Array und Listen

Es gibt zwei Möglichkeiten lineare Datenstrukturen zu realisieren. Entweder Arrays oder (verlinkte) Listen. Arrays belegen einen zusammenhängenden Bereich im Speicher. Elemente einer verlinkten Liste können beliebig verteilt sein. Ob zur Realisierung einer linearen Datenstruktur ein Array oder eine Liste verwendet wird, hängt von der Anwendung ab. Arrays werden meist für statische Datenstrukturen verwendet, d.h. wenn die Länge des Arrays nicht verändert wird. Listen werden meist für dynamische Datenstrukturen verwendet, d.h. wenn die Länge variabel ist. Zu den positiven Eigenschaften von Arrays zählen der schneller Zugriff auf Einzelelemente durch den Index. Zu den negativen Eigenschaften von Arrays zählen das sehr aufwändige Einfügen der Elemente. Zu den positiven Eigenschaften von Listen zählen die relativ effiziente Manipulation, zu den negativen Eigenschaften der ineffiziente Direktzugriff.

Matrizen

Enthalten die Elemente einer linearen Datenstrukturen weitere lineare Datenstrukturen, spricht man von einer Matrix. Durch weitere Verschachtelung können beliebige hochdimensionale Matrizen realisiert werden.

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24

Anwendungen

Matritzen benutzt man um Elementen zu Gruppieren oder Anzuordnen. Des weiteren dienen sie der Implementierung jeglicher Art von Tabellen. Matrizen können auch als Adjazenmatrizen genutzt werden, um Graphen darzustellen

Atomare Operationen auf lineare Datenstrukturen

Zu den Operationen gehören Lesen mit

• get(i): Element an Position i lesen
• first(): erstes Element lesen
• last(): letztes Element lesen
• next(e): Element nach Element e lesen

und Schreiben mit

• set(i,e): Element an Position i auf e setzen
• add(i,e): Element e an Position i einfügen
• del(i): Element an Position i löschen

Typische Problemstellungen

• Sortieren

5

4

6

1

3

2

$\to$

1

2

3

4

5

6

• Suchen

9

17

28

32

45

56

Wo befindet sich 34?

• Textsuche

T

G

C

G

T

A

Wo befindet sich "CG"?

• Textvergleiche

L

E

H

R

E

N

L

E

H

R

E

N

Sind beide ähnlich?

Suchen und Sortieren

Suchen und Sortieren sind voneinander abhängige Operationen. Dabei gibt es zwei Ansätze: Wenn Elemente nie sortiert sind, dann ist die Suche sehr aufwändig. Wenn die Elemente sortiert sind, wird die Suche erleichtert, jedoch kann das Sortieren an sich sehr aufwändig sein. Wenn Elemente hinzugefügt oder gelöscht werden ist diese Problematik noch sichtbarer. Nur ein unsortiertes Element macht die Suche aufwändig, doch bei jeder Einfügung oder Löschung zu sortieren ist ebenfalls sehr aufwändig. Spezielle dynamische Datenstrukturen erlauben eine automatische und effiziente Sortierung bei Einfügung oder Löschung.

Lineare Datenstruktur in Java

• Arrays:

int[] arr = new int[10];

arr[1] = 4;

• Listen:

List<Integer> myList = new LinkedList<Integer>();! myList.add(5);!

• Neben LinkedList unterstützt Java eine Reihe weiterer Listenimplementierungen mit unterschiedlichen Vor- und Nachteilen
• Schnittstelle List<Type> beinhaltet die gemeinsamen Methoden

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.3.5 und 13 zu finden.