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. Dynamische Objekte; Exkurs: Bäume
  2. Erstellen Sie C++ Programme für folgende Problemstellungen:

    1. + Erweitern Sie die Implementierung des Tischlereiprogramms (Beispiel 1 aus Woche VII; Kapitel 5A) derart, dass beliebig viele Lager gleichzeitig verwaltet werden können. Lösen Sie folgende Teilaufgaben:
      • Anlegen (allozieren) eines zusätzlichen Lagers und Schließen (freigeben) eines existenten Lagers. Alle Methoden sollen wie bisher nur auf einem bestimmten Lager operieren (das beim Methodenaufruf als Objekt entsprechend übergeben wird). Der Benutzer soll in der Lage sein, das aktuelle Lager interaktiv auszuwählen.
      • Die Suche nach einem passenden Brett soll nicht nur innerhalb eines Lagers geschehen, sondern über alle Lager. Ergebnis der Suche ist neben den bisherigen Daten auch die Nummer (oder Bezeichnung) des Lagers, in dem das Brett gefunden wurde.
    2. + Erweitern Sie die Implementierung des Autoverleihprogramms (Beispiel 2 aus Woche VII; Kapitel 5A) derart, dass mehrere Garagen gleichzeitig verwaltet werden können. Lösen Sie folgende Teilaufgaben:
      • Eröffnen (allozieren) einer zusätzlichen Garage und Schließen (freigeben) einer existenten Garage. Alle Methoden sollen wie bisher nur auf einer bestimmten Garage operieren (die beim Methodenaufruf als Objekt entsprechend übergeben wird). Der Benutzer soll in der Lage sein, die aktuelle Garage interaktiv auszuwählen.
      • Das Ausmustern soll nicht nur innerhalb einer Garage durchgeführt werden, sondern über alle Garagen. Die erstellte Liste muss neben den bisherigen Daten auch die Nummer (oder Bezeichnung) der Garage enthalten, in der sich der angeführte Stellplatz befindet.
    3. + Erweitern Sie die Implementierung des CD-Verwaltungsprogramms (Beispiel 3 aus Woche VII; Kapitel 5A) derart, dass mehrere Sammlungen gleichzeitig verwaltet werden können. Lösen Sie folgende Teilaufgaben:
      • Beginn (allozieren) einer neuen Sammlung und Auflösen (freigeben) einer existenten Sammlung. Alle Methoden sollen wie bisher nur auf einer bestimmten Sammlung operieren (die beim Methodenaufruf als Objekt entsprechend übergeben wird). Der Benutzer soll in der Lage sein, die aktuelle Sammlung interaktiv auszuwählen.
      • Die Suche nach Interpret soll nicht nur innerhalb einer Sammlung geschehen, sondern über alle Sammlungen. Ergebnis der Suche ist neben den bisherigen Daten auch die Nummer (oder Bezeichnung) der Sammlung, in die entsprechende CD gefunden wurde.
    4. + Erweitern Sie die Implementierung des Bar-Progamms (Beispiel 4 aus Woche VII; Kapitel 5A) derart, dass mehrere Bars gleichzeitig verwaltet werden können. Lösen Sie folgende Teilaufgaben:
      • Eröffnen (allozieren) einer neuen Bar und Schließen (freigeben) einer existenten Bar. Alle Methoden sollen wie bisher nur auf einer bestimmten Bar operieren (die beim Methodenaufruf als Objekt entsprechend übergeben wird). Der Benutzer soll in der Lage sein, die aktuelle Bar interaktiv auszuwählen.
      • Der Bestandstest soll nicht nur innerhalb einer Bar geschehen, sondern über alle Bars. Ergebnis der Suche ist neben den bisherigen Daten auch die Nummer (oder Bezeichnung) der Bar, in der nicht mehr genügend von der entsprechenden Spiritouse vorhanden ist.
    5. Realisieren Sie eine Klasse für eine doppelt verkettete Liste, hierbei besitzt jedes Element zwei Zeiger, wobei der eine auf das vorhergehende und der andere auf das nachfolgende Element zeigt. Lösen Sie folgende Teilaufgaben:
      • Erzeugen, Löschen der gesamten Liste. Einfügen eines Elements und Bestimmung der Listenlänge.
      • Suchen nach Positionsindex, Suchen nach Inhalt des Listenelements und Löschen eines Elements.
      • Sortieren der Listenelemente in aufsteigender Reihenfolge.
    6. Realisieren Sie eine Klasse für eine zirkuläre Liste, hierbei verweist das letzte Element wieder auf das erste Element der Liste. Lösen Sie folgende Teilaufgaben:
      • Erzeugen, Löschen der gesamten Liste. Einfügen eines Elements und Bestimmung der Listenlänge.
      • Suchen nach Positionsindex, Suchen nach Inhalt des Listenelements und Löschen eines Elements.
      • Sortieren der Listenelemente in aufsteigender Reihenfolge.
    7. Implementieren Sie die Datenstruktur einer Hashtabelle mit dem Separate Chaining-Kollisionsverfahren. Beim Separate (Simple) Chaining wird die Kollisionsbehandlung mit linearen Listen bewerkstelligt, d.h. kollidierende Schlüsselwerte werden in einer linearen Überlaufkette (Liste) ausgehend vom ursprünglich gehashten Tabellenplatz gespeichert. Lösen Sie folgende Teilaufgaben:
      • Einfügen von Elementen
      • Suchen und Löschen von Elementen
      • Sortieren der Überlaufketten in aufsteigender Reihenfolge.
    8. Implementieren Sie einen Stack mit dynamisch größenveränderbarem Array:
      Die Implementierung ist sehr ähnlich der statischen Variante. Allerdings ist cont kein Array, sondern ein Zeiger (int* cont;). Der Konstruktor fordert dann erst (mit new) ein Array an und lässt den Zeiger cont auf das erste Element des Arrays zeigen. Wenn beim Einfügen das Array bereits voll ist, so wird ein neues Array angefordert, das doppelt so groß ist wie das aktuelle, die Werte werden aus dem alten Array in das neue umkopiert und das alte Array wird zurückgegeben.
      Schreiben Sie ein Hauptprogramm, mit dem man Ihre Stackimplementation testen kann und überlegen Sie sich Vor- und Nachteile dieser Implementation gegenüber der in der Vorlesung vorgestellten dynamischen Variante.
      • Implementierung wie oben beschrieben
      • Erweitern Sie den Stack derart, dass beim Löschen, falls der Füllungsgrad des Arrays 50% unterschreitet, die Größe des Arrays wieder halbiert wird.
    9. Entwickeln Sie eine Klasse List zur Verwaltung einer beliebig großen Anzahl von ganzen Zahlen (integer) mit Hilfe der Datenstruktur einer linearen Liste, indem Sie die Klasse IntStack der Vorlesung (dynamische Variante) um folgende Methoden erweitern:
      class List {
            …                       // wie IntStack (dynamische Variante)
         public:
            …                       // wie IntStack (dynamische Variante)
            bool top(int * value);  // liefert den obersten Wert des Stacks mittels Zeiger zurück.
            bool top(int & value);  // liefert den obersten Wert des Stacks mittels Referenz zurück.
            bool member(int value); // sucht value in der Liste
            int length();           // liefert die Länge der Liste (= die Höhe des Stacks)
            void print(ostream& o = cout); // gibt die Liste auf den ostream o aus
      }
      
      Schreiben Sie ein Hauptprogramm, das Ihre Implementation der Klasse entsprechend testet.
    10. Entwickeln Sie eine Klasse StrStack, die Zeichenketten beliebiger Länge auf einem Stack verwaltet.
      Anmerkung: Reservieren Sie für eine Zeichenkette, die mit push auf den Stack gelegt werden soll, dynamisch den erforderlichen Speicherplatz. Es genügt dann, die Adresse, an der sich die Zeichenkette befindet, im eigentlichen Stack abzulegen. Natürlich muss der Speicherplatz wieder freigegeben werden, wenn eine Zeichenkette mit pop aus dem Stack entfernt wird.
    11. Implementieren Sie eine Klasse String, mit der Zeichenketten beliebiger Länge verwaltet werden können. Dazu wird bei der Konstruktion des Objekts ein Array alloziert, das den aktuellen Wert aufnehmen kann. Wird der Wert so verändert, dass die Größe des Arrays nicht mehr ausreicht, so ist der Speicherplatz freizugeben und ein entsprechend größeres Array zu allozieren. Lösen Sie folgende Teilaufgaben:
      • Konstruktoren, die es erlauben sowohl 'leere' Zeichenketten zu definieren (die Größe des allozierten Arrays soll dann defaultmäßig 10 Zeichen sein), als auch Zeichenketten mit den üblichen C++ Zeichenkettenkonstanten zu initialisieren (die Größe des allozierten Arrays soll dann das nächstgrößere Vielfache von 10 ausgehend von der tatsächlich benötigten Zeichenanzahl sein). So sollen z.B. folgende Definitionen erlaubt sein
          String s;                //s besteht aus einem 10 Zeichen großen Array, das den Leerstring enthält
          String t="abc"           //t besteht aus einem 10 Zeichen großen Array, das die Zeichenkette "abc" enthält
          String u="12345678901";  //u besteht aus einem 20 Zeichen großen Array mit entsprechendem Inhalt.
        
        Außerdem ist der Zuweisungsoperator derart zu überladen, dass C++ Zeichenketten an bereits existente String Objekte zugewiesen werden können. Dabei ist unter Umständen neuer Speicherplatz zu allozieren
          s="abc"; //kein neuer Speicherplatz erforderlich
          u="123"; //kein neuer Speicherplatz erforderlich
          t="12345678901"; //es muss ein neues Array alloziert werden (das alte wird natürlich freigegeben)
        
      • Überladen Sie den Zuweisungsoperator derart, dass auch Zuweisungen von einem String an einen anderen möglich sind. Also etwa in der Form
          s=t;
        
        Warum ist der durch den Compiler automatisch generierte Zuweisungsoperator nicht ausreichend?
      • Überladen Sie den Operator + so, dass zwei String Objekte aneinandergehängt werden können. Das Resultat der Operation soll ein neues String Objekt sein.
          t=s+u; //t enthält jetzt die Zeichenkette "abc123"
        
    12. Ändern Sie das Stammbaumprogramm (Beispiel 2 aus Woche XI; Kapitel 8) so ab, dass die Anzahl der Personen insgesamt und die Anzahl der Kinder pro Person beliebig groß werden können.
    13. * Ändern Sie das Programm für Straßennetze (Beispiel 5 aus Woche XI; Kapitel 8) so ab, dass die Anzahl der Orte insgesamt und die Anzahl der Verbindungen pro Ort beliebig groß werden können. Welches Problem tritt auf, wenn ein Ort aus dem Netz entfernt werden soll? (Hinweis: "dangling pointers") Implementieren Sie eine entsprechende Erweiterung, die auch das problemlose Entfernen von Orten aus dem Straßennetz ermöglicht.
    14. * Implementieren Sie eine Klasse Person, die (mindestens) die Attribute Größe, Gewicht, Alter und IQ umfasst. Die Personen sollen in verketteten Listen gespeichert werden, wobei aber jede Person in vier Listen aufscheint. Jede der vier Listen ist nach einem der vier Attribute sortiert ("orthogonale Listen"). In der folgenden Grafik wurde aus Gründen der Übersichtlichkeit die Liste für das Alter nicht eingezeichnet.

      Schreiben Sie die Klasse PersonenListe, die alle vier Listen beinhaltet. Programmieren Sie die Methoden zum Einfügen und Löschen von Personeneinträgen.
    15. * Erweitern Sie die Implementierung des Tischlereiprogramms (Beispiel 1 aus Woche VII; Kapitel 5A) derart, dass beliebig viele Holzarten verwaltet werden können. Die Funktionalität soll ansonsten gleich bleiben.