Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | hraban-naas |
View: | 102 times |
Download: | 0 times |
Weiteres Programm
Studium des Breitendurchlaufs
Hierzu • zunächst Studium von Warteschlangen
• zuerst einfache Warteschlangen aus ganzen Zahlen• daraus Abstrakter Datentyp Warteschlange
• Anpassung für Baumknoten
Strategie bei den drei behandelten Durchlaufarten durchbinäre Suchbäume heißt Tiefensuche (es wird zunächst in die Tiefe und nicht in die Breite gegangen).
Alternative: Breitensuche - trage den Baum schichtenweise ab.
Beispiel:
17
6 23
4 7 18 26
17 # 6 # 23 # 4 # 7 # 18 # 26
Implementation?
Idee: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: Wurzel
17
6 23
4 7 18 26
Beispiel:
Realisierung?
Wir machen einen Ausflug in das Gebiet der Warteschlangen.
Eine Warteschlange arbeitet so:• Einfügen von Elementen am Ende • Entfernen von Elementen am Anfang
Vereinfachende Annahme für diese einführendeDiskussion: Elemente sind ganze Zahlen.
Berücksichtigt werden muß:
• ausgezeichnete Elemente Anfang (Kopf) und Ende (Fuß)
• Liste der Elemente (möchte mich nicht am Anfang auf eine feste Anzahl von Elementen festlegen; sonst: Feld möglich)
• Operationen:• Einfügen am Ende• Entfernen am Anfang• Initialisierung
Wunsch: möchte Daten und Operationen gern zusammenbetrachten können.
struct IntListe {int Element;IntListe * weiter;};
die bekannteListendeklaration.
Aber weiter: Kopf, Fuß und Operationen auf der Warteschlange?
Idee:deklariere entsprechende struct.
DieListe IntListe * DieListe;
Kopf Fuss IntListe * Kopf, *Fuss;
Einfuegen(int) IntListe * Einfuegen(int);
Entfernen() IntListe * Entfernen();
Init() IntListe * Init();
DerKopf() int DerKopf();
ListenDruck(...) void ListenDruck(ofstream *);
Warteschlange
struct Warteschlange {
};
Damit wird die Signatur der Operationen mit den Datenfür die Operationen gemeinsam deklariert.
Vorteil:
• alle Eigenschaften eines Datentyps (hier: Warteschlange) sind zusammengefaßt.
• die wesentlichen Operationen, die zu einem Datentyp gehören, werden mit dem Datentypen vereinbart, d.h.
• Lokalität der Änderungen
• Übersichtlichkeit
• Verständlichkeit
Problem: wir kennen die Signaturen der Operationen.
Was ist mit dem Code?
Der wird getrennt von der struct-Definition vereinbart.
(Analogie: • Angabe der Signatur der benutzten Funktionen in einer Funktion,• davon getrennte Angabe des Code)
(Analogie: • Angabe der Signatur der benutzten Funktionen in einer Funktion,• davon getrennte Angabe des Code)
IntListe * Warteschlange::Init() {Kopf = Fuss = NULL;return Kopf;};
Typ des Rückgabewerts
Name des Typs
Name der Funktion
“das zum TypWarteschlange gehörende Init”
IntListe * Warteschlange::Init() {DieListe = Kopf = Fuss = NULL;return DieListe;};
Beachte:
• die in der struct-Definition definierten Namen (Kopf, Fuss) sind hier sichtbar.
• der Name der struct muß angegeben werden, um die Zuordnung zu ermöglichen (Init kann ja auch bei anderen Typen vorkommen).
Weitere Beispiele
int Warteschlange::DerKopf() {return (DieListe == NULL ?
-1 : DieListe->Element);};
Konvention
void Warteschlange::ListenDruck(ofstream *aus) {IntListe * Laeufer = Kopf;
while (Laeufer != NULL) {*aus << Laeufer->Element << endl;Laeufer = Laeufer->weiter;}
};
IntListe * Warteschlange::Entfernen() {if (Kopf == NULL){
DieListe = Kopf;return NULL;
else {if (Kopf == Fuss) {Kopf = Fuss = NULL;}else {
Kopf = Kopf->weiter;}DieListe = Kopfreturn DieListe;
}};
IntListe * Warteschlange::Einfuegen(int i) {IntListe *K = new IntListe;K->Element = i;K->weiter = NULL;if (DieListe == NULL){
Kopf = K;Kopf->weiter = Fuss;}
else if (Fuss == NULL){Kopf->weiter = K;
Fuss = K;}
else {Fuss->weiter = K;Fuss = K;
} DieListe = Fuss; return DieListe;
};
der Codemüßte bekannt
sein
void main() {ofstream *out = new ofstream("aus.aus");Warteschlange W;
W.Init();for (int i=1; i < 10; i++) W.Einfuegen(i);W.ListenDruck(out); W.Einfuegen(117);*out << "\nNach Einfuegen von 117: " << endl;W.ListenDruck(out);*out << "\nKopf: " << W.DerKopf() << endl;W.Entfernen();*out << "\nNach Entfernen des ersten Elements: ";W.ListenDruck(out);*out << "\nKopf: " << W.DerKopf() << endl;
}
Deklaration der Warteschlange
Zugriff über Qualifikation
Ausgabe:
1 # 2 # 3 # 4 # 5 # 6 # 7 # 8 # 9 #
Nach Einfuegen von 117:
1 # 2 # 3 # 4 # 5 # 6 # 7 # 8 # 9 # 117 #
Kopf: 1
Nach Entfernen des ersten Elements: 2 # 3 # 4 # 5 # 6 # 7 # 8 # 9 # 117 #
Kopf: 2
Programm: prog-21.cpp
Beobachtung:
Eigentlich werden die Interna (Kopf, Fuss, DieListeetc) überhaupt nicht benötigt.
• Die Interna könnten/sollten privat, d.h. verborgen bleiben.
• Zugriff von außen nur über die entsprechenden Operationen
• Warteschlange als eine Art Datenkapsel mit• internen Zustand (Kopf, Fuss, DieListe)• Zugriffsoperationen (Einfuegen etc.)• Zustand von außen nicht änderbar
AbstrakterDaten-
typ
AbstrakterDaten-
typ
DieListe
Kopf Fuss
Einfuegen(int)
Entfernen()
Init()
DerKopf()
ListenDruck(...)
privatöffentlich
Führt zu folgender Deklaration:
struct Warteschlange {private:
IntListe * DieListe;IntListe * Kopf, * Fuss;
public:void Einfuegen(int);void Entfernen();void Init();int DerKopf();void ListenDruck(ofstream *);
};
neu
beachte:void
hierbei:• public deutet an, daß auf die darauf folgenden Namen
von außen (durch Qualifikation) zugegriffen werden darf.• private deutet an, daß die darauf folgenden Namen
vor dem Zugriff geschützt sindBeispiel: Warteschlange W sei deklariert.
Illegal: W.KopfW.DieListeW.Fuss
Legal z.B.:W.Init()W.Einfuegen(45)W.DerKopf()
void Warteschlange::Einfuegen(int i) {IntListe *K = new IntListe;K->Element = i;K->weiter = NULL;if (DieListe == NULL){
Kopf = K;Kopf->weiter = Fuss;}
else if (Fuss == NULL){Kopf->weiter = K;Fuss = K;}
else {Fuss->weiter = K;Fuss = K;
} DieListe = Kopf;
};
Änderungen:Typ der
Rückgabe ist void;return
eliminiert
Änderungen:Typ der
Rückgabe ist void;return
eliminiert
Programm: prog-21a.cpp
Allgemeine Anmerkung: Warteschlange wird ein abstrakterDatentyp (ADT) genannt.
ADTs sind charakterisiert durch• Offenlegen der Schnittstellen (Signaturen)• Verbergen der Implementation (d.h. Zugriff nur über wohldefinierte Operationen)
Wichtige Konstruktion in der Softwaretechnik, insb. imobjektorientierten Entwurf.
Wesentliches Thema für das
zweite Semester
Wesentliches Thema für das
zweite Semester
Zurück zur Breitensuche.
Strategie:•Verwendung einer Warteschlange Q, die aus Knoten des Baums besteht• Füge zunächst den Wurzelknoten in Q ein.
• der Kopf K von Q wird gedruckt.
• nach dem Druck geschieht folgendes:• ist K.LSohn != NULL, so wird dieser Knoten in Q eingefügt,• ist K.RSohn != NULL, so wird dieser Knoten in Q eingefügt,
• das geschieht solange, bis Q leer ist
Änderung imTyp des Listen-
elements
Anpassung der Datentypen: struct BinBaum {char text[maxLen];int zaehler;BinBaum * LSohn, *RSohn;
};struct BaumListe {
BinBaum * Element;BaumListe * weiter;};
struct Warteschlange {private:
BaumListe * DieListe;BaumListe * Kopf, * Fuss;
public:void Einfuegen(BinBaum *);void Entfernen();void Init();
int IstLeer();BinBaum * DerKopf();
};
void BreitenSuche(BinBaum *K, ofstream *aus) {void KnotenDruck(BinBaum *, ofstream *);Warteschlange W;
W.Init();W.Einfuegen(K);while (!W.IstLeer()) {
BinBaum *L = W.DerKopf();W.Entfernen();W.Einfuegen(L->LSohn);W.Einfuegen(L->RSohn);KnotenDruck(L, aus);
}}
zentrale Prozedur:
Programm: prog-22.cc
Herr von Ribbeck auf Ribbeck im Havelland,Ein Birnbaum in seinem Garten stand,Und kam die goldene HerbsteszeitUnd die Birnen leuchteten weit und breit,Da stopfte, wenn's Mittag vom Turme scholl,Der von Ribbeck sich beide Taschen voll,Und kam in Pantinen ein Junge daher,So rief er: »Junge, wiste 'ne Beer?«Und kam ein Mädel, so rief er: »Lütt Dirn,Kumm man röwer, ick hebb 'ne Birn.«So ging es viel Jahre, bis lobesamDer von Ribbeck auf Ribbeck zu sterben kam.Er fühlte sein Ende. 's war Herbsteszeit,Wieder lachten die Birnen weit und breit;Da sagte von Ribbeck: »Ich scheide nun ab.Legt mir eine Birne mit ins Grab.«Und drei Tage drauf, aus dem Doppeldachhaus,Trugen von Ribbeck sie hinaus,Alle Bauern und Büdner mit FeiergesichtSangen »Jesus meine Zuversicht«,Und die Kinder klagten, das Herze schwer:»He is dod nu. Wer giwt uns nu 'ne Beer?«
1 Herr1 Havelland,Ein6 von3 Birnbaum2 Herbsteszeit9 Ribbeck3 weit1 »Junge,1 Garten1 Havelland.1 Herbsteszeit,1 Mittag4 auf2 war1 wenn's1 »Ich5 'ne2 Birnen1 Grab.«1 Junge