Vererbung

Öffnen Sie VS CodeVisual Studio Code, der kostenlose Code-Editor von Microsoft, in dem Sie im Kurs programmieren. Glossar → entsprechend Ihrem Setup.

Öffnen Sie Ihr TerminalfensterFenster, in dem Sie dem Computer Befehle als Text eintippen statt zu klicken. In VS Code liegt es im unteren Bereich des Fensters. Glossar → und führen Sie dann cdWechselt das Verzeichnis: cd me geht in den Ordner me, cd .. eine Ebene nach oben, cd allein ins Homeverzeichnis. Glossar → aus. Die EingabeaufforderungDas Zeichen am Anfang der Zeile im Terminal, etwa $ oder me/ $. Es zeigt, dass das Terminal auf Ihren nächsten Befehl wartet. Steht davor ein Ordnername wie me/, befinden Sie sich gerade in diesem Ordner. Glossar → Ihres Terminalfensters sollte wie folgt aussehen:

$

Geben Sie dann

wget https://dev.inf.zone/download/exercises/08/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 wgetLädt eine Datei aus dem Internet in das aktuelle Verzeichnis herunter, im Kurs zum Beispiel das Aufgabenmaterial einer Übung. Glossar → 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.

Jede Person ist eine struct vom Typ person mit zwei Membern:

• parents: ein Array aus zwei Pointern auf die beiden Eltern (jeweils wieder eine person),
• alleles: ein Array aus zwei char (jeweils 'A', 'B' oder 'O').

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

main initialisiert zuerst den Zufallszahlengenerator („Seeding“):

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

srand legt fest, welche Folge von Pseudozufallszahlen spätere Aufrufe von rand() liefern. Weil time(0) die aktuelle Uhrzeit in Sekunden liefert, kommen bei jedem Lauf (in einer neuen Sekunde) andere Zahlen heraus. srand wird einmal vor dem ersten rand() aufgerufen – das erledigt das Codegerüst schon; Sie rufen danach nur noch rand() auf. rand() liefert eine ganze Zahl zwischen 0 und RAND_MAX, einer sehr großen Zahl (in der CS50-Umgebung 2147483647). Die nötige Bibliothek <stdlib.h> ist bereits eingebunden.

rand() steckt auch in der fertigen Funktion random_allele:

// 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?

Dann ruft main nacheinander drei Funktionen auf:

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

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

// Free memory
free_family(p);

• create_family legt die Familie an (GENERATIONS ist 3) und gibt einen Pointer auf das Kind zurück – Ihre Aufgabe.
• print_family gibt den Stammbaum aus – fertig.
• free_family gibt den mit malloc reservierten Speicher wieder frei – Ihre Aufgabe.

In create_family sind die beiden rekursiven Aufrufe für die Eltern schon vorgegeben; die Stellen, an denen Sie Code ergänzen, sind mit TODO markiert.

Warum Rekursion? Um die Allele einer Person zu bestimmen, brauchen Sie die Allele ihrer Eltern. Für diese brauchen Sie die Allele deren Eltern – und so weiter, bis zur ältesten Generation, die Sie simulieren. Wie Rekursion funktioniert, zeigt das Short Rekursion.

Reservieren Sie zuerst Speicher für eine neue Person. Erinnern Sie sich, dass malloc Speicher reserviert und sizeof(person) die Anzahl der benötigten Bytes liefert. Bekommt malloc keinen Speicher, gibt es NULL zurück; das sollten Sie abfangen.

// Allocate memory for new person
person *new_person = malloc(sizeof(person));
if (new_person == NULL)
{
    return NULL;
}

Prüfen Sie dann, ob noch Generationen zu erzeugen sind, also ob generations > 1 ist. In diesem Fall hat das Codegerüst schon zwei Eltern, parent0 und parent1, durch rekursive Aufrufe von create_family erzeugt. Setzen Sie die Pointer auf die Eltern und weisen Sie der neuen Person von jedem Elternteil zufällig ein Allel zu.

• Über einen Pointer greifen Sie mit der Pfeilnotation auf die Member einer struct zu (Strukturen): Ist p ein Pointer auf eine Person, dann ist p->parents[0] der Pointer auf ihren ersten Elternteil.
• rand() % 2 liefert zufällig 0 oder 1 – also einen gültigen Index für eines der beiden Allele. Mehr zu rand() steht im Handbuch unter rand; leichter lesbar ist der Eintrag zu random, einer Variante, die long statt int zurückgibt.

// 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];

Ist generations == 1, hat die Person keine Eltern mehr: Beide Pointer werden NULL, beide Allele zufällig.

// 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();

Zum Schluss gibt die Funktion den Pointer auf die neue Person zurück.

// Return newly created person
return new_person;

free_family bekommt einen Pointer auf eine person, gibt rekursiv den Speicher aller ihrer Vorfahren frei und dann den der Person selbst.

• Behandeln Sie zuerst den Basisfall: Ist p NULL, gibt es nichts freizugeben, und die Funktion kann sofort returnen.
• Andernfalls geben Sie rekursiv beide Eltern frei, bevor Sie das Kind freigeben. Umgekehrt ginge es nicht: Nach free(p) dürfen Sie p->parents nicht mehr lesen.

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);
}