Dr. Matthias Grabert Abteilung Angewandte
Informationsverarbeitung 28. November 2002
Johannes Mayer Blatt 6
Objektorientierte Softwareentwicklung mit C++ (WS 2002/2003)
Abgabetermin: 5. Dezember 2002
Entscheiden Sie jeweils, ob die Begriffe in einer ,,Is-A``- oder
,,Part-of``-Beziehung zueinander stehen. Zeichnen Sie für die ,,Is-A``-Beziehungen
einen einfachen Abhängigkeitsgraphen und bilden Sie dadurch eine mögliche
Klassenhierarchie bezüglich Ober- und Unterklassen.
- LKW, Pkw, Auto, Reifen, Motor, Dreirad, Fahrrad, Fahrzeug, Fahrer,
Antriebsachse
- Getränkekiste, Sprudelflasche, Bierflasche, Flasche, Verschluss, Volumen
- Konzert, Besucher, Sänger, Person, Security-Guard, Manager, Schuhe, Kleidung
Implementieren sie eine Klasse für ungerichtete Graphen, die Methoden enthählt,
um
- Knoten einzufügen, entfernen, zählen und suchen,
- Kanten einzufügen, entfernen, zählen und suchen und
- die Entfernung aller Knoten von einem gegebenen Knoten zu bestimmen.
Unter Verwendung dieser Klasse sollen nun für Beispieldaten die Erdös-Zahlen (siehe
letztes Übungsblatt) berechnet werden. Ihr Programm erhählt die Daten von der
Standardeingabe. Diese enthalten die folgenden (durch Whitespace getrennten) Felder:
- Anzahl der Autoren (Integer)
- je Autor: Name des Autors (String ohne Whitespaces)
- Anzahl der Paper (Integer)
- und je Paper:
- Anzahl der Autoren (Integer)
- Titel des Papers (String ohne Whitespaces)
- je Autor: Nummern des Autors (Integer)
(Die Autoren werden mit 0 beginnend nummeriert.)
(Erdös ist immer der erste Autor in allen Datensätzen!)
Beispiel für eine Eingabe:
2
Erdos
Thomasius
3
2 Mein_erstes_Paper 0 1
1 Noch_so'n_Paper 0
1 Weiteres_Paper 1
Daraus erstellen Sie dann einen Publikationsgraphen,
in dem zwei Autoren genau dann durch eine Kante verbunden sind,
wenn sie zusammen publiziert haben, und bestimmen mit der bereits
implementierten Abstandsmethode die Erdös-Zahlen aller Autoren.
(Beachten Sie, dass es auch Autoren mit Erdös-Zahl unendlich gibt.)
Danach sollen jeweils Erdös-Zahl und Autor durch einen Tabulator
getrennt in einer eigenen Zeile ausgegeben werden, wobei die
Autoren in alphabetischer Reihenfolge erscheinen sollen.
Tipps:
- Sie dürfen nun die Klassen
string
, vector
und map
aus der STL verwenden.
- Bei der Entfernungsbestimmung sollten Sie sich merken, welche Knoten schon besucht wurden,
damit die Suche auch terminiert und nicht in einen Zyklus gerät.
- Die Entfernungsbestimmung kann folgendermaßen druchgeführt werden:
- Setze die Entfernung des Knoten, zu dem die Entfernung bestimmt werden soll, auf 0.
- Suche die noch nicht besuchten Nachbarn aller Knoten mit der bisher höchsten Entfernung
(am Anfang 0) und weise ihnen eine um 1 größere Entfernung zu.
- Wiederhole den letzten Schritt solange, bis keine weiteren Knoten mehr hinzukommen.
Dabei müssen nicht alle Knoten durchlaufen werden, sondern nur die von dem gegebenen Knoten
aus erreichbaren!
- Zu den Beispieleingaben
erdos.ta
bis erdos.tj
sind jeweils zur Überprüfung die
Ausgaben gegeben. Diese können mit dem Kommando diff
mit dem eigenen Ergebnis verglichen
werden.
- Ein Iterator einer
map
, deren Schlüssel vom Typ string
sind, durchläuft die
Schlüssel in alphabetischer Reihenfolge.
Johannes Mayer
2002-11-28