EINI-I
Einführung in die Informatik
für Naturwissenschaftler und
Ingenieure I
Vorlesung
2 SWS
WS ‘99/00
Gisbert Dittrich
FBI Unido
[email protected]
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Gliederung Kapitel 9
• Einfache Dateibehandlung
• Beispiel: Wörter zählen
– Problem, Datenstruktur
– Einfügen: Strategie + Implementierung
– Alphabetisch geordnete Ausgabe: Strategie + Impl.
• Durchlaufstrategien
– In die Tiefe
• Inorder
• Präorder
• Postorder
– In die Breite
25.1.2000
2
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Dateien
• Einfache Dateibehandlung
– (externe Dateien, Öffnen, Lesen/Schreiben,
Schließen).
– Am Beispiel: Problem, die Wörter in einem
gegebenen Text zu zählen und sie mit ihrer
Häufigkeit alphabetisch geordnet auszugeben.
• Zunächst: Dateien
• Lies aus einer Eingabe-Datei, schreibe in eine
Ausgabe-Datei. Am elementaren Beispiel.
• Programm
25.1.2000
3
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Dateien
• #include <fstream.h>
bindet die Bibliothek zur Dateibehandlung ein
• Bindung von Datei-Variablen (im Programm) an
Dateien (im Dateisystem) beim Öffnen der
Datei.
ifstream *Eingabedatei;
EingabeDatei = new ifstream (inpDat);
• Benutzung von Dateien: wie Standard Ein-/Ausgabe
– ifstream: Eingabe - ofstream: Ausgabe
• Benutzung: wie cin
25.1.2000
– *Eingabedatei >> gelesen;
4
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Dateien
• Testen:
!(*Eingabedatei).eof()
(liefert "true" genau dann, wenn das Ende der Datei
noch nicht erreicht ist; eof: end of file)
• Analog: ofstream *AusgabeDatei;
• Werden Dateien zum Schreiben geöffnet, so
geht meist ihr vorheriger Inhalt verloren.
25.1.2000
5
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Wörter zählen
• Problem:
– zähle die Wörter in einem gegebenen Text,
– gib sie mit ihrer Häufigkeit alphabetisch geordnet
aus.
• Datenstruktur:
– binärer Suchbaum (--> Wörter lassen sich ordnen)
– erweitert um einen Zähler.
25.1.2000
6
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Datenstruktur zum Zählen von Wörtern
text
zaehler
LSohn RSohn
struct BinBaum {
char text[maxLen];
int zaehler;
BinBaum * LSohn, *RSohn;
};
25.1.2000
7
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Strategie zum Einfügen
• Suchen nach einer Zeichenkette im binären
Suchbaum
– Zeichenkette nicht gefunden:
• neuen Knoten einfügen,
• Zähler zu 1 initialisieren
– Zeichenkette gefunden:
• Zähler um 1 erhöhen
25.1.2000
8
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
void strcpy(char *, char *);
int strcmp(char *, char *);
BinBaum * Einfuegen(BinBaum *B, char * k) {
if (B == NULL) {
BinBaum *Hilf = new BinBaum;
Text noch
strcpy(Hilf->text, k);
nicht
Hilf->zaehler = 1;
gesehen
Hilf->LSohn = Hilf->RSohn = NULL;
return Hilf;
}
else {
int Vergl = strcmp(B->text,k);
Text
if (Vergl < 0)
bekannt:
B->RSohn = Einfuegen(B->RSohn, k);
einfügen,
else if (Vergl > 0)
Zähler
B->LSohn = Einfuegen(B->LSohn, k);
erhöhen
else if (Vergl == 0)
B->zaehler += 1;
return B;
}
25.1.2000
}
9
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Alphabetisch geordnete Ausgabe
• Behauptung:
• Nachfolgender Durchlauf liefert als Resultat:
– geordnete Ausgabe
• Durchlaufstrategie:
– Durchlaufe den binären Suchbaum mit Wurzel w
rekursiv wie folgt:
• Durchlauf durch den linken Unterbaum von w
• Ausdruck (der Nutzinfo) der Wurzel w
• Durchlauf durch den rechten Unterbaum von w
25.1.2000
10
Vorl “EINI-I"
Prof. Dr. G. Dittrich
Kap 9: Durchlaufstrategien
Beispiel (Baumdurchlauf)
17
6
4
23
7
18
26
4 6 7 17 18 23 26
17
6
4
25.1.2000
23
7
18
26
11
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Beweis
• Durch vollständige Induktion nach der
Anzahl der Knoten
– Der Induktionsbeginn (kein Knoten) ist erfüllt
– Der Induktionsschritt:
• der linke Unterbaum wird geordnet ausgegeben
(IV),
• dann wird die Wurzel ausgegeben,
• dann wird der rechte Unterbaum geordnet
ausgegeben (IV).
(Die Wurzel steht bzgl. der Ordnung "in der Mitte".)
25.1.2000
12
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Programmtext: Ausdrucken
void KnotenDruck(BinBaum *, ofstream *);
void Ausdrucken(BinBaum *K, ofstream *aus) {
if (K != NULL) {
Ausdrucken(K->LSohn, aus);
KnotenDruck(K, aus);
Ausdrucken(K->RSohn, aus);
}
}
Programm
25.1.2000
13
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Anmerkungen
• Zugriff auf Ein- und Ausgabedateien wird über
Zeiger auf ifstream- und ofstream-Variablen
bewirkt.
• Initialisierungen
– EingabeDatei = new ifstream(inpDat);
– AusgabeDatei = new ofstream(outpDat);
• Varianten (Ausgabedateien als Konstante
bekannt) z.B.:
– ofstream *Ausgabe = new ofstream("von.aus");
25.1.2000
14
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
BinBaum * Einfuegen(BinBaum *, char *);
BinBaum * Einlesen(ifstream *inp) {
BinBaum *bst = NULL;
char gelesen[maxLen];
*inp >> gelesen;
while (!(*inp).eof()) {
bst = Einfuegen(bst, gelesen);
*inp >> gelesen;
}
return bst;
}
Feinheiten: *inp und (*inp).eof()
25.1.2000
15
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Analog: Ausgabe
void Schreiben(char *, int, ofstream *);
void KnotenDruck(BinBaum *T, ofstream *aus){
Schreiben(T->text, T->zaehler, aus);
}
void Schreiben(char * s, int k, ofstream *aus){
*aus << k << "\t\t\t" << s << endl;
}
25.1.2000
16
Vorl “EINI-I"
Prof. Dr. G. Dittrich
Kap 9: Durchlaufstrategien
Durchlauf durch Bäume
17
6
4
Inorder
23
7
(
Diese Art des Durchlaufs
heißt Inorder-Durchlauf.
18
26
Inorder(Wurzel BLinks)
w
BLinks
4 6 7 17 18 23 26
BRechts
)=
Druck(w)
Inorder(Wurzel BRechts)
25.1.2000
17
Vorl “EINI-I"
Prof. Dr. G. Dittrich
Kap 9: Durchlaufstrategien
Druck(w)
Präorder
(
w
BLinks
BRechts
)=
Präorder(Wurzel BLinks)
Präorder(Wurzel BRechts)
17 6 4 7 23 18 26
17
6
4
25.1.2000
23
7
18
26
18
Vorl “EINI-I"
Prof. Dr. G. Dittrich
Postorder
(
Postorder(Wurzel BLinks)
w
BLinks BRechts
)=
4
25.1.2000
Postorder(Wurzel BRechts)
Druck(w)
4 7 6 18 26 23 17
17
6
Kap 9: Durchlaufstrategien
23
7
18
26
19
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Durchlaufstrategien
• Strategie bei allen drei Durchlaufarten heißt
Tiefensuche:
Es wird zunächst in die Tiefe und nicht in die Breite
gegangen.
• Alternative: Breitensuche
Trage den Baum "schichtenweise" ab.
25.1.2000
20
Vorl “EINI-I"
Prof. Dr. G. Dittrich
Kap 9: Durchlaufstrategien
Beispiel Breitensuche
17
6
4
23
7
18
26
17 6 23 4 7 18 26
25.1.2000
21
Prof. Dr. G. Dittrich
Vorl “EINI-I"
Kap 9: Durchlaufstrategien
Idee zur Implementation
Verwalte die Knoten in einer "Warteschlange"
• ein Knoten wird gedruckt
• seine Söhne werden in die Warteschlange
eingefügt
bis die Warteschlange leer ist
Initialisierung der Warteschlange mit der Wurzel
des Baums.
25.1.2000
22
Vorl “EINI-I"
Prof. Dr. G. Dittrich
Kap 9: Durchlaufstrategien
Beispiel
17
6
4
23
7
18
17
25.1.2000
26
6
23
4
7
18
26
23

Durchlaufstrategien