Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Aufgabe Includes

1. Im folgenden Beispiel schlägt die Kompilierung von main.cpp fehl.
   1. Erklären Sie, wo das Problem liegt.
   2. Nutzen Sie Include-Guards (Vorlesung C08 - Modularisierung) so, dass das Problem nicht mehr auftritt.
   Codeschnipsel

   Datei struct_a.h

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

   
   
   Datei struct_b.h

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

   
   
   Datei main.cpp

   #include "struct_a.h"
   #include "struct_b.h"
   #include <iostream>
   
   int main() {
       struct_b b(42);
       struct_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 kompiliert 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. Das Problem aus Codebeispiel 2 lässt sich mit Pointern lösen, dazu sind jedoch sogenannte forward declarations nötig. Diese zeigen dem Compiler an, dass eine Klasse später unter einem bestimmten Name deklariert wird, umfassen aber nicht die eigentliche Deklaration. Im Codebeispiel unten wird eine forward declaration für car benutzt. Ohne diese Deklaration wüsste der Compiler nicht, dass es sich bei car* um einen gültigen (Pointer-)Datentypen handelt, und würde einen Typfehler melden.

   class car;     // forward declaration
   
   class wheel {
       car* _car;
   };
   

   
   
   Direkt im nächsten Versuch probieren wir also eine Lösung mit Pointern aus. Dummerweise kompiliert 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

Für ein besonderes Bauteil werden mehrere Holzprofile zu einem Verbundquerschnitt verleimt (insbesondere überlappen sich die Querschnitte nicht). Wir wollen

Aufgaben

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

1. Implementieren Sie zunächst eine Klasse cross_section, die eine abstrakte Methode area zur Ermittlung der Querschnittsfläche enthält. Denken Sie auch daran, der Klasse einen virtuellen Destruktor (mit leerer Implementierung) hinzuzufügen, damit der Destruktor bei abgeleiteten Klassen korrekt aufgelöst wird.
2. Entwerfen Sie eine nicht-abstrakte Klasse rectangle als Subklasse von cross_section. Schreiben Sie einen Konstruktor, mit dem der Nutzer der Klasse Breite und Höhe vorgeben kann.
3. Schreiben Sie analog dazu eine Klasse semicircle.
4. Implementieren Sie eine andere Querschnitt-Klasse composite (auch als Subklasse von cross_section), die einen Verbundquerschnitt erzeugt, der aus Subklassen von cross_section zusammengesetzt ist. composite soll einen std::vector<cross_section*> speichern mit Pointern auf die individuellen Teilquerschnitte. Überlegen Sie sich, wie sich der Querschnitt eines Verbunds berechnet, und implementieren Sie area dementsprechend.
5. Schreiben Sie außerdem ein Hauptprogramm, dessen main()-Methode den abgebildeten Verbundquerschnitt mit \(r=10, b1=12, b2=18, t1=7, t2=3\) erzeugt und dessen Fläche berechnet. Achten Sie auf korrekte Speicherverwaltung.

Aufgabe (Bonus) 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 doubly_linked_list sich an beliebigen (nicht aufeinanderfolgenden) Positionen im Speicher befinden können. 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 doubly_linked_list) iteriert. Ein solches Konstrukt wird im Allgemeinen Iterator genannt.

Im Repository haben wir für Sie bereits eine Implementierung für eine doubly_linked_list hinterlegt. Sie dürfen diese Implementierung anpassen, wenn Sie es für notwendig halten. Die Deklaration des Iterations ist für diese Aufgabe bereits vorgegeben, sie gehört zu den existierenden Deklarationen in den doubly_linked_list-Header:

class linked_list_iterator {

    // all the variables you need go here

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

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

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

    // non-standard for LinkedLists due to time complexity
    linked_list_iterator& operator+=(size_t amount);

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

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

linked_list_iterator begin(doubly_linked_list &l);
linked_list_iterator end(doubly_linked_list &l);

Aufgaben

1. Implementieren Sie die angegebenen Methoden des linked_list_iterators.
   
   • begin gibt hierbei einen Iterator zurück, der auf das erste Element der doubly_linked_list zeigt.
   • end gibt einen Iterator zurück, der "hinter" das letzte Element der doubly_linked_list 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:

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