CS50 Week5: Problem Set, Speller

하버드 CS50 강의 5주차 Problem Set 과제 Speller 의 풀이 과정을 다룹니다.
해시 테이블을 이용해 맞춤법 검사기를 만드는 문제입니다.
C언어로 해시 테이블을 구현하며 해시 함수의 설계, 연결 리스트를 활용한 데이터 저장 방법 및 동적 메모리 할당을 연습합니다.

Task

문제 링크에서 자세한 내용을 확인할 수 있습니다.

프로그램 실행 예시

$ ./speller texts/lalaland.txt
MISSPELLED WORDS

[...]
AHHHHHHHHHHHHHHHHHHHHHHHHHHHT
[...]
Shangri
[...]
fianc
[...]
Sebastians
[...]

WORDS MISSPELLED:
WORDS IN DICTIONARY:
WORDS IN TEXT:
TIME IN load:
TIME IN check:
TIME IN size:
TIME IN unload:
TIME IN TOTAL:

코드는 템플릿이 주어져서 필요한 부분만 채우면 된다.

Code

해시 테이블을 구현해야한다.

check 함수

해시 테이블은 배열과 연결 리스트로 구현된다.
배열에서 단어를 찾지 못했을 경우 다음 노드로 이동한다.

마지막 노드까지 찾아도 없으면 false를 반환한다.

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

hash 함수

해시 함수는 마음대로 구현하면 된다.

일단은 간단하게 첫 글자를 기준으로 나누기로 한다.
그러므로 BUCKET_SIZE 는 26이다.

const unsigned int BUCKET_SIZE = 26;

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

더 나은 해시 함수를 만들어야 하는데, 일단은 구현에 치중하느라 안바꿨다.

load 함수

dictionary 파일을 읽고 단어를 해시 테이블에 저장한다.

malloc을 사용해서 메모리를 할당해야한다.

새 단어가 배열에 저장된 연결 리스트의 첫 노드가 된다.

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

    char current_word[LENGTH + 1];
    while (fscanf(inptr, "%s", current_word) == 1)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            unload();
            return false;
        }
        strcpy(n->word, current_word);
        int index = hash(current_word);
        n->next = table[index];
        table[index] = n;
    }

    fclose(inptr);
    return true;
}

주의할 점은 n->word = current_word; 이렇게 하면 오류가 난다.

current_word 는 load 함수 내에 선언된 포인터다. 지금 단어를 가르킬 뿐이다.
명시적으로 단어 내용을 복사해줘야 한다.

size 함수

테이블을 돌면서 단어 수를 새 주면 된다.

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    unsigned int dict_size = 0;
    for (int i = 0; i < BUCKET_SIZE; i++)
    {
        node *ptr = table[i];
        while (ptr != NULL)
        {
            dict_size++;
            ptr = ptr->next;
        }
    }
    return dict_size;
}

unload 함수

malloc으로 할당된 메모리를 해제해야 한다.

해제를 먼저 해버리면 연결된 다음 노드를 찾을 수 없음에 주의하자.

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