Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Aufgabe Zeiger, Referenzen oder Kopie?

1. Erinnern Sie sich an den Bubblesort-Algorithmus aus der Einführung in die Programmierung?
   
   

   void bubblesort(double* buf, uint32_t size) {
       for (uint32_t i = 0; i < size; ++i) {
           for (uint32_t j = 0; j < size - i - 1; ++j) {
               if (buf[j] > buf[j + 1])
                   swap(buf[j], buf[j + 1]);
           }
       }
   }
   

   
   
   Für den Algorithmus fehlt nur noch die Implementierung von swap. Nur eine der folgenden drei Implementierungen produziert einen funktionierenden Sortieralgorithmus.
   
   Welche ist es und warum funktionieren die anderen Implementierungen nicht?
   
   

   void swap(double x, double y) {
       double tmp = x;
       x = y;
       y = tmp;
   }
   

   void swap(double &x, double &y) {
       double tmp = x;
       x = y;
       y = tmp;
   }
   

   void swap(double &x, double &y) {
       x = y;
       y = x;
   }
   

2. Verändern Sie bubblesort und swap derartig, dass Pointer verwendet werden, d.h. swap hat danach die Signatur void swap(double *x, double *y).
   In C++ sollten Sie immer Referenzen bevorzugen, wo es möglich ist, aber es ist dennoch wichtig, die korrekte Syntax für Pointer zu kennen.
   
3. Der folgende Code lässt sich unter GCC 8.4.0 kompilieren, stürzt aber mit der Meldung Segmentation fault (core dumped) ab. Erklären Sie, woran das Problem liegt und reparieren Sie den Code.
   
   

   #include <cstdint>
   #include <iostream>
   #include <string>
   
   std::string& as_binary_string(uint64_t num) {
       std::string s;
       for (int32_t i = 0; i < 64; ++i) {
           char digit = (num & (1ull << (63 - i))) == 0 ? '0' : '1';
           s.push_back(digit);
       }
       return s;
   }
   
   int main() {
       std::string bin = as_binary_string(420);
       std::cout << bin << "\n";
   }
   

4. Der folgende Code ist dem obigen sehr ähnlich, funktioniert aber einwandfrei.
   Wieso hat dieser Code nicht dasselbe Problem wie der andere?
   
   

   #include <iostream>
   #include <string>
   
   char& central_character(std::string &s) {
       return s[s.size() / 2];
   }
   
   int main() {
       std::string text = "HelloWorld!";
       central_character(text) = 'X';
       std::cout << text << "\n";
   }
   

5. Der folgende Code lässt sich unter GCC 8.4.0 nicht kompilieren. Erklären Sie, wo das Problem liegt.
   
   

   #include <cstdint>
   int main() {
       int32_t k = 5;
       int32_t& i = k * 20;
   }
   

   
   
   

   #include <cstdint>
   #include <string>
   
   void print_multiple_times(std::string &str, int32_t times) {
       for (int32_t i = 0; i < times; ++i) {
           std::cout << str;
       }
   }
   int main() {
       print_multiple_times(std::string("bla"), 20);
   }
   

Aufgabe Zeigerdiagramme

Was sind Zeigerdiagramme?

---

Um Zeiger, sowie Wertebelegungen in Programmen besser zu verstehen, können sogenannte Zeigerdiagramme gezeichnet werden, die den Zustand des Programms zu einem bestimmten Zeitpunkt darstellen. Ein Zeiger wird dabei durch ein Sechseck mit einem Kreis darin dargestellt. Darunter steht der Zeigertyp und dessen Name. Ausgehend vom Kreis zeigt ein Pfeil auf einen Wert, beispielsweise ein Struct in Form eines Rechtecks, in dem alle Attribute erneut als Sechsecke aufgeführt sind. Dies können entweder erneut Zeiger sein oder Attribute, die mit Werten belegt und entsprechend ausgewiesen sind. Sowohl das Rechteck, als auch alle darin liegenden Sechsecke werden darunter mit ihrem (Zeiger-)Typ und einem eventuellen Variablennamen beschrieben. Schauen sie sich als Beispiel folgendes kleine Programm an, welches das Struct punkt nutzt. Das Bild rechts zeigt ihnen das daraus resultierende Zeigerdiagramm.

struct punkt {
double x;
double y;
};

int main(){
punkt a {2.0, 1.8};
punkt *a2;
double *b = &a.x;
punkt *c = &a;
punkt *d = c;
}

    \umlpointer[x=0,y=0,name=pointer1,type=double *b]{}
    \umlpointer[x=0,y=2,name=pointer2,type=Punkt *c]{}
    \umlpointer[x=2,y=3,name=pointer3,type=Punkt *d]{}
    \umlpointer[x=5,y=3,name=pointer4,type=Punkt *a2]{}
    \umlnullptr[x=7,y=3,name=nullptr-1]{}

    \begin{umlstruct}[x=3, y=0]{Punkt a}
        \umlstructvalue[x=0,y=0, name=value1, type=double x, value=2]{}
        \umlstructvalue[x=2,y=0, name=value2, type=double y, value=1.8]{}
    \end{umlstruct}

    \umlpointto{pointer2}{Punkt a}
    \umlpointto[geometry=-|]{pointer3}{Punkt a}
    \umlpointto{pointer4}{nullptr-1}
    \umlpointto{pointer1}{value1}

Aufgabe

Stellen Sie die Situation des Speichers an den markierten Punkten 1-5 des unten stehenden Programms in je einem Zeigerdiagramm dar. Geben Sie die Diagramme in einem gerenderten Format wie etwa PDF oder PNG ab. Sie können zur Erstellung der Diagramme Tikz-UML verwenden, aber eine Abgabe in einem Zeichenprogramm Ihrer Wahl (z.B. Paint, GIMP) reicht vollkommen aus.

struct result {
    uint32_t num;
    result *ans;
    result& operator=(result &otherstruct) { 
        num = otherstruct.num;
        ans = &otherstruct;
        return *this;
    }
    result operator+(result &otherstruct) {
        return result {num+otherstruct.num,&otherstruct};
    }
};

void test(){
    result a {2,nullptr};
    result b {5,&a};
    a.num = 4;
    b.ans->num = 3;
    //------1------

    result c = a+b;
    result *d = &c;
    d->ans->num = 7;
    //------2------

    result *e = new result();
    e->ans = &c;
    e->num = 22;
    e->ans->ans->num = 5;
    c = a = b;
    //------3------

    result tmp1 = b + c;
    result tmp2 = a + tmp1;
    /* Bonus: Warum geht dieser Befehl nicht: result tmp4 = a + (b + c); */
    a = tmp2;
    result tmp3 = *e + a;
    *e = tmp3;
    uint32_t res = a.ans->ans->ans->ans->ans->num + e->num;
    //------4------
    
}

int main(){
    test();
    //------5------ (nachdem test() fertig durchgelaufen ist)
    return 0;
}

Aufgabe Doppelt verkettete Liste

Die Datenstrukur doppelt verkettete Liste ist eine situationsabhängige Alternative zu Arrays. Die Datenstruktur besteht aus Elementen, die neben ihren eigentlichen Werten zusätzlich ein Vorgänger- und ein Nachfolgerelement kennen. Hier ein Beispiel für zwei Einträge einer doppelt verketteten Liste:

Die Datenstruktur selbst enthält zwei Zeiger, die auf das erste und letzte Element zeigen. In einer leeren Liste sind beide mit dem nullptr belegt. Im folgenden Beispiel wurde der Wert 8 an Position 1 in die verkettete Liste eingefügt:

Wir werden die Funktionalität unserer doubly_linked_list so implementieren, dass der Nutzer der Datenstruktur nie mit Objekten vom Typ element interagieren muss. Das reduziert die Fehleranfälligkeit des Programms.

Aufgaben

1. Deklarieren Sie struct element und struct doubly_linked_list mit den nötigen Membervariablen. Die Datenstruktur und deren Methoden sollen in einer Headerdatei doubly_linked_list.h definiert und in einer Datei doubly_linked_list.cpp implementiert werden.
   Denken Sie an die rule of three: Beim Implementieren von Datenstrukturen mit Zeigerdatentypen (in diesem Fall doubly_linked_list) müssen sie den Destruktor (~doubly_linked_list()), den Copy-Konstruktor (doubly_linked_list(const doubly_linked_list&)) und den Copy-Assignment-Operator (doubly_linked_list& operator=(const doubly_linked_list&)) explizit überschreiben. Das gilt nicht für element, da die doubly_linked_list für deren Management zuständig ist.
2. Implementieren Sie folgende Memberfunktionen des element-Structs:
   1. void insert_after(uint64_t value);
      Anhängen eines neuen Elementes.
      Beachten Sie, dass das Nachfolgeelement von dem aktuellen Struct nicht verloren geht.
   2. void insert_before(uint64_t value);
      Hinzufügen eines neuen Elements vor der aktuellen Position.
      Beachten Sie, dass das Vorgängerelement von dem aktuellen Struct nicht verloren geht.
   3. element* remove();
      Lösche das aktuelle Element aus der Liste, gibt das Vorgängerelement zurück.
3. Implementieren Sie folgende Memberfunktionen in doubly_linked_list. Versuchen Sie dabei die Zugriffe auf die Knoten minimal zu halten.
   1. void append(uint64_t val) und void prepend(uint64_t val);
      Hängt ein neues Element ans Ende (bzw. an den Anfang) der Liste.
   2. bool insert_at(uint64_t val, size_t position);
      Fügt ein neues Element an der angegebenen Position in die Liste ein. Gibt zurück, ob das Einfügen erfolgreich war.
      
   3. size_t size();
      Ermittelt die Anzahl der Elemente der Liste.
   4. bool remove(size_t position);
      Löscht das Element, welches sich an der übergebenen Position befindet.
      Gibt zurück, ob das Löschen erfolgreich war. Denken Sie daran, dass sie dynamisch allokierte Objekte in C++ explizit durch delete löschen müssen.
   5. uint32_t operator[](size_t position) oder uint32_t get(size_t position);
      Gibt das Element an der angegebenen Position zurück.
      Gibt einen beliebigen Wert zurück, wenn der Index ungültig ist.
      
      Achtung: In vernünftigen Programmiersprachen (etwa in Python) würde man hier einen Fehler (Exception) werfen, wenn der Index außerhalb der gültigen Reichweite ist. In C++ geht das zwar theoretisch auch, bringt aber eventuell Laufzeitoverhead mit sich. Daher sieht man oft die alternative Variante, dass der Rückgabewert bei ungültigen Indizes nicht fest definiert ist. In modernem, sicherem C++ würde man grundsätzlich Exceptions bevorzugen.
      
      Übrigens: Viele Datenstrukturen in der C++-Standardbibliothek prüfen bei get, ob der angefragte Index gültig ist und werfen wenn nötig eine Exception, die operator[]-Implementierungen hingegen nicht.
   6. void print();
      Gibt alle Werte der Liste von vorne nach hinten aus.
   7. void append_merge(doubly_linked_list &b) und void prepend_merge(doubly_linked_list &b);
      Bonus: Überträgt alle Knoten einer anderen Liste an ans Ende (bzw. an den Anfang) an. Die andere Liste ist danach leer.
   8. void sort();
      Bonus: Sortiert die Liste.
4. Zeigen Sie die Verwendung aller Funktionen in ihrer main-Methode.
5. Welche der Operationen in doubly_linked_list sind unabhängig von der Listenlänge schnell, welche langsam? Begründen Sie Ihre Antwort kurz.