(2022年) CS50 week5

其實之前就已經修完 CS50 了，不過因應 2022 年將課堂作業的系統
從 c9.io 換到 github codespace + vscode 整合
打算來重溫一下裡面的作業，並暖身一下 C 語言的手感

由於已經有許多前輩分享課程與作業的心得
加上官網教材的投影片、重點筆記、教學影片都非常完整
故不再做詳細的紀錄，專注在作業 (Lab, Problem sets) 上面

https://cs50.harvard.edu/x/2022/weeks/5/

Lab5： Inheritance

(點擊展開) 符合 style50 風格的程式碼

// 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)
{
    // Allocate memory for new person
    person *p = malloc(sizeof(person));
    if (p == NULL)
    {
        return NULL;
    }

    // Generation with parent data
    if (generations > 1)
    {
        // Recursively create blood type histories for parents
        p->parents[0] = create_family(generations - 1);
        p->parents[1] = create_family(generations - 1);

        // Randomly assign child alleles based on parents
        p->alleles[0] = p->parents[0]->alleles[rand() % 2];
        p->alleles[1] = p->parents[1]->alleles[rand() % 2];
    }

    // Generation without parent data
    else
    {
        // Set parent pointers to NULL
        p->parents[0] = NULL;
        p->parents[1] = NULL;

        // Randomly assign alleles
        p->alleles[0] = random_allele();
        p->alleles[1] = random_allele();
    }

    // Return newly created person
    return p;
}

// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
    // Handle base case
    if (p == NULL)
    {
        return;
    }

    // Free parents
    free_family(p->parents[0]);
    free_family(p->parents[1]);

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

–

(點擊展開) 個人覺得比較好讀的程式碼風格

// 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)
{
    // Allocate memory for new person
    person *p = malloc(sizeof(person));
    if (p == NULL)
        return NULL;

    // Generation with parent data
    if (generations > 1) {
        // Recursively create blood type histories for parents
        p->parents[0] = create_family(generations - 1);
        p->parents[1] = create_family(generations - 1);

        // Randomly assign child alleles based on parents
        p->alleles[0] = p->parents[0]->alleles[rand() % 2];
        p->alleles[1] = p->parents[1]->alleles[rand() % 2];
    }

    // Generation without parent data
    else {
        // Set parent pointers to NULL
        p->parents[0] = NULL;
        p->parents[1] = NULL;

        // Randomly assign alleles
        p->alleles[0] = random_allele();
        p->alleles[1] = random_allele();
    }

    // Return newly created person
    return p;
}

// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
    // Handle base case
    if (p == NULL)
        return;

    // Free parents
    free_family(p->parents[0]);
    free_family(p->parents[1]);

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

–

執行

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

驗證

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

作業： Speller

(點擊展開) 符合 style50 風格的程式碼

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <strings.h>
#include <stdio.h>
#include <cs50.h>

#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = 676; // 26 * 26 (aa to zz)
int words_size = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // get index by hashed
    int dictionary_index = hash(word);
    // get first node of table[dictionary_index]
    node *cursor = table[dictionary_index];

    while (cursor != NULL)
    {
        // compare lowered string
        if (strcasecmp(cursor->word, word) == 0)
        {
            return true;
        }

        // if not found => next node
        else
        {
            cursor = cursor->next;
        }
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // let its ASCII number to multiply
    // then % N (676)
    // means result will be 0 ~ 675
    return (tolower(word[0]) * tolower(word[1])) % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // load file data
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }

    // define basic variable: word
    char word[LENGTH + 1];

    // create hash table
    // scan each string and record value to variable: word
    // EOF means end of file
    while (fscanf(file, "%s", word) != EOF)
    {
        // create a memory block for dn (dictionary node)
        node *dn = malloc(sizeof(node));
        if (dn == NULL)
        {
            return false;
        }

        strcpy(dn->word, word); // copy word value to (*db).word
        dn->next = NULL;        // default is NULL

        // get index by hashed
        int dictionary_index = hash(word);
        // set hash table
        if (table[dictionary_index] == NULL)
        {
            // first node of table[dictionary_index]
            table[dictionary_index] = dn;
        }
        else
        {
            // swap node's linked:
            //    old: table[dictionary_index]
            //    new: dn

            // set (*new).next                     is old (from NULL)
            // set current table[dictionary_index] is dn
            dn->next = table[dictionary_index];
            table[dictionary_index] = dn;
        }

        // final: plus words_size
        words_size++;
    }

    // when finish, close fopen
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // counted in function: load()
    return words_size;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *cursor = table[i];
        node *current_node = table[i];

        // do recursion for free all memory of nodes
        while (cursor != NULL)
        {
            // replace cursor to next node
            cursor = cursor->next;

            // relase memory and set next node of should release
            free(current_node);
            current_node = cursor;
        }
    }

    return true;
}

–

(點擊展開) 個人覺得比較好讀的程式碼風格

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <strings.h>
#include <stdio.h>
#include <cs50.h>

#include "dictionary.h"

// Represents a node in a hash table
typedef struct node {
    char word[LENGTH + 1];
    struct node *next;
} node;

// Number of buckets in hash table
const unsigned int N = 676; // 26 * 26 (aa to zz)
int words_size = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // get index by hashed
    int dictionary_index = hash(word);
    // get first node of table[dictionary_index]
    node *cursor = table[dictionary_index];

    while (cursor != NULL) {
        // compare lowered string
        if (strcasecmp(cursor->word, word) == 0)
            return true;

        // if not found => next node
        else
            cursor = cursor->next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // let its ASCII number to multiply
    // then % N (676)
    // means result will be 0 ~ 675
    return (tolower(word[0]) * tolower(word[1])) % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // load file data
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
        return false;

    // define basic variable: word
    char word[LENGTH + 1];

    // create hash table
    // scan each string and record value to variable: word
    // EOF means end of file
    while (fscanf(file, "%s", word) != EOF) {
        // create a memory block for dn (dictionary node)
        node *dn = malloc(sizeof(node));
        if (dn == NULL)
            return false;

        strcpy(dn->word, word); // copy word value to (*db).word
        dn->next = NULL;        // default is NULL

        // get index by hashed
        int dictionary_index = hash(word);
        // set hash table
        if (table[dictionary_index] == NULL) {
            // first node of table[dictionary_index]
            table[dictionary_index] = dn;
        }
        else {
            // swap node's linked:
            //    old: table[dictionary_index]
            //    new: dn

            // set (*new).next                     is old (from NULL)
            // set current table[dictionary_index] is dn
            dn->next = table[dictionary_index];
            table[dictionary_index] = dn;
        }

        // final: plus words_size
        words_size++;
    }

    // when finish, close fopen
    fclose(file);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // counted in function: load()
    return words_size;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for (int i = 0; i < N; i++) {
        node *cursor = table[i];
        node *current_node = table[i];

        // do recursion for free all memory of nodes
        while (cursor != NULL) {
            // replace cursor to next node
            cursor = cursor->next;

            // relase memory and set next node of should release
            free(current_node);
            current_node = cursor;
        }
    }

    return true;
}

–

執行

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

…

驗證

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

(2022年) CS50 week5

Lab5： Inheritance

作業： Speller

Read more

(2022年) CS50 week7

(2022年) CS50 week6

(2022年) CS50 week4

(2022年) CS50 week3