kw6

 Datenstruktur

 49 views
of 35
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Wir müssen also überlegen: ã Implementierung der Knoten, ã Implementierung der Kanten, ã daraus: Implementierung des Graphen insgesamt. Annahme: die…
Share
Transcript
Wir müssen also überlegen: • Implementierung der Knoten, • Implementierung der Kanten, • daraus: Implementierung des Graphen insgesamt. Annahme: die Knoteninhalte sind Zeichenketten (Vereinfachung - Knoteninhalte können beliebig komplex sein). Zunächst: Operationen auf Knoten Prinzip: Information Hiding (Verbergen von Informationen). Allgemein: Information sollten von Benutzern einer Struktur nur gelesen werden können. Änderungen sollten durch Funktions- aufrufe kontrollierbar sein. Grund: Programme als Kontrakt • zwischen Aufrufern und Akteuren, • die Aufrufer garantieren Eigenschaften von Werten, • die Akteure garantieren wohldefiniertes Verhalten, Das geht nur durch Kontrolle des Zugriffsverhaltens. Konsequenzen: • Daten in einer struct möglichst private • Zugriff: lesend und schreibend durch geeignete Funktionen. struct Bsp { int a; char b; }; Es sei deklariert: Bsp X; X.a = 1 und cout << X.a sind möglich, also schreibender und lesender Zugriff. Insbesondere kann jedes Programm, das auf X zugreifen kann, X.a ändern, ohne daß X selbst davon erfährt. struct Bsp2 { Deklariere Bsp2 Y; private: int a; Y.a ist illegal public: und wird vom Setze(int); int Lese(); Compiler char b; zurückgewiesen. }; Bsp2 Y struct Bsp2 { private: sei deklariert. int a; • Y.a ist ein illegaler public: Ausdruck, void Setze(int); • Y.b dagegen nicht, int Lese(); char b; • Zugriff auf Y.a }; lesend nur durch Y.Lese(), void Bsp2::Setze(int x) { schreibend (also a = x; verändernd) nur durch } Y.Setze(33). int Bsp2::Lese() { return a; } Konsequenz: • wenn die Inhalte der Knoten des Graphen nicht von außen (d.h. durch beliebige Benutzer) geändert werden sollen, so sollte der Inhalt als private deklariert werden. • Weiterhin sind Definitions- und Leseoperationen notwendig. Inhalt: Zeichenkette unbestimmter Länge struct Knoten { private: char * Inhalt; .... Weitere public: Felder void SetzeWert(char *); char * LeseWert(); .... }; void Knoten::SetzeWert(char *s) { for (int j = 0; s[j++] != '\0'; ); Inhalt = new char [--j]; Inhalt = s; ... } Verschaffe mir ein Stelle Länge der Zeichenkette entsprechend großes Feld. fest Zuweisung char * Knoten::LeseWert() {return Inhalt;} Weitere Operationen: int Gleich(Knoten *); Gegeben ein Knoten, möchte feststellen, ob sein Inhalt gleich dem des aktuellen Knotens ist: Alter Bekannter int Knoten::Gleich(Knoten * K) { int strcmp(char *, char *); return (strcmp((*K).Inhalt, Inhalt) == 0? true: false); } Die üblichen Konstanten Die Adjazenzlisten zu einem Knoten werden in einer verketteten Liste verwaltet. Ergibt ein private Attribut Adjazenz mit entsprechenden Funktionen: struct Knoten { private: char * Inhalt; Knoten * Adjazenz; ... public: void SetzeWert(char *); char * LeseWert(); int Gleich(Knoten *); ... Knoten * LeseAdjazenz(); void SetzeAdjazenz(Knoten *); }; Knoten * Knoten::LeseAdjazenz() { return Adjazenz; } Das sollte klar sein. void Knoten::SetzeAdjazenz(Knoten * K) { Knoten * L = new Knoten; ...; L->SetzeWert(K->LeseWert()); L->Adjazenz = Adjazenz; Adjazenz = L; } Erzeuge also einen neuen Knoten L • kopiere die Zeichenkette von K (dem Parameter) nach L: L->SetzeWert(K->LeseWert()); • füge L an den Anfang der Adjazenzliste des Knotens L->Adjazenz = Adjazenz •das ist dann die Adjazenzliste des Knotens: Adjazenz = L Schließlich werden die Knoten miteinander verkettet (Verwaltungsinformation, die nichts mit dem Graphen selbst zu tun hat). Adjazenz- Ver- Inhalt liste waltung * * Vollständige Definition von Knoten: struct Knoten { private: char * Inhalt; Knoten * Adjazenz; Knoten * Verwaltung; public: void SetzeWert(char *); char * LeseWert(); int Gleich(Knoten *); Knoten * LeseVerwaltung(); Knoten * LeseAdjazenz(); void SetzeVerwaltung(Knoten *); void SetzeAdjazenz(Knoten *); void Druck(char *, char *); }; Knoten * Knoten::LeseVerwaltung() { return Verwaltung; } (ist wieder trivial) void Knoten::SetzeVerwaltung(Knoten * K) { K->Verwaltung = Verwaltung; Verwaltung = K; } Setze den neuen Knoten an den Anfang der Verwaltungsliste Schließlich: Drucken void Knoten::Druck(char * vor, char * nach) { *ausgabe << vor << Inhalt << nach; } Datei für Texte, in denen der die Ausgabe Inhalt eingebettet werden kann (z. B. „\t“ oder „\n“) Sozusagen Basisschicht im Schichtenmodell: Definition des Graphen und seiner Grundoperationen eine klitzekleine Zwischenschicht Definition von Knoten und ihrer Grundoperationen Zwischenschicht • dient zur Realisierung von hilfreichen Operationen auf Knoten des Graphen • Operationen sind freilich nicht so vital für die Knoten, daß sie in die Knoten-Definition aufhgenommen werden müßten. • es handelt sich dabei um: • Finden eines Knoten in der Verwaltungsliste eines anderen, • Einfügen eines Knoten in dieser Liste, • Finden eines Knoten in der Adjazenzliste eines anderen, • Drucken der Adjazenzliste eines Knoten. int VerwFinde(Knoten *K, Knoten *L) { if (L == NULL) return false; else return (K->Gleich(L) ? true: VerwFinde(K, L->LeseVerwaltung())); } Knoten * VerwEinfuegen(Knoten * K, Knoten * L){ int VerwFinde(Knoten *, Knoten *); if (!VerwFinde(K, L)) K->SetzeVerwaltung(L); return K; } int AdjFinde(Knoten *K, Knoten *L) { if (L == NULL) return false; else return (K->Gleich(L) ? true: AdjFinde(K, L->LeseAdjazenz())); } void ListenDruck(Knoten *L) { if (L == NULL) *ausgabe << "}," << endl; else { *ausgabe << L->LeseWert() << (L->LeseAdjazenz() == NULL ? "" : ", "); ListenDruck(L->LeseAdjazenz()); } } Analoges Vorgehen bei der Formulierung des Graphen: • welche Komponenten sind private? • welche Operationen werden benötigt? • Hilfsoperationen wieder versteckt, damit zweifache Funktion der private-Deklaration: • Schützen vor unberechtigtem Zugriff, • Verbergen von Funktionen, die nicht außerhalb eines wohldefinierten lokalen Kontexts aufgerufen werden sollten. Der Graph besteht zunächst aus einem Zeiger auf einen Knoten (ähnlich der Wurzel bei binären Suchbäumen) und der Initialisierung: struct Graph { private: Knoten * EinKnoten; ... public: void Init(); ... }; Ein Knoten? (Ganz Gallien?) Über die Verwaltungsinformation werden alle anderen Knoten eingefügt. Die Initialisierung ist ziemlich trivial: void Graph::Init() { EinKnoten = NULL; } Hilfsfunktion: Nachsehen, wo ein Knoten auf der Verwaltungsliste eines anderen steckt; ein Zeiger auf diesen Knoten wird zurückgegeben. Wird als private vereinbart, da nur lokal verwendet. Knoten * Graph::DaIstDerKnoten(Knoten * K, Knoten * Wo) { if (Wo == NULL) return NULL; else if (K->Gleich(Wo) == true) return Wo; else return DaIstDerKnoten(K, Wo->LeseVerwaltung()); } Weiter: Testfunktionen • ist ein Knoten mit einem bestimmten Inhalt im Graphen vorhanden? • sind zwei Knoten mit einer Kante verbunden? int Graph::KnotenTesten(Knoten * K) { if (DaIstDerKnoten(K, EinKnoten) != NULL ?) return true; else return false; } int Graph::KanteTesten(Knoten * K, Knoten * L) { Knoten * OK = DaIstDerKnoten(K, EinKnoten); return (OK == NULL ? false : AdjFinde(OK, L)); } Also: • suche den Knoten K in der Verwaltungsliste von EinKnoten, • ist der Knoten nicht vorhanden (d.h. wird NULL zurück- gegeben), kann keine Kante vorhanden sein, • sonst: suche in der Adjazenzliste des Resultatknotens nach dem Knoten L. Stand der Dinge: struct Graph { private: Knoten * EinKnoten; Knoten * DaIstDerKnoten(Knoten *, Knoten *); public: void Init(); int KnotenTesten(Knoten *); int KanteTesten(Knoten *, Knoten *); ... }; Ziemlich kanonisch: Einfügen von Knoten und Kanten: void Graph::KnotenEinfuegen(Knoten * K) { if (EinKnoten == NULL) EinKnoten = K; else if (!KnotenTesten(K)) EinKnoten->SetzeVerwaltung(K); } Sehe nach, ob Nur falls der Knoten noch überhaupt schon nicht vorhanden ist, wird er ein Knoten in die Verwaltungsliste vorhanden ist. eingefügt. Einfügen einer Kante zwischen zwei Knoten: void Graph::KanteEinfuegen(Knoten *K, Knoten *L) { if (!KnotenTesten(K)) KnotenEinfuegen(K); if (!KnotenTesten(L)) KnotenEinfuegen(L); if (!KanteTesten(K, L)) { K->SetzeAdjazenz(L); L->SetzeAdjazenz(K); } } Überprüfe, ob die Schaue nach, ob die Kante bereits vorhanden Knoten überhaupt schon ist, sonst setze die vorhanden sind, füge sie Adjazenzfelder beider ggf. ein. Knoten entsprechend. Schließlich, als Hilfsfunktionen: • Konstruiere aus einer Zeichenkette einen neuen Knoten im Graphen (MkKnoten), • Druck des gesamten Graphen. Knoten * Graph::MkKnoten(char * s) { Knoten * K = new Knoten, * L; K->SetzeWert(s); L = DaIstDerKnoten(K, EinKnoten); return (L == NULL ? K : L); } Konstruiere einen Schaue nach, ob ein Knoten Knoten mit dem mit diesem Inhalt bereits Inhalt-Feld im Graphen vorhanden ist Setze Rückgabewert entsprechend Drucken: • drucke jeden Knoten, • drucke für jeden Knoten seine Adjazenzliste (kommt aus der Zwischenschicht). void Graph::Druck(char * vor, char * nach) { void ListenDruck(Knoten *); for (Knoten * K = EinKnoten; K != NULL; K = K->LeseVerwaltung()) { *ausgabe << "ADJ("; K->Druck(vor, nach); ListenDruck(K->LeseAdjazenz()); } } Insgesamt sieht die struct so aus: struct Graph { private: Knoten * EinKnoten; Knoten * DaIstDerKnoten(Knoten *, Knoten *); public: void Init(); Knoten * MkKnoten(char *); int KnotenTesten(Knoten *); int KanteTesten(Knoten *, Knoten *); void KnotenEinfuegen(Knoten *); void KanteEinfuegen(Knoten *, Knoten *); void Druck(char *, char *); }; void main() { Graph * G = new Graph; char * ara[] = {"\t", "eins", "zwei", "drei", "vier", "fünf", "sechs", "sieben"}; Knoten * MkKnoten(char *), * K[8]; G->Init(); for (int i = 1; i < 8; i++) K[i] = G->MkKnoten(ara[i]); G->KanteEinfuegen(K[1], K[2]); ... G->KanteEinfuegen(K[6], K[7]); G->Druck("", ") = {"); } (Beispielgraph) Ausgabe: ADJ(eins) = {sieben, sechs, zwei}, ADJ(sieben) = {sechs, fünf, vier, drei, zwei, eins}, ADJ(sechs) = {sieben, eins, fünf}, ADJ(fünf) = {sieben, sechs, vier}, ADJ(vier) = {sieben, fünf, drei}, ADJ(drei) = {sieben, vier, zwei}, ADJ(zwei) = {sieben, drei, eins}, Programm: prog-25.cpp
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks