Institut für Informatik

Michael Wand
David Hartmann

Sommersemester 2020 • 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. Verifizieren Sie, dass sich die folgenden zwei Codebeispiele nicht kompilieren lassen.
   Erklären Sie, warum das so ist.
   
   

   int32_t k = 5;
   int32_t& i = k * 20;
   

   
   
   

   void print_multiple_times(std::string &str, int32_t times) {
       for (int32_t i = 0; i < times; ++i) {
           std::cout << str;
       }
   }
   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 an den markierten Punkten 1-5 des unten stehenden Programms in je einem Zeigerdiagrammen, wie sie oben eingeführt wurden, dar. Kennzeichnen Sie auch ein Objekt, sofern sich dieses auf dem Heap befindet — Sie können dies entweder im Namen des Objektes Kennzeichnen, per Kommentar-Box (umlnote) oder besser: das Objekt in einem abgegrenzten Bereich platzieren (etwa mit den tikz-uml Umgebung umlpackage).
Um die Korrektur zur erleichtern: Geben Sie die Diagramme in einem direkten Format wie etwa PDF oder PNG ab.

Hinweis:
Es ist nicht nötig \(LaTeX\) zu verwenden. Abgaben mit Paint, die die obige Syntax einhalten sind durchaus erlaubt. Alternativ zur Installation auf Ihrem Rechner können Sie auch eines der vielen Online-Tools verwenden, z.B. die Sharelatex-Instanz des ZDV o.ä.

struct Result {
    int 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 = a + b;
    Result tmp2 = tmp1 + c;
    /* Bonus: Warum geht dieser Befehl nicht: Result tmp4 = a + b + c; */
    a = tmp2;
    Result tmp3 = *e + a;
    *e = tmp3;
    int 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 flexible Datenstruktur zum Speichern von Werten. Die Datenstruktur besteht aus Elementen, die neben ihren eigentlichen Werten zusätzlich ein Vorgänger- und ein Nachfolgerelement kennen. Hier ein Beispiel für eine doppelt verkettete Liste mit zwei Einträgen:

Die Datenstruktur erhält nun zwei Zeiger, die auf das erste und letzte Element zeigen. Diese sind initial mit dem nullptr belegt. Um die Datenstruktur zu verwenden, können nun Funktionen geschrieben werden, die ausgehend von diesen Zeigern ihre Aufgabe erledigen. Eine Aufgabe wäre beispielsweise das Hinzufügen eines neuen Elements an einer bestimmten Position. Dazu müsste zunächst die Position ermittelt werden, an der das neue Element eingefügt werden soll. Im Anschluss müsste das Element wie in der folgenden Abbildung skizziert hinzugefügt werden:

Noch eine kurze Bemerkung zu der zusätzlichen Struktur im Diagramm: Eigentlich reicht es vollkommen aus ein beliebiges Element der Liste zu kennen, um auf alle anderen Elemente der Liste zugreifen zu können. Wir haben jedoch schon in der letzten Übung gelernt, dass Strukturen genutzt werden können, um interne low-level-Mechanismen von high-level-Aufgaben zu trennen. Ähnliches möchten wir auch hier erreichen. Der User Ihrer Klasse/Ihres Structs DoublyLinkedList soll die Grundfunktionalitäten nutzen können, ohne die interne Darstellung (also die interne Klasse Element) kennen zu müssen.

Aufgaben

Implementieren Sie also folgende Funktionalitäten:

1. Beginnen Sie mit den Strukturen Element und DoublyLinkedList. Die Datenstruktur und deren Methoden sollen in einer Header (oder .h) Datei definiert und in einer .cpp Datei implementiert werden.
   Zu Beachten: Insbesondere beim Arbeiten mit pointerbasierten Datenstrukturen müssen Destruktoren meist händisch definiert werden, die den Speicher des jeweiligen Objektes wieder freigeben, sobald dieser nicht mehr benötigt wird.
2. Memberfunktionen des low-level Element-Structs:
   1. void insertAfter(int value);
      Anhängen eines neuen Elementes.
      Beachten Sie, dass das Nachfolgeelement von dem aktuellen Struct nicht verloren geht.
   2. void insertBefore(int 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. Memberfunktionen des DoublyLinkedList-Structs.
   Versuchen Sie dabei die Zugriffe der Knoten minimal zu halten.
   1. void append(int val) und void prepend(int val);
      Hängt ein neues Element ans Ende (bzw. an den Anfang) der Liste.
   2. bool insertAt(int val, size_t position);
      Fügt ein neues Element an der angegebenen Position in die Liste ein.
   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.
      Hinweis: Beachten Sie insbesondere hier, ob sie den Destruktor von eventuell gelöschten Objekten aufrufen.
   5. int operator[](size_t position) oder int 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 Standarddatenstrukturen der C++-Bibliothek prüfen bei get, ob der angefragte Index valide ist und werfen je nach dem eine Exception, die operator[]-Implementierungen hingegen nicht.
   6. void print();
      Gibt alle Werte der Liste von vorne nach hinten aus.
   7. void reverse();
      Bonus: Dreht die Reihenfolge der Liste komplett um.
   8. void append_merge(DoublyLinkedList &b) und void prepend_merge(DoublyLinkedList &b);
      Bonus: Überträgt alle Knoten einer anderen Liste an ans Ende (bzw. an den Anfang) an. Die andere Liste ist danach leer.
   9. void sort();
      Bonus: Sortiert die Liste.
4. Zeigen Sie die Verwendung aller Funktionen in ihrer main-Methode.
5. Welche der Operationen sind unabhängig von der Listenlänge schnell, welche langsam? Geben Sie jeweils Beispiele an und erklären Sie die Laufzeiten.