Upload
olympe
View
21
Download
1
Embed Size (px)
DESCRIPTION
Wintersemester 2007/08. Einführung in die Informatik für Naturwissenschaftler und Ingenieure ( alias Einführung in die Programmierung) (Vorlesung). Prof. Dr. Günter Rudolph Fakultät für Informatik Lehrstuhl für Algorithm Engineering. Kapitel 8: Elementare Datenstrukturen. Inhalt - PowerPoint PPT Presentation
Citation preview
Einführung in die Informatik für
Naturwissenschaftler und Ingenieure
(alias Einführung in die Programmierung)
(Vorlesung)
Prof. Dr. Günter Rudolph
Fakultät für Informatik
Lehrstuhl für Algorithm Engineering
Wintersemester 2007/08
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 2
Kapitel 8: Elementare Datenstrukturen
Inhalt
● Definition
● ADT Keller
● ADT Schlange
● ADT Liste
● ADT Binärbaum
- Exkurs: Einfache Dateibehandlung
- Exkurs: Strings (C++) … endlich!
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 3
Kapitel 8: Elementare Datenstrukturen
ADT Binäre Bäume
Beispiel:
Zahlenfolge 17, 4, 36, 2, 8, 19, 40, 6, 7, 37
17
4 36
2 8 19 40
6 37
7
kleiner : nach links
größer : nach rechts
z.B. „Suche, ob 42 enthalten“
benötigt nur 3 Vergleiche bis zur Entscheidung false
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 4
Kapitel 8: Elementare Datenstrukturen
ADT Binäre Bäume: Terminologie
L R
linker Unterbaum
rechterUnterbaum
Wurzel
Blätter
keine Wurzel und kein Blatt
innerer Knoten
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 5
Kapitel 8: Elementare Datenstrukturen
ADT Binäre Bäume: Datenstruktur
struct BinTree { T data; // Nutzdaten BinTree *lTree, *rTree; // linker und rechter Unterbaum};
Falls ein Unterbaum nicht existiert, dann zeigt der Zeiger auf 0.
bool IsElement(int key, BinTree *tree) { if (tree == 0) return false; if (tree->data == key) return true; if (tree->data < key) return IsElement(key, tree->rTree); return IsElement(key, tree->lTree);}
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 6
Kapitel 8: Elementare Datenstrukturen
ADT Binäre Bäume: Einfügen
BinTree *Insert(int key, BinTree *tree) { if (tree == 0) { BinTree *b = new BinTree; b->data = key; b->lTree = b->rTree = 0; return b; } else { if (tree->data < key) tree->rTree = Insert(key, tree->rTree); else if (tree->data > key) tree->lTree = Insert(key, tree->lTree); return tree; } }
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 7
Kapitel 8: Elementare Datenstrukturen
ADT Binäre Bäume: Aufräumen
void Clear(BinTree *tree) { if (tree == 0) return; // Rekursionsabbruch Clear(tree->lTree); // linken Unterbaum löschen Clear(tree->rTree); // rechten Unterbaum löschen delete tree; // aktuellen Knoten löschen}
u.s.w.1
2
3
4 5
6
7
8 9
10
11
12 13
14
15
1617
18
19
20
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 8
Kapitel 8: Elementare Datenstrukturen
ADT Binäre Bäume
Höhe := Länge des längsten Pfades von der Wurzel zu einem Blatt.
Höhe(leerer Baum) = 0
Höhe(nicht leerer Baum) = 1 + max { Höhe(linker U-Baum), Höhe(rechter U-Baum) }
(U-Baum = Unterbaum)Anmerkung: rekursive Definition!
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 9
Kapitel 8: Elementare Datenstrukturen
ADT Binäre Bäume 1
2
3
4
Auf Ebene k können jeweils zwischen 1 und 2k-1 Elemente gespeichert werden.
In einem Baum der Höhe h können also zwischen h und
Elemente gespeichert werden!
Rudolph: EINI (WS 2007/08) ● Kap. 8: Elementare Datenstrukturen 10
Kapitel 8: Elementare Datenstrukturen
ADT Binäre Bäume 1
2
3
4
Ein vollständiger Baum der Höhe h besitzt 2h – 1 Knoten.
Man braucht maximal h Vergleiche, um Element (ggf. nicht) zu finden.
Bei n = 2h – 1 Elementen braucht man log2(n) < h Vergleiche!
●
Ein degenerierter Baum der Höhe h besitzt h Knoten (= lineare Liste).
Man braucht maximal h Vergleiche, um Element (ggf. nicht) zu finden.
Bei n = h braucht man also n Vergleiche!
●