CS50 Problem Set 5#

1
// Simulate genetic inheritance of blood type
2
#define _DEFAULT_SOURCE
3
#include <stdbool.h>
4
#include <stdio.h>
5
#include <stdlib.h>
6
#include <time.h>
7

8
// Each person has two parents and two alleles
9
typedef struct person
10
{
11
    struct person *parents[2];
12
    char alleles[2];
13
} person;
14

15
const int GENERATIONS = 3;
16
const int INDENT_LENGTH = 4;
17

18
person *create_family(int generations);
19
void print_family(person *p, int generation);
20
void free_family(person *p);
21
char random_allele();
22

23
int main(void)
24
{
25
    // Seed random number generator
26
    srandom(time(0));
27

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

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

34
    // Free memory
35
    free_family(p);
36
}
37

38
// Create a new individual with `generations`
39
person *create_family(int generations)
40
{
41
    // TODO: Allocate memory for new person
42
    person *p = malloc(sizeof(person));
43

44
    // If there are still generations left to create
45
    if (generations > 1)
46
    {
47
        // Create two new parents for current person by recursively calling create_family
48
        person *parent0 = create_family(generations - 1);
49
        person *parent1 = create_family(generations - 1);
50

51
        // TODO: Set parent pointers for current person
52
        p->parents[0] = parent0;
53
        p->parents[1] = parent1;
54

55
        // TODO: Randomly assign current person's alleles based on the alleles of their parents
56
        p->alleles[0] = parent0->alleles[random() % 2];
57
        p->alleles[1] = parent1->alleles[random() % 2];
58
    }
59

60
    // If there are no generations left to create
61
    else
62
    {
63
        // TODO: Set parent pointers to NULL
64
        p->parents[0] = NULL;
65
        p->parents[1] = NULL;
66

67
        // TODO: Randomly assign alleles
68
        p->alleles[0] = random_allele();
69
        p->alleles[1] = random_allele();
70
    }
71

72
    // TODO: Return newly created person
73
    return p;
74

75
    return NULL;
76
}
77

78
// Free `p` and all ancestors of `p`.
79
void free_family(person *p)
80
{
81
    // TODO: Handle base case
82
    if (p == NULL)
83
    {
84
        return;
85
    }
86

87
    // TODO: Free parents recursively
88
    free_family(p->parents[0]);
89
    free_family(p->parents[1]);
90

91
    // TODO: Free child
92
    free(p);
93
}
94

95
// Print each family member and their alleles.
96
void print_family(person *p, int generation)
97
{
98
    // Handle base case
99
    if (p == NULL)
100
    {
101
        return;
102
    }
103

104
    // Print indentation
105
    for (int i = 0; i < generation * INDENT_LENGTH; i++)
106
    {
107
        printf(" ");
108
    }
109

110
    // Print person
111
    if (generation == 0)
112
    {
113
        printf("Child (Generation %i): blood type %c%c\n", generation, p->alleles[0],
114
               p->alleles[1]);
115
    }
116
    else if (generation == 1)
117
    {
118
        printf("Parent (Generation %i): blood type %c%c\n", generation, p->alleles[0],
119
               p->alleles[1]);
120
    }
121
    else
122
    {
123
        for (int i = 0; i < generation - 2; i++)
124
        {
125
            printf("Great-");
126
        }
127
        printf("Grandparent (Generation %i): blood type %c%c\n", generation, p->alleles[0],
128
               p->alleles[1]);
129
    }
130

131
    // Print parents of current generation
132
    print_family(p->parents[0], generation + 1);
133
    print_family(p->parents[1], generation + 1);
134
}
135

136
// Randomly chooses a blood type allele.
137
char random_allele()
138
{
139
    int r = random() % 3;
140
    if (r == 0)
141
    {
142
        return 'A';
143
    }
144
    else if (r == 1)
145
    {
146
        return 'B';
147
    }
148
    else
149
    {
150
        return 'O';
151
    }
152
}

1
// Implements a dictionary's functionality
2

3
#include <ctype.h>
4
#include <stdbool.h>
5
#include <stdio.h>
6
#include <stdlib.h>
7
#include <string.h>
8
#include <strings.h>
9

10
#include "dictionary.h"
11

12
// Represents a node in a hash table
13
typedef struct node
14
{
15
    char word[LENGTH + 1];
16
    struct node *next;
17
} node;
18

19
int word_counter = 0;
20

21
// TODO: Choose number of buckets in hash table
22
const unsigned int N = 26;
23

24
// Hash table
25
node *table[N];
26

27
// Returns true if word is in dictionary, else false
28
bool check(const char *word)
29
{
30
    // TODO
31
    // Hash the word to obtain its hash value
32
    int hash_value = hash(word);
33

34
    // Search the hash table at the location specified by the word’s hash value
35
    // Return "true" if the word is found
36
    node *cursor = table[hash_value];
37
    while (cursor != NULL)
38
    {
39
        if (strcasecmp(cursor->word, word) == 0)
40
        {
41
            return true;
42
        }
43
        else
44
        {
45
            cursor = cursor->next;
46
        }
47
    }
48

49
    return false;
50
}
51

52
// Hashes word to a number
53
unsigned int hash(const char *word)
54
{
55
    // TODO: Improve this hash function
56
    return toupper(word[0]) - 'A';
57
}
58

59
// Loads dictionary into memory, returning true if successful, else false
60
bool load(const char *dictionary)
61
{
62
    // TODO
63
    // Make sure there is no garbage values
64
    for (int i = 0; i < N; i++)
65
    {
66
        table[i] = NULL;
67
    }
68

69
    // Open the dictionary file
70
    FILE *dict = fopen(dictionary, "r");
71
    if (dict == NULL)
72
    {
73
        printf("The dictinary does not exist.\n");
74
        return false;
75
    }
76

77
    // Read strings from file one at a time
78
    char temp_word[LENGTH];
79

80
    while (fscanf(dict, "%s", temp_word) != EOF)
81
    {
82
        // Create space for a new hash table node
83
        node *new_word = malloc(sizeof(node));
84

85
        // Copy the word into the new node
86
        strcpy(new_word->word, temp_word);
87

88
        // Hash the word to obtain its hash value
89
        int hash_value = hash(temp_word);
90

91
        // Insert the new node into the hash table (using the index specified by its hash value)
92
        new_word->next = table[hash_value];
93
        table[hash_value] = new_word;
94
        word_counter += 1;
95
    }
96

97
    // close the dictinary file
98
    fclose(dict);
99

100
    return true;
101
}
102

103
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
104
unsigned int size(void)
105
{
106
    // TODO
107
    return word_counter;
108
}
109

110
// Unloads dictionary from memory, returning true if successful, else false
111
bool unload(void)
112
{
113
    // TODO
114
    for (int i = 0; i < N; i++)
115
    {
116
        node *tmp = table[i];
117
        node *cursor = table[i];
118

119
        while (cursor != NULL)
120
        {
121
            cursor = cursor->next;
122
            free(tmp);
123
            tmp = cursor;
124
        }
125
    }
126
    return true;
127
}