Vererbung

Öffnen Sie VS Code entsprechend Ihrem Setup.

Öffnen Sie Ihr Terminalfenster und führen Sie dann cd aus. Die Eingabeaufforderung Ihres Terminalfensters sollte wie folgt aussehen:

$

Geben Sie dann

wget https://inf.zone/download/exercises/05/inheritance.zip

ein und führen Sie den Befehl mit der Eingabetaste aus, um eine ZIP-Datei namens inheritance.zip in den aktuellen Ordner herunterzuladen. Achten Sie darauf, dass Sie das Leerzeichen zwischen wget und der folgenden URL nicht übersehen, und auch kein anderes Zeichen!

Führen Sie jetzt

unzip inheritance.zip

aus um das ZIP-Archiv in einen Ordner namens inheritance zu extrahieren. Sie brauchen die ZIP-Datei nicht mehr, also können Sie

rm inheritance.zip

ausführen. Antworten Sie mit “y”, gefolgt von der Eingabetaste, um die heruntergeladene ZIP-Datei zu entfernen.

Führen Sie dann

cd inheritance

aus, um in dieses Verzeichnis zu wechseln. Ihre Eingabeaufforderung sollte nun wie folgt aussehen:

inheritance/ $

Wenn alles wie beschrieben funktioniert hat, sollten Sie nach dem Ausführen von

ls

eine Datei, inheritance.c, sehen.

Betrachten wir zunächst die Definition eines Typs namens person. Jede Person hat ein Array von zwei parents, von denen jedes ein Zeiger auf eine andere person-struct ist. Jede Person hat auch ein Array mit zwei alleles, von denen jedes ein char ist (entweder A, B oder O).

// Each person has two parents and two alleles
typedef struct person
{
    struct person *parents[2];
    char alleles[2];
}
person;

Werfen wir nun einen Blick auf die main-Funktion. Die Funktion beginnt mit dem “Seeding” (d.h. der Bereitstellung eines Anfangsinputs) eines Zufallszahlengenerators, den wir später zur Erzeugung von Zufallsallelen verwenden werden.

// Seed random number generator
srand(time(0));

Diese Funktion ändert die Folge von Pseudozufallszahlen, die beim Aufruf der Funktion rand() zurückgegeben werden. Der Aufruf von srand(time(0)) bewirkt, dass die Funktion rand() bei jedem Programmaufruf Zahlen in einer anderen Reihenfolge ausgibt, da time, d.h. die Systemzeit, bei jedem Aufruf anders ist. Daher sollte diese Funktion ein Mal vor der ersten Verwendung von rand() aufgerufen werden. Da dies bereits im Codegerüst geschieht, brauchen Sie sich um nichts weiteres zu kümmern, d.h. Sie müssen nicht jedes Mal, bevor Sie rand() aufrufen, srand() erneut aufrufen. Einzig relevant ist noch folgende Information: Wenn die Funktion rand() im weiteren Verlauf des Codes aufgerufen wird, gibt diese pseudo-zufällige Zahlen zwischen 0 und RAND_MAX (im Falle des CS50-Setups steckt dahinter die Zahl 32767) zurück - die benötigte Bibliothek <stdlib.h> ist ebenfalls bereits im Codegerüst eingebunden.

Die Funktion rand() werden Sie später noch benötigen. rand() kommt aber auch in der bereits implementierten Funktion random_allele() vor:

// Randomly chooses a blood type allele.
char random_allele()
{
    int r = rand() % 3;
    if (r == 0)
    {
        return 'A';
    }
    else if (r == 1)
    {
        return 'B';
    }
    else
    {
        return 'O';
    }
}

Wieso wird hier rand() % 3 verwendet?

Die main-Funktion ruft dann die Funktion create_family auf, um die Erstellung von person-structs für eine Familie mit 3 Generationen (d.h. eine Person, ihre Eltern und ihre Großeltern) zu initiieren.

// Create a new family with three generations
person *p = create_family(GENERATIONS);

Wir rufen dann print_family auf, um jedes dieser Familienmitglieder mit seinen jeweiligen Allelen auszugeben.

// Print family tree of blood types
print_family(p, 0);

Schließlich wird die Funktion free_family aufgerufen, um Speicher mit free freizugeben, der zuvor mit malloc allokiert wurde.

// Free memory
free_family(p);

Die Vervollständigung dieser beiden Funktionen create_family und free_family ist nun Ihre Aufgabe!

Die Funktion create_family sollte einen Zeiger auf eine person zurückgeben, die ihre Allele über die angegebene Anzahl von generations geerbt hat.

• Überlegen Sie zunächst, warum dieses Problem eine gute Gelegenheit für eine Rekursion bietet.
  • Um die Allele der jetzigen Person zu bestimmen, müssen Sie zunächst die Allele ihrer Eltern ermitteln.
  • Um die Allele dieser Eltern zu bestimmen, müssen Sie zunächst die Allele ihrer Eltern bestimmen. Und so weiter, bis Sie die letzte Generation erreicht haben, die Sie simulieren möchten.

Um dieses Problem zu lösen, finden Sie mehrere TODOs im im Code des Aufgabenmaterials.

Zuerst sollten Sie Speicher für eine neue Person zuweisen. Erinnern Sie sich, dass Sie malloc verwenden können, um Speicher zuzuweisen, und sizeof(person), um die Anzahl der benötigten Bytes zu erhalten.

// Allocate memory for new person
person *new_person = malloc(sizeof(person));

Als nächstes ist zu prüfen, ob noch Generationen zu erzeugen sind, d.h. ob generations > 1 ist.

Wenn generations > 1, dann gibt es weitere Generationen, die noch erstellt werden müssen. Wir haben in dem zur Verfügung gestellten Code bereits zwei neue Eltern, parent0 und parent1, durch rekursiven Aufruf von create_family erzeugt. Sie sollten sich in der Funktion create_family dann um das Setzen der Zeiger auf die Eltern der neu erstellten Person kümmern. Anschließend sollten Sie der neuen Person beide alleles zuweisen, indem Sie zufällig ein Allel von jedem Elternteil auswählen.

• Erinnern Sie sich, dass Sie die Pfeilnotation verwenden können, um über einen Zeiger auf eine Variable zuzugreifen. Wenn zum Beispiel p ein Zeiger auf eine Person ist, dann kann auf den Zeiger auf das erste Elternteil dieser Person mit p->parents[0] zugegriffen werden.
• Für die zufällige Zuweisung von Allelen ist die Funktion rand() nützlich (Hinweis: Der Eintrag zu rand() ist im Handbuch nicht entsprechend aufbereitet; Sie können für weitere Informationen auch den leichter zugänglichen Handbucheintrag zu random() lesen; einziger Unterschied neben dem Namen: Die Funktion gibt einen long statt einen int zurück). Diese Funktion gibt eine ganze Zahl zwischen 0 und RAND_MAX, oder 32767, zurück. Um eine Pseudo-Zufallszahl zu erzeugen, die entweder 0 oder 1 ist, können Sie den Ausdruck rand() % 2 verwenden.

// Create two new parents for current person by recursively calling create_family
person *parent0 = create_family(generations - 1);
person *parent1 = create_family(generations - 1);

// Set parent pointers for current person
new_person->parents[0] = parent0;
new_person->parents[1] = parent1;

// Randomly assign current person's alleles based on the alleles of their parents
new_person->alleles[0] = parent0->alleles[rand() % 2];
new_person->alleles[1] = parent1->alleles[rand() % 2];

Nehmen wir an, es gibt keine weiteren Generationen mehr zu simulieren. Das heißt, generations == 1. Wenn dies der Fall ist, gibt es keine Eltern für diese Person. Beide Elternteile der neuen Person sollten auf NULL gesetzt werden, und jedes allele sollte zufällig generiert werden.

// Set parent pointers to NULL
new_person->parents[0] = NULL;
new_person->parents[1] = NULL;

// Randomly assign alleles
new_person->alleles[0] = random_allele();
new_person->alleles[1] = random_allele();

Schließlich sollte Ihre Funktion einen Zeiger auf die neu erstellte person zurückgeben.

// Return newly created person
return new_person;

Die Funktion free_family sollte als Eingabe einen Zeiger auf eine person akzeptieren, Speicher für diese Person freigeben und dann rekursiv Speicher für alle ihre Vorfahren freigeben.

• Da es sich um eine rekursive Funktion handelt, sollten Sie zunächst den Basisfall behandeln. Ist die Funktionseingabe NULL, so gibt es nichts freizugeben, so dass die Funktion sofort returnen kann.
• Andernfalls sollten Sie beide Elternteile der Person rekursiv mit free freigeben, bevor Sie das Kind freigeben.

Achtung Spoiler: Der folgende Code zeigt Ihnen, wie Sie genau das umsetzen können!

// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
    // Handle base case
    if (p == NULL)
    {
        return;
    }

    // Free parents recursively
    free_family(p->parents[0]);
    free_family(p->parents[1]);

    // Free child
    free(p);
}