5. Datenstrukturen · § search(k) stelle fest, obder Wert kin der Datenstruktur enthalten ist § Wir lernen später Datenstrukturen kennen, die auch andere Operationen, z.B. das

5. Datenstrukturen

2

Motivation§ Datenstrukturen sind neben Algorithmen weitere

wichtige Bausteine in der Informatik

§ Eine Datenstruktur speichert gegebene Daten und stellt auf diesen bestimmte Operationen zur Verfügung

§ Bisher haben wir Arrays als eine statische Datenstrukturkennengelernt, d.h. wir mussten vorab wissen, wie vieleWerte gespeichert werden sollen

§ Dynamische Datenstrukturen wachsen und schrumpfennach Bedarf, d.h. mit der Anzahl gespeicherter Werte

Informatik 1 / Kapitel 5: Datenstrukturen

3

Wörterbuch-Operationen§ Datenstrukturen sollen mindestens die folgenden

Wörterbuch-Operationen unterstützen

§ insert(k) füge den Wert k in die Datenstruktur ein§ delete(k) lösche ein Vorkommen des Werts k

in der Datenstruktur

§ search(k) stelle fest, ob der Wert k in der Datenstruktur enthalten ist

§ Wir lernen später Datenstrukturen kennen, die auch andere Operationen, z.B. das Bestimmen desMinimums, effizient unterstützen


4

Inhalt

§ 5.1 Dynamische Arrays

§ 5.2 Einfach verkettete Listen

§ 5.3 Doppelt verkettete Listen

§ 5.4 LIFO- und FIFO-Warteschlangen

§ 5.5 Prioritätswarteschlangen

§ 5.6 Suchbäume

§ 5.7 Hashtabellen


5

5.1 Dynamische Arrays§ Bei der Deklaration eines Arrays mussten wir bisher immer

dessen Größe angeben und wissen, wie viele Wertedarin gespeichert werden sollen

§ Wir lernen nun dynamische Arrays kennen, welche mit der Zahl gespeicherter Werte wachsen und schrumpfen und die Wörterbuch-Operationen unterstützen


6

Klassen in Pseudocode§ Zur Beschreibung von Datenstrukturen erweitern wir

unseren Pseudocode um Klassen, welche uns zur Kapselung von Daten und Operationen dienen

§ Hierzu führen wir die folgenden Schlüsselwörter ein

§ class zur Definition einer Klasse

§ public zum Festlegen der Sichtbarkeit eines Attributs oder einer Methode außerhalb der Klassen

§ private zum Einschränken der Sichtbarkeit eines Attributs oder einer Methode innerhalb der Klassen

§ new zum Anlegen einer neuen Instanz der Klasse


7

Klassen in Pseudocode§ Beispiel: Eine einfache Klasse zum Zählen


1 public class Counter {2 // Aktueller Wert3 private int count;4

5 // Wert erh ohen6 public int increase () {7 return count ++;8 }9

10 // Wert erfragen11 public int getCount () {12 return count;13 }14 }

8

Klassen in Pseudocode§ Deklarieren wir eine Variable vom Typ einer Klasse,

so hat diese initial den Wert null


1 Counter c;2 // c hat initial den Wert null3

4 c = new Counter ();5 // c verweist nun auf eine Instanz von Counter

9

Dynamische Arrays§ Die Idee hinter dynamischen Arrays ist, dass wir das Array

durch ein größeres Array ersetzen, wenn die Kapazitäterreicht ist, und durch ein kleineres Array, wenn die Kapazität weit unterschritten wird

§ Unser Array a wird mit einer initialen Größe (z.B. 4) deklariert und wir merken uns wie viele Werte nbereits darin gespeichert sind


a n = 0

10

Dynamisches Array


1 public class DynamicArray {2

3 // Array zum Speichern der Werte4 private int [] a;5

6 // Anzahl bisher gespeicherter Werte7 private int n;8

9 /**10 * Lege ein dynamisches Array mit initialer Gr oße 4 an11 */12 public DynamicArray () {13 a = new int [4];14 n = 0;15 }16

17 // Definition der Methoden folgt ...18 }

11

Einfügen in dynamische Arrays§ Wollen wir einen zusätzlichen Wert einfügen, müssen wir

überprüfen, ob die Kapazität des Arrays bereits erreicht ist,d.h. ob n der Größe des Arrays entspricht

§ Ist dies der Fall, so ersetzen wir zuerst das Array durch ein Array doppelter Größe und kopieren alle bisher gespeicherten Werte in das neue Array


2 1 4 7a n = 4

insert(5)

2 1 4 7a n = 4

12

Einfügen in dynamische Arrays§ Anschließend können wir den einzufügenden Wert

an die Stelle a[n] des Arrays stellen und denWert von n erhöhen

§ Das Einfügen in ein dynamisches Array hat damit Laufzeitin O(n), da wir im schlechtesten Fall alle bisher gespeicherten Werte in ein neues Arraykopieren müssen


2 1 4 7a 5 n = 5

13

Einfügen in dynamische Arrays


1 public void insert (int k) {2 // Arraygr oße verdoppeln , falls Kapazit at erreicht3 if (n == a. length ) {4 int [] an = new int [2 * a. length ];5 for (int i = 0; i < n; i++) {6 an[i] = a[i];7 }8 a = an;9 }

10 // Fuge Wert k an na chster freier Position ein11 a[n] = k;12 n++;13 }

14

Löschen in dynamischen Arrays§ Um einen Wert k zu löschen, müssen wir zuerst eines

seiner Vorkommen im Array finden

§ Wir kopieren den zuletzt eingefügten Wert a[n-1] an die Stelle des Vorkommens von k undverringern den Wert von n


2 1 4 7a 5 3 n = 6

delete(1)

2 3 4 7a 5 n = 5

15

Löschen in dynamischen Arrays§ Stellen wir fest, dass die Kapazität des Arrays weit

unterschritten wird, verkleinern wir das Array

§ Das Löschen in einem dynamischen Array hat damit Laufzeit in O(n), da wir im schlechtesten Fall dasgesamte Array durchlaufen,um den Wert k zu finden


2 3 1a n = 3

delete(1)

2 3a n = 2

16

Löschen in dynamischen Arrays


1 public void delete (int k) {2 // Lineare Suche nach Wert k3 int p = -1;4 for (int i = 0; i < n; i++) {5 if (a[i] == k) {6 p = i;7 break ;8 }9 }

10

11 // Stelle letzten gespeicherten Wert an die Stelle von k12 if (p > -1) {13 a[p] = a[n - 1];14 n--;15 }16

17 // Arraygr oße halbieren , falls weit unter Kapazit at18 if (n == a. length / 4) {19 int [] an = new int[a. length / 2];20 for (int i = 0; i < n; i++) {21 an[i] = a[i];22 }23 a = an;24 }25 }

17

Suche in dynamischen Arrays§ Um einen Wert k in einem dynamischen Array zu suchen,

verwenden wir die bereits bekannte lineare Suche

§ Die Suche in einem dynamischen Array hat damitLaufzeit in O(n), da wir im schlechtesten Falldas gesamte Array durchlaufen müssen


18

Suche in dynamischen Arrays


1 public boolean search (int k) {2 // Lineare Suche nach dem Wert k3 for (int i = 0; i < n; i++) {4 if (a[i] == k) {5 return true;6 }7 }8 return false;9 }

19

Speicherverbrauch dynamischer Arrays§ Wir haben die Größe des Arrays bei Erreichen der

Kapazität immer verdoppelt und bei unterschreiteneines Viertels der Kapazität halbiert

§ Diese Faktoren sind prinzipiell frei wählbar, sie beeinflussen jedoch den Speicherverbrauch des dynamischen Arrays sowie die effektive Laufzeitder Operationen


20

5.2 Einfach verkettete Listen§ Dynamische Arrays belegen unter Umständen mehr

Speicher als für die darin gespeicherten Wertenötig ist, zudem erfordern das Vergrößernund Verkleinern ein Kopieren der Werte

§ Listen benötigen genau so viel Speicher wie für diedarin gespeicherten Werte nötig ist

§ Listen bestehen aus sogenannten Knoten, welche jeweilseinen Wert enthalten und miteinander verkettet sind


21

Knoten einer einfach verketteten Liste§ Bei einer einfach verketteten Liste enthält jeder Knoten

einen Wert (value) und verweist auf den nächsten Knoten (next) in der Liste


valuenext

22

Knoten einer einfach verketteten Liste


1 private class Node {2

3 // Wert des Knotens4 private int value;5

6 // Nachfolgender Knoten7 private Node next;8

9 public void setValue (int v) {10 value = v;11 }12

13 public void setNext (Node n) {14 next = n;15 }16

17 public int getValue () {18 return value;19 }20

21 public Node getNext () {22 return next;23 }24

25 }

valuenext

23

Kopf einer einfach verketteten Liste§ Wir merken uns für eine einfach verkettete Liste den

ersten Knoten der Liste, genannt Kopf (head), und können von dort alle Knoten der Liste erreichen

§ Initial, wenn die Liste noch leer ist und es keine Knotengibt, hat der Kopf den Wert null


1 public class SingleLinkedList {2

3 // Kopf der Liste4 private Node head;5

6 // Definition der Methoden folgt ...7

8 }

24

Einfügen am Anfang in einfach verkettete Liste§ Zum Einfügen eines Werts k am Anfang der Liste erzeugen

wir einen neuen Knoten; dieser wird zum neuen Kopfder Liste und hat den bisherigen Kopf als Nachfolger

§ Das Einfügen am Anfang hat damit Laufzeit in O(1)


1 public void insertFirst (int k) {2 // Neuen Knoten am Anfang einf ugen3 Node node = new Node ();4 node. setValue (k);5 node. setNext (head );6 head = node;7 }

25

Einfügen am Anfang in einfach verkettete Liste§ Beispiel: Einfügen am Anfang in initial leere Liste


headnull

2

head

null

insertFirst(2)

insertFirst(4)

2

head

null4

26

Einfügen am Ende in einfach verkettete Liste§ Zum Einfügen eines Werts k am Ende einer einfach

verketteten Liste unterscheiden wir zwei Fälle

§ Ist die Liste noch leer, so erzeugen wir einen neuen Knoten mit Wert k; dieser wird neuer Kopf der Liste

§ Andernfalls müssen wir zuerst den letzten Knoten in der Liste finden; an diesen hängen wir einen neuen Knotenmit Wert k als Nachfolger an


27

Einfügen am Ende in einfach verkettete Liste

§ Das Einfügen am Ende hat Laufzeit in O(n)


1 public void insertLast (int k) {2 // Ist die Liste noch leer?3 if (head == null) {4 head = new Node ();5 head. setValue (k);6 } else {7 // Letzten Knoten finden8 Node cur = head;9 while (cur. getNext () != null) {

10 cur = cur. getNext ();11 }12 // Neuen Knoten anh angen13 Node node = new Node ();14 node. setValue (k);15 cur. setNext (node );16 }17 }

28

Einfügen am Ende in einfach verkettete Liste§ Beispiel: Einfügen am Ende einer Liste


2

head

null4

insertLast(5)

2

head

4 5 null

29

Löschen am Anfang aus einfach verketteter Liste§ Zum Löschen am Anfang einer einfach verketteten Liste

unterscheiden wir zwei Fälle

§ Ist die Liste noch leer, so gibt es nichts zu tun

§ Andernfalls machen wir den Nachfolger des aktuellen Kopfs der Liste zum neuen Kopf der Liste undgeben den im gelöschten Knoten enthaltenenWert zurück


30

Löschen am Anfang aus einfach verketteter Liste

§ Das Löschen am Anfang hat Laufzeit in O(1)


1 public int deleteFirst () {

2 int k = 0;

3 if (head != null) {

4 k = head. getValue ();

5 Node newHead = head. getNext ();

6 head. setNext (null );

7 head = newHead ;

8 }

9 return k;

10 }

31

Löschen am Anfang aus einfach verketteter Liste§ Beispiel: Löschen am Anfang einer Liste


2

head

4 5 null

deleteFirst()

head

2 5 null

32

Löschen am Ende aus einfach verketteter Liste§ Zum Löschen am Ende einer einfach verketteten Liste

unterscheiden wir zwei Fälle

§ Besteht die Liste nur aus einem Knoten, so entfernenwir diesen, indem wir den Kopf der Liste auf null setzen

§ Andernfalls müssen wir den letzten Knoten der Liste sowie seinen Vorgänger finden; wir entfernen denletzten Knoten, indem wir seinen Vorgänger aufauf null als Nachfolger verweisen lassen


33

Löschen am Ende aus einfach verketteter Liste

§ Das Löschen am Ende hat Laufzeit in O(n)Informatik 1 / Kapitel 5: Datenstrukturen

1 public int deleteLast () {2 int k = 0;3 if (head != null) {4 // Besteht die Liste nur aus einem Knoten ?5 if (head. getNext () == null) {6 k = head. getValue ();7 head = null;8 } else {9 // Zweitletzten Knoten finden

10 Node pre = head;11 Node cur = head. getNext ();12 while (cur. getNext () != null) {13 pre = cur;14 cur = cur. getNext ();15 }16 // Letzten Knoten entfernen17 k = cur. getValue ();18 pre. setNext (null );19 }20 }21 return k;22 }

34

Löschen am Ende aus einfach verketteter Liste§ Beispiel: Löschen am Ende einer Liste


2

head

4 5 null

deleteLast()

head

4 2 null

35

Löschen aus einfach verketteter Liste§ Zum Löschen eines gegebenen Werts k aus einer einfach

verketteten Liste suchen wir einen Knoten in der Liste, der den Wert enthält, und merken uns seinen Vorgänger

§ Haben wir einen solchen Knoten gefunden, entfernenwir ihn, indem seinen Nachfolger zum Nachfolgerseines Vorgängers machen


36

Löschen aus einfach verketteter Liste

§ Das Löschen hat damit Laufzeit in O(n)


1 public boolean delete (int k) {2 boolean found = false ;3 if (head != null) {4 Node pre = null;5 Node cur = head;6 while (cur != null && cur. getValue () != k) {7 pre = cur;8 cur = cur. getNext ();9 }

10 if (cur != null) {11 found = true;12 pre. setNext (cur. getNext ());13 cur. setNext (null );14 }15 }16 return found;17 }

37

Löschen aus einfach verketteter Liste§ Beispiel: Löschen aus einer Liste


2

head

4 5 null

delete(2)

head

4 5 null

38

Suche in einfach verketteter Liste§ Zum Suchen eines gegebenen Werts k in einer einfach

verketteten Liste durchlaufen wir diese und überprüfen für jeden Knoten, ob dieser den gesuchten Wert enthält


39

Suche in einfach verketteter Liste

§ Die Suche hat Laufzeit in O(n)


1 public boolean search (int k) {2 boolean found = false ;3 if (head != null) {4 Node cur = head;5 while (cur != null && cur. getValue () != k) {6 cur = cur. getNext ();7 }8 if (cur != null) {9 found = true;

10 }11 }12 return found;13 }

40

Zusammenfassung§ Dynamische Arrays unterstützen die sogenannten

Wörterbuch-Operationen, können mit der Zahlgespeicherter Werte wachsen und schrumpfen,belegen aber mehr Speicherplatz als nötig

§ Einfach verkettete Listen belegen so viel Speicherplatzwie nötig und unterstützen ebenfalls die sogenanntenWörterbuch-Operationen


41

Literatur[1] H.-P. Gumm und M. Sommer: Einführung in die

Informatik, Oldenbourg Verlag, 2012 (Kapitel 4)

[2] T. H. Cormen, C. E. Leiserson, R. Rivest undC. Stein: Algorithmen – Eine Einführung,Oldenbourg Verlag, 2009 (Kapitel 10)


Documents

5. Datenstrukturen · § search(k) stelle fest, obder Wert kin der Datenstruktur enthalten ist § Wir lernen später Datenstrukturen kennen, die auch andere Operationen, z.B. das