Kurs:Algorithmen und Datenstrukturen/Vorlesung/Lineare Datenstrukturen

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Lineare Datenstrukturen[Bearbeiten]

In diesem Kapitel behandeln wir die linearen Datenstrukturen.

Definition[Bearbeiten]

Eine lineare Datenstruktur L ist eine Sequenz . Die lineare Datenstruktur ordnet Elemente (entweder primitive Datentypen oder komplexere Datenstrukturen) in einer linearen Anordnung an.

Beispiel[Bearbeiten]

Zahlenfolgen

5 4 6 1 3 2

Strings

L I N E A R

Array und Listen[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

  • Sortieren
5 4 6 1 3 2

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[Bearbeiten]

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[Bearbeiten]

  • 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[Bearbeiten]

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.

Vorheriges Thema.jpg Discussion Nächstes Thema.jpg