So I'd like if someone could tell me if my understanding of the Inheritance problem from Week 5 is correct or not.
// Simulate genetic inheritance of blood type
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Each person has two parents and two alleles
typedef struct person
{
struct person *parents[2];
char alleles[2];
}
person;
const int GENERATIONS = 3;
const int INDENT_LENGTH = 4;
person *create_family(int generations);
void print_family(person *p, int generation);
void free_family(person *p);
char random_allele();
int main(void)
{
// Seed random number generator
srand(time(0));
// Create a new family with three generations
person *p = create_family(GENERATIONS);
// Print family tree of blood types
print_family(p, 0);
// Free memory
free_family(p);
}
// Create a new individual with `generations`
person *create_family(int generations)
{
// TODO: Allocate memory for new person
person *p = malloc(sizeof(person));
// If there are still generations left to create
if (generations > 1)
{
// Create two new parents for current person by recursively calling create_family
person *parent0 = create_family(generations - 1);
person *parent1 = create_family(generations - 1);
// TODO: Set parent pointers for current person
p->parents[0] = parent0;
p->parents[1] = parent1;
// TODO: Randomly assign current person's alleles based on the alleles of their parents
p->alleles[0] = parent0->alleles[rand() % 2];
p->alleles[1] = parent1->alleles[rand() % 2];
}
// If there are no generations left to create
else
{
// TODO: Set parent pointers to NULL
p->parents[0] = NULL;
p->parents[1] = NULL;
// TODO: Randomly assign alleles
p->alleles[0] = random_allele();
p->alleles[1] = random_allele();
}
// TODO: Return newly created person
return p;
}
// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
// TODO: Handle base case
if (p == NULL)
{
return;
}
// TODO: Free parents recursively
free_family(p->parents[0]);
free_family(p->parents[1]);
// TODO: Free child
free(p);
}
// Print each family member and their alleles.
void print_family(person *p, int generation)
{
// Handle base case
if (p == NULL)
{
return;
}
// Print indentation
for (int i = 0; i < generation * INDENT_LENGTH; i++)
{
printf(" ");
}
// Print person
if (generation == 0)
{
printf("Child (Generation %i): blood type %c%c\n", generation, p->alleles[0], p->alleles[1]);
}
else if (generation == 1)
{
printf("Parent (Generation %i): blood type %c%c\n", generation, p->alleles[0], p->alleles[1]);
}
else
{
for (int i = 0; i < generation - 2; i++)
{
printf("Great-");
}
printf("Grandparent (Generation %i): blood type %c%c\n", generation, p->alleles[0], p->alleles[1]);
}
// Print parents of current generation
print_family(p->parents[0], generation + 1);
print_family(p->parents[1], generation + 1);
}
// 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';
}
}
So we start by allocating space for the individual. My question here is...how much space does the computer allocate? The person structure has 2 parent persons, which will have their own parents and so on and so forth. So how does the computer know how much space to allocate?
After allocating space for the person, we start recursively calling the function for each generation. So let's name them as the individual, P[A], P[B], GP[A] and GP[B], where P -> Parent, and GP -> Grandparent and A and B mean first and second respectively.
So we first go into the loop for P[A]. We ask the computer to allocate space again. But we use the same variable p to point to a new block of memory for P[A]. Won't that result in the block of memory we allocated for the individual being lost? Then we call the function for the grandparents of P[A], i.e. GP[A] and GP[B]. We first go into GP[A], and since generation is < 1, we set its parent pointers to null and give it random alleles. Same for GP[B].
After both calls of the function are done for P[A], we then set the parents array of P[A] to be equal to the pointers, parent0 and parent1, which point to GP[A] and GP[B] respectively.
Then we do the same for P[B].
Then we do the same for the individual and we move on to the next function, free_family.
In free_family, do we end up calling the function for the parents of each grandparent as well? Cuz then it makes sense that the function returns and we end up freeing the child, which in this case is the grandparent. And then we do the same for each grandparent, which results in the parents being freed. And then finally we free the individual.
So is my explanation correct. Do you have any explanations for my questions that I have highlighted in bold? Would greatly appreciate any advice.
So we start by allocating space for the individual. My question here is...how much space does the computer allocate? The person structure has 2 parent persons, which will have their own parents and so on and so forth. So how does the computer know how much space to allocate?
You are mixing up the semantic interpretation of your data types with their actual structure, and perhaps also getting confused about indirection. Like every C struct (that does not have a flexible array member), your struct person has a fixed, definite size. You can, for example, determine this size via the sizeof operator. It will be at least large enough to accommodate all the members, which are
struct personcharOn a typical implementation featuring 64-bit pointers, I would expect such a structure to be 24 bytes in size -- 16 for the two pointers, two for the two chars, and 6 bytes of padding for alignment purposes. Implementations may choose differently, but whatever that size is, that's how many bytes malloc(sizeof(person)) will attempt to allocate.
And note well that one struct person does not contain others. C does not permit a structure type to directly or indirectly contain sub-objects of its own type. But it does permit structures to contain pointers to other objects of the same type, which is what you have.
So we first go into the loop for P[A]. We ask the computer to allocate space again. But we use the same variable p to point to a new block of memory for P[A]. Won't that result in the block of memory we allocated for the individual being lost? Then we call the function for the grandparents of P[A], i.e. GP[A] and GP[B]. We first go into GP[A], and since generation is < 1, we set its parent pointers to null and give it random alleles. Same for GP[B].
I don't see any such loop in the program. Unless the question is hypothetical (in which case the answer depends on many details that have not been presented), I think you must be talking about the create_family function, which does not loop, but does recurse.
Here you need to understand that among the key properties of functions is that each execution of any function gets its own set of non-static local variables. Including when it calls itself recursively. So the p in the initial call to create_family is a different variable from the p used in each of its recursive calls to create_family, and each of those calls' own recursive calls get their own ps, etc.. These are all independent; one does not clobber another.
In free_family, do we end up calling the function for the parents of each grandparent as well? Cuz then it makes sense that the function returns and we end up freeing the child, which in this case is the grandparent. And then we do the same for each grandparent, which results in the parents being freed. And then finally we free the individual.
Yes. free_family frees the parents of each person by recursively calling itself. So in those recursive calls, it frees the parents' parents. And in those calls, the parents' parents' parents, up to the point in each branch where the person's parents are not recorded (as indicated by null pointers).