CS50 2023 - Week5 Data Structures
概要
Week5では、データ構造について学びます。
講義の主な内容は、抽象データ型、キュー、スタック、連結リスト、ツリー、バイナリーサーチツリー(二分探索木)、ハッシュテーブルです。
Lab 5
Inheritance
血液型の継承をシミュレートするプログラムを作成します。
人間の血液型は2つの対立遺伝子によって決定されます。対立遺伝子はA、B、Oの3つがあり、子供は親からランダムに対立遺伝子の1つを受け継ぎます。この遺伝をシミュレートして、3世代の家族の血液型を表示するようします。
以下は実際に私が提出したコードです。
// 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 *new_person = 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
new_person->parents[0] = parent0;
new_person->parents[1] = parent1;
// TODO: Randomly assign current person's alleles based on the alleles of their parents
new_person->alleles[0] = new_person->parents[0]->alleles[rand() % 2];
new_person->alleles[1] = new_person->parents[1]->alleles[rand() % 2];
}
// If there are no generations left to create
else
{
// TODO: Set parent pointers to NULL
new_person->parents[0] = NULL;
new_person->parents[1] = NULL;
// TODO: Randomly assign alleles
new_person->alleles[0] = random_allele();
new_person->alleles[1] = random_allele();
}
// TODO: Return newly created person
return new_person;
}
// 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';
}
}
Problem Set 5
Speller
高速なスペルチェックプログラムを作成します。
ここで言う高速とは、実行時間の短さを指します。
以下は実際に私が提出したコードです。
// Implements a dictionary's functionality
#include <cs50.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include "dictionary.h"
// represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
} node;
// TODO: Choose number of buckets in hash table
const unsigned int N = 26;
unsigned int hash_value;
unsigned int word_count;
// hash table
node *table[N];
// Hashes word to a number
unsigned int hash(const char *word)
{
// TODO: Improve this hash function
unsigned long hash = 5381;
int c;
while ((c = toupper(*word++)))
{
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
}
return hash % N;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// TODO
FILE *file = fopen(dictionary, "r");
if (file == NULL)
{
return false;
}
char word[LENGTH + 1];
while (fscanf(file, "%s", word) != EOF)
{
node *n = malloc(sizeof(node));
if (n == NULL)
{
return false;
}
strcpy(n->word, word);
hash_value = hash(word);
n->next = table[hash_value];
table[hash_value] = n;
word_count++;
}
fclose(file);
return true;
}
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
hash_value = hash(word);
node *cursor = table[hash_value];
while (cursor != NULL)
{
if (strcasecmp(word, cursor->word) == 0)
{
return true;
}
cursor = cursor->next;
}
return false;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// TODO
if (word_count > 0)
{
return word_count;
}
return 0;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
// TODO
for (int i = 0; i < N; i++)
{
node *cursor = table[i];
while (cursor)
{
node *tmp = cursor;
cursor = cursor->next;
free(tmp);
}
if (i == N - 1 && cursor == NULL)
{
return true;
}
}
return false;
}
さいごに
Week5は、Week2と同様に、課題の条件は比較的シンプルです。
課題のページを熟読し、Walkthroughの内容をよく理解することが鍵となります。
本題から大きく脱線しますが、日本では血液型占いや診断がポピュラーである一方、イギリスでは多くの人が自らの血液型を知らなかったります。アメリカではどうなのか、少し気になるところです。
この記事が気に入ったらサポートをしてみませんか?