Aufgaben zur UE
Einführung in die Programmierung

Legen Sie alle Programme so aus, dass der Benutzer die geforderten Berechnungen beliebig oft durchführen kann, ohne das Programm jedes mal neu zu starten.

Die mit einem Plus gekennzeichneten Aufgaben sind an konkreten Problemstellungen orientiert.

Anspruchsvollere Aufgaben sind mit einem Stern gekennzeichnet.

  1. Zeiger
  2. Erstellen Sie C++ Programme für folgende Problemstellungen:

    1. + Wie Beispiel 1 aus der Vorwoche. Alle Konten eines Kunden sollen aber über Zeiger, die im Kundenobjekt zu speichern sind, erreichbar sein. Umgekehrt soll jedes Konto über einen Zeiger mit dem zugehörigen Kunden verbunden sein.
    2. + Für die Darstellung eines Stammbaumes in einem Computerprogramm ist eine Klasse Person zu schreiben, die neben den Attributen Name und Geburtsdatum auch jeweils einen Zeiger zur Mutter und zum Vater der Person enthält. Ist ein Elternteil nicht bekannt, so wird der entsprechende Zeiger einfach auf den Wert Null gesetzt. Jedes Objekt vom Typ Person soll außerdem Zeiger zu allen Kindern (max. 20) der betreffenden Person enthalten. Insgesamt sind maximal 500 Personen zu verarbeiten, die in einem Array gespeichert werden sollen. Schreiben Sie eine Funktion bool integritaetstest(), die für alle gespeicherten Personen prüft, ob die Zeiger für die Verwandschaftsbeziehungen konsistent sind. (Es darf also z.B. nicht sein, dass eine Person, zwar einen Zeiger auf den Vater enthält, aber diese Person nicht in der Liste der Kinder des Vaters auftritt.) Die Funktion soll den Wert true liefern, falls keine Fehler gefunden wurden, false sonst.
    3. + Implementieren Sie die Klasse Person zur Darstellung eines Stammbaumes wie im Beispiel 2. Schreiben Sie eine Methode void print_nachkommen(), die Name und Geburtsdatum der Person, sowie aller ihrer Nachkommen (in einer beliebigen Reihenfolge) ausgibt. Tipp: Da alle Nachkommen einer Person die direkten Nachkommen genauso umfasst, wie die Nachkommen der Nachkommen, empfiehlt sich hier ein rekursiver Ansatz.
    4. + Wie Beispiel 3 aus der Vorwoche. Beim Sortieren soll aber ein Feld von Zeigern auf Personen verwendet werden. Müssen zwei Personen aufgrund des Sortieralgorithmus vertauscht werden, so sollen nur die entsprechenden Zeiger vertauscht werden. Welche Vor-/Nachteile könnte eine solche Implementierung im Gegensatz zu einem direkten Vertauschen der Personenobjekte haben?
    5. + Implementieren Sie eine Klasse Ort, in der jedes Objekt neben dem Ortsnamen auch noch die Verbindungen zu maximal 5 anderen Orten enthalten kann. Modellieren Sie diese Verbindungen als Zeiger auf die entsprechenden erreichbaren Orte. Schreiben sie ein Hauptprogramm, in dem Sie ein Straßennetz mit mindestens 5 Orten und 10 Verbindungen aufbauen. (Das Netz kann ruhig konstant sein und muss nicht eingelesen werden.) Jede Verbindung ist als Einbahnstraße zu interpretieren, die von dem Ort, in dem der Zeiger gespeichert ist, zu dem Ort führt, auf den der Zeiger zeigt. Der Benutzer soll die Möglichkeit haben, eine 'virtuelle Reise' durchzuführen. Das heißt von einem (fixen) Startpunkt aus werden dem Benutzer immer alle von dort direkt erreichbaren Zielorte angezeigt. Nachdem sich der Benutzer ein Ziel ausgesucht hat, gilt dieser Ort als nächster Startpunkt und so weiter. Bis man entweder an einen Ort gelangt, von dem aus keine anderen Orte erreichbar sind, oder der Benutzer das Programm abbricht.
    6. + Implementieren Sie ein Klasse Kunde, in der jedes Objekt neben dem Namen auch einen Zeiger auf einen weiteren Kunden enthalten soll. Im Hauptprogramm soll eine Warteschlange realisiert werden. Der Zeiger eines Kundenobjekts zeigt dabei immer auf den nächsten Kunden in der Schlange. (Falls der Kunde der letzte in der Schlange ist, so ist der Zeiger auf den Wert 0 zu setzen.) Es muss möglich sein, dass neue Kunden kommen (und sich brav hinten anstellen), bzw. dass der erste Kunde in der Reihe bedient wird und deshalb aus der Schlange entfernt wird. Eine Funktion soll die Namen aller Kunden, die zum aktuellen Zeitpunkt in der Schlange stehen, in der korrekten Reihenfolge ausgeben.
    7. Schreiben Sie ein Programm, in dem für die einfachen Datentypen int und char, sowie für eine beliebige simple Klasse als Grundtyp folgende Variablen vereinbart werden: jeweils eine Variable vom Grundtyp, jeweils eine Variable als Zeiger auf den Grundtyp, jeweils eine Variable als Zeiger auf einen Zeiger auf den Grundtyp, jeweils eine Variable als Referenz auf den Grundtyp und eine Variable als Referenz auf einen Zeiger auf den Grundtyp. Belegen Sie alle Variablen mit sinnvollen Werten und überlegen (oder testen) Sie, welche Arten von Zuweisungen unter den verschiedenen Variablen möglich sind. Für den Fall, dass der Grundtyp eine Klasse ist, müssen Sie auch für jede der entsprechenden Variablen die print()-Methode des zugehörigen Objekts aufrufen. Warum können keine Variablen als Referenz auf eine Referenz auf den Grundtyp vereinbart werden?
    8. Schreiben Sie eine Funktion, die aus einem double Array, das als Parameter übergeben wird, folgende statistische Werte berechnet und zurückliefert: die Summe der Werte, den Mittelwert, den Median, das Maximum und das Minimum. Außerdem soll eine sortierte Version des Arrays ebenfalls zurückgeliefert werden. Das ursprüngliche Array soll unverändert bleiben. Speicherplatz für das sortierte Array muss von der aufrufenden Funktion zur Verfügung gestellt werden.
    9. Erweitern Sie die Klasse IntStack aus der Vorlesung um die Methoden

      bool IntStack::top(int * value) const;
      bool IntStack::top(int & value) const;

      die es dem Benutzer ersparen, vor jedem Aufruf der Methode top die Methode isEmpty() aufrufen zu müssen.
      Wenn (mindestens) ein Element am Stack liegt, sollen die Methoden den Wert des obersten Elements über den Parameter value zurückgeben; die Methode soll als Funktionswert true liefern. Ist der Stack aber leer, soll value unverändert bleiben und die Methode false zurückliefern. Verstecken Sie die ursprüngliche top Methode vor dem unbedarften User, so daß nur mehr die beiden neu definierten Methoden außerhalb der Klasse bekannt sind. Schreiben Sie ein Hauptprogramm, mit dem Sie beide Methoden testen können.
    10. Verändern Sie die Klasse String aus dem 5. Beispiel der Vorwoche so, dass der Operator == nicht testet, ob der Inhalt (die Zeichenkette) der Objekte gleich ist, sondern ob es sich bei beiden Objekten um ein und dasselbe Objekt handelt. (Dies lässt sich am einfachsten durch einen Vergleich der Adresse der Objekte im Speicher bewerkstelligen. Das Schlüsselwort this liefert innerhalb einer Methode einen Zeiger auf das Objekt, für das die Methode aufgerufen wurde.) Der Operator != soll weiterhin den Inhalt der Objekte vergleichen. Zeigen Sie, dass dann !(a==b) nicht mehr gleichbedeutend ist mit (a!=b). Erklären Sie den Sachverhalt und suchen Sie außerdem einen Weg, zwei Variable x und y, die Variable vom Typ String bezeichnen, in Ihrem Programm zu definieren, so dass x==y gilt.
    11. Schreiben Sie eine Klasse Person, die nur eine Instanzvariable vom Typ char [160] enthält, in der aber der Vorname, der Familienname und ein Kennwort abgespeichert werden sollen. Um dies zu erreichen werden die drei Teilstrings durch ':' getrennt in einen String zusammengefasst z.B.:
      Hans:Wurst:Kasperlpost
      Schreiben Sie einen Konstruktor, der alle drei Teilstrings als Parameter enthält und ein entsprechendes Objekt erzeugt. Weiters wird eine Methode print benötigt, die alle drei Teilstrings durch Leerzeichen getrennt ausgibt, sowie die Methoden print_vorname,print_zuname und print_kennwort, die jeweils den entsprechenden Teilstring am Bildschirm ausgeben.
      Beachten Sie, dass die Teilstrings unter Umständen auch das Zeichen ':' enthalten können. Ein üblicher 'Programmiertrick' um dieses Problem zu lösen, besteht darin eventuelle Doppelpunkte in Teilstrings beim Zusammenfassen zu verdoppeln. Aus den Informationen 'James:Geronimo' 'Bond' 'Agent:007' wird dann die Zeichenkette 'James::Geronimo:Bond:Agent::007'. Beim Trennen der Zeichenkette in die einzelnen Teile ist aus doppelten Doppelpunkten wieder ein einfacher zu machen. Einfache Doppelpunkte trennen die verschiedenen Teile.
    12. * Ändern Sie die Klasse Iterator (Bsp. 14 der Vorwoche) so, dass die Methode obj überflüssig wird. Statt dessen soll der Operator * (Dereferenzierung) und die Operatoren ++ und -- derart überladen werden, dass das kurze Programmstück im Beispiel aus der Vorwoche nun folgendermaßen geschrieben werden kann:
      Iterator it;
      (*it++).print(); //Ausgabe von 'a'
      (*it--).print(); //Ausgabe von 'b'
      (*it).print(); //Ausgabe von 'a'
    13. * Erweitern Sie die Klasse Kunde aus Beispiel 6 um eine zusätzliche Instanzvariable 'Prioritaet' vom Typ int. Implementieren Sie eine Funktion, die die Warteschlange so umsortiert, dass die Kunden nach Priorität geordnet in der Schlange stehen. Zwei Kunden gleicher Priorität müssen die ursprüngliche Reihenfolge in der Schlange beibehalten (= das Sortierverfahren muss stabil sein).
    14. * Ausgehend von einer Klasse Ort und einem entsprechenden Straßennetz, wie im Beispiel 5 beschrieben, ist eine Funktion zu implementieren, die feststellt, ob es eine Verbindung von einem Ort A zu einem Ort B gibt, oder nicht. (A und B sind vom Benutzer frei wählbar.) Tipp: Sie können rekursiv vorgehen, indem Sie die Tatsache nutzen, dass ein Weg von A nach B genau dann existiert, wenn entweder eine direkte Verbindung vorhanden ist, oder ein Weg von irgendeinem der von A aus direkt erreichbaren Orte nach B existiert. Ein iterativer Ansatz wäre folgendermaßen möglich: Beginnend mit einer Menge, die nur den Ort A enthält, werden alle Orte in die Menge aufgenommen, die von A aus erreichbar sind. Im nächsten Schritt alle Orte, die von irgendeinem der neu hinzugekommenen Elemente der Menge erreichbar sind. Das Verfahren stoppt, sobald entweder B in die Menge aufgenommen werden soll (dann gibt es einen Weg) oder in einem Schritt keine neuen zusätzlichen Elemente in die Menge augenommen wurden (dann gibt es keinen Weg). Bei Bedarf können Sie die Klasse Ort um beliebige Instanzvariablen erweitern (wie z.B. schon_besucht oder ähnliche).
    15. * Wie Beispiel 3, allerdings sollen die Nachkommen geordnet ausgegeben werden. Zunächst die Person, dann alle Kinder, dann alle Enkel, dann die Urenkel und so weiter.