[CS50X] 2024 Week5 Data Structures Problem Set 5 (Inheritance, Speller)

 

 

Volume

문제 링크

https://cs50.harvard.edu/x/2024/psets/5/inheritance/

Inheritance - CS50x 2024

 

 

 

실제 코드 구현

// 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 *n = 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
        n->parents[0] = parent0;
        n->parents[1] = parent1;
        // TODO: Randomly assign current person's alleles based on the alleles of their parents
        int r = rand();
        n->alleles[0] = parent0->alleles[r % 2];
        n->alleles[1] = parent1->alleles[r % 2];
    }

    // If there are no generations left to create
    else
    {
        // TODO: Set parent pointers to NULL
        n->parents[0] = NULL;
        n->parents[1] = NULL;
        // TODO: Randomly assign alleles
        n->alleles[0] = random_allele();
        n->alleles[1] = random_allele();
    }

    // TODO: Return newly created person
    return n;
}

// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
    // TODO: Handle base case
    if (p == NULL)
    {
        return;
    }
    person *ptr = p;
    // TODO: Free parents recursively
    free_family(ptr->parents[0]);
    free_family(ptr->parents[1]);
    // TODO: Free child
    free(ptr);
}

// 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';
    }
}

 

 

후기

구조를 파악하는 것이 조금 어려웠지만 workthrough 과 주석을 참고해서 이해했다.

재귀를 통해 free 하는 부분에서 디버깅을 많이 했는데

재귀에 대한 이해가 부족할 뿐더러

언제 재귀를 쓰는게 이득이고 손해인지 판단을 아직 잘 못하는 것이 원인인듯 하다.

 

 

 

 

 

 

 

 

Speller

문제 링크

https://cs50.harvard.edu/x/2024/psets/5/speller/

Speller - CS50x 2024

 

 

 

실제 코드 구현

// Implements a dictionary's functionality
#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 = 260;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    for (node *ptr = table[hash(word)]; ptr != NULL; ptr = ptr->next)
    {
        if (strcasecmp(ptr->word, word) == 0)
        {
            return true;
        }
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    int length = strlen(word);
    if (length > 9)
    {
        length = 9;
    }
    int index = (toupper(word[0]) - 'A') * 10 + length;
    return index;
}

// Loads dictionary into memory, returning true if successful, else false
int counter = 0;
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);
        n->next = table[hash(word)];
        table[hash(word)] = n;
        counter++;
    }
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    return counter;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    for (int i = 0; i < N; i++)
    {
        node *ptr = table[i];
        while (ptr != NULL)
        {
            node *n = ptr->next;
            free(ptr);
            ptr = n;
        }
    }
    return true;
}

 

 

 

 

후기

cs50 문제 중에 파일이 가장 많았는데 

정작 구현해야할 파일은 1개 였고 기능도 어렵지 않았다.

해쉬테이블과 해쉬 함수 등을 연결리스트 통해 구현하면 됐다.

핵심 중 하나는 시간에 관한 것이였다.

문제에서 공간보다는 시간을 줄이는 것에 중점을 두고 staff solution 과 비교를 원했다.

내 코든 직원 코드보다 1.5배 이상 느리다.

그 이유는 해쉬 테이블을 260 크기로 사용하고 있는데

나는 해쉬 함수를 문자열의 길이와 첫번째 문자로 풀었다.

첫번째 알파벳만 이용한 것 (크기 26) 보다 빠르다.

물론 메모리 공간과 속도에는 상충 관계가 존재하고 

더 큰 크기의 해쉬테이블을 사용한다면 더 빠른 속도를 기대할 수 있을 것 이다.