Institut für Informatik

Michael Wand
David Hartmann

Sommersemester 2020 • DIGITAL

Aufgabe Includes

1. Die folgenden drei Dateien kompillieren nicht.
   1. Erklären Sie wo das Problem liegt.
   2. Verändern Sie die Header so, dass das Problem nicht mehr auftritt.
      Hinweis: Include Guards (Vorlesung C08 - Modularisierung)
   3. Es gibt eine weitere Möglichkeit nur die main.cpp abzuändern, sodass das Problem nicht mehr auftauchen würde, nämlich indem man die Zeile #2, #include "B.h" aus der main.cpp entfernt. Verifizieren Sie zuerst, dass diese Änderung eine Kompillierung des ursprünglichen Codes ermöglicht.
      Wieso ist diese zweite Methode trotzdem nicht zu empfehlen?
   Codeschnipsel

   Datei A.h

   #include "<iostream>"
   #include "B.h"
   
   struct A {
       B b;
       A(B _b) : b(_b) {}
       void print() {
           std::cout << "B=";
           b.print();
       }
   };
   

   
   
   Datei B.h

   #include <iostream>
   
   struct B {
       int val;
       B(int _val) : val(_val) {}
       void print() {
           std::cout << "{val = " << val << "}";
       }
   };
   

   
   
   Datei main.cpp

   #include "A.h"
   #include "B.h"
   #include <iostream>
   
   int main() {
       B b(42);
       A a(b);
       b.print();
       std::cout << "\n";
       a.print();
       return 0;
   }
   

   
   
   
2. Wir haben nun einen neuen Fall, in dem zwei Klassen die jeweils andere speichern müssten. Der Code kompilliert nicht, dieses mal erscheint jedoch eine andere Fehlermeldung.
   Erklären Sie wo das Problem liegt.
   Codeschnipsel

   Datei left.h

   #include "right.h"
   
   struct Left {
       Right right;
       Left(Right _right) : right(_right) {}
   };
   

   
   
   Datei right.h

   #include "left.h"
   
   struct Right {
       Left left;
       Right(Left _left) : left(_left) {}
   };
   

   
   
   Datei main.cpp

   #include "left.h"
   #include "right.h"
   #include <iostream>
   
   int main() {
   }
   

   
   
   
3. Codebeispiel 2 hat nichts gebracht. Wir haben aber gehört, dass Forward-Declaration helfen soll. Dies sind „unausgefüllte“ Deklarationen der Structs oder Klassen, ohne weitere Details über diese mit anzugeben.
   
   Wir erklären in C++ so, dass eine Klasse (im folgenden Code-Schnipsel Car) später definiert wird und stellen nur sicher, dass der Compiler weiß, dass dieses Objekt existiert (wir müssen nur sicherstellen, dass die Klasse später genauer definiert wird). Der Nachteil hierbei ist, dass wir bis die Klasse genauer definiert wird, auf keine Details (Member, Speichergröße) zurückgreifen dürfen. Reine Pointer sind jedoch vollkommen okay, da der Speicher dafür stets durch size_t gegeben ist. Die Syntax dafür sieht folgendermaßen aus:

   class Car;     // forward declaration
   
   class Wheel {
       Car* car;
   };
   

   
   
   Direkt im nächsten Versuch probieren wir also Pointer aus. Dummerweise kompilliert der Code trotzdem nicht.
   Lösen Sie den Fehler mithilfe der hier erklärten Forward-Declarations im Header.
   Codeschnipsel

   Datei left.h

   #include "right.h"
   
   struct Left {
       Right *right;
       Left(Right *_right) : right(_right) {}
   };
   

   
   
   Datei right.h

   #include "left.h"
   
   struct Right {
       Left *left;
       Right(Left *_left) : left(_left) {}
   };
   

   
   
   Datei main.cpp

   #include "left.h"
   #include <iostream>
   
   int main() {
   }
   

   
   
   

Aufgabe Polymorphie

Nun zur Aufgabe:
Für ein besonderes Bauteil werden mehrere Holzprofile zu einem Verbundquerschnitt verleimt (insbesondere überlappen sich die Querschnitte nicht). Folgende drei Querschnitte sollen verwendet werden:

Aufgaben

Die Aufgabe ist, eine objektorientierte Klassehierarchie zu definieren, die das obige Setting representieren würde:

1. Implementieren Sie zunächst eine Klasse Querschnitt, die eine abstrakte Methode flaeche zur Ermittlung der Querschnittsfläche enthält.
2. Entwerfen Sie eine nicht-abstrakte Klasse Rechteck als Subklasse von Querschnitt. Sehen Sie einen Konstruktor zur Belegung aller vorgegebenen Attribute vor.
3. Schreiben Sie analog dazu eine Klasse Halbkreis.
4. Implementieren Sie eine andere Querschnitt-Klasse Verbund (auch als Subklasse), die einen Verbundquerschnitt erzeugt, der aus Subklassen von Querschnitt zusammengesetzt ist. Verbund soll einen std::vector<Querschnitt*> speichern mit Pointern auf die individuellen Teilquerschnitte. Überlegen Sie sich, wie man hier flaeche sinnvoll implementieren kann.

1. Schreiben Sie außerdem ein Hauptprogramm, dessen main()-Methode all Ihre Klassen erzeugt und deren Methode flaeche testet.

Aufgabe Iteratoren

uint32_t buffer[10] {1, 3, 3, 7, 4, 2, 3, 6, 0, 0};

// points to first element
uint32_t *begin = buffer + 2;
// points to the next position after the last element
uint32_t *end = buffer + 5;

for (uint32_t *p = begin; p != end; ++p) {
    std::cout << *p << "\n";
}

LinkedLists bieten a priori keine Möglichkeit durch einfache Pointerarithmetik über Elemente zu iterieren; Dies liegt daran, dass die Elemente einer DoublyLinkedList sich an beliebigen (nicht aufeinanderfolgenden) Positionen im Speicher befinden können. (Jeder Knoten wird separat durch new Instanziiert — bei einem Array wird etwa per new T[10] direkt ein ganzer Speicherblock reserviert).
In dieser Aufgabe implementieren Sie eine Klasse, die sich nach außen hin wie ein Pointer verhält, aber intern stattdessen über die im Speicher verteilten Elemente (hier einer DoublyLinkedList) iteriert. Ein solches Konstrukt wird im Allgemeinen Iterator genannt.

Im Repository haben wir für Sie bereits eine Implementierung für eine DoublyLinkedList hinterlegt. Die Deklaration des Iterations ist für diese Aufgabe bereits vorgegeben, sie gehört zu den existierenden Deklarationen in den DoublyLinkedList-Header:

class LinkedListIterator {

    // all the variables you need go here

public:
    LinkedListIterator(/* ... arguments ... */);

    int& operator*();
    int* operator->();

    // pre-increment
    LinkedListIterator& operator++();
    // post-increment
    LinkedListIterator operator++(int);

    // non-standard für LinkedLists
    LinkedListIterator& operator+=(size_t amount);

    // non-standard, very useful for LinkedLists
    void insert_after(int element);
};

bool operator ==(const LinkedListIterator &lhs, const LinkedListIterator &rhs);
bool operator !=(const LinkedListIterator &lhs, const LinkedListIterator &rhs);

LinkedListIterator begin(DoublyLinkedList &l);
LinkedListIterator end(DoublyLinkedList &l);

Aufgaben

1. Implementieren Sie die angegebenen Methoden des LinkedListIterators.
   
   • begin gibt hierbei einen Iterator zurück, der auf das erste Element der DoublyLinkedList zeigt.
   • end gibt einen Iterator zurück, der "hinter" das letzte Element der DoublyLinkedList zeigt - ein solches Element existiert natürlich nicht, überlegen Sie sich daher, wie ein solcher Iterator aussehen könnte.
   • Beachten Sie: Ist eine Liste l leer, so muss notwendigerweise begin(l) == end(l) wahr sein.
   Code zum Testen Ihrer Implementierung:

   DoublyLinkedList l;
   l.append(1);
   l.append(2);
   l.append(3);
   l.append(4);
   l.append(5);
   l.append(6);
   
   LinkedListIterator b = begin(l);
   ++b;
   ++b;
   b.insert_after(7);
   LinkedListIterator e = end(l);
   for (LinkedListIterator p = b; p != e; ++p) {
       std::cout << *p << "\n";
   }
   

2. Eine Konsequenz eines Iterators ist, dass man den "Pointer" auf ein Element speichern kann, um an einer beliebigen Stelle später weiterzuarbeiten. Welche Operationen der DoublyLinkedList (aus Übung 04) können damit deutlich beschleunigt werden?
3. Bonus: Warum gibt der eine Inkrement-Operator eine Referenz zurück, der andere aber nicht?
4. Schreiben Sie eine Funktion void insert_ones_after_zeros(LinkedListIterator first, LinkedListIterator last). Die beiden Iteratoren first und last begrenzen wie oben erklärt einen Teil einer DoublyLinkedList. Nutzen Sie die Iteratoren, um zwischen first und last eine 1 hinter jede 0 in der DoublyLinkedList einzufügen.

   DoublyLinkedList l;
   l.append(0);
   l.append(4);
   l.append(0);
   l.append(2);
   l.append(0);
   l.append(3);
   
   LinkedListIterator b = begin(l);
   ++b;
   ++b;
   LinkedListIterator e = end(l);
   insert_ones_after_zeros(b, e);
   // l sollte jetzt die Elemente 0, 4, 0, 1, 2, 0, 1, 3 enthalten.
   // Hinter die erste 0 wird keine 1 eingefügt, weil b auf das dritte Element zeigt und dadurch die erste 0 nicht zwischen b und e liegt.