Speller: 課題
高速なスペルチェックのプログラムを書くという課題。
https://cs50.harvard.edu/x/2021/psets/5/speller/
Speller: 回答例
// Implements a dictionary's functionality
#include <stdbool.h>
#include "dictionary.h"
#include <stdio.h>
#include <cs50.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
//represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// no. of buckets in hash table
const unsigned int N = 26;
// initialise positive hash value using unsigned int
unsigned int hash_value;
// initialise (positive) hash table word count
unsigned int word_count;
// hash table
node *table[N];
// Hashes word to a number
unsigned int hash(const char *word)
{
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)
{
// Open dict
FILE *file = fopen(dictionary, "r");
// If file is not opened, return false
if (file == NULL)
{
return false;
}
// storage space for word
char word[LENGTH + 1];
// Scan dict for strings that are not the end of the file
while (fscanf(file, "%s", word) != EOF)
{
// Allocate memory for new node
node *n = malloc(sizeof(node));
// If malloc returns NULL, return false
if (n == NULL)
{
return false;
}
// Pointer to next node and word itself
strcpy(n->word, word);
// Hash the word to get hash value
hash_value = hash(word);
// Set new pointer
n->next = table[hash_value];
// Set head to new pointer
table[hash_value] = n;
// Increment word count
word_count++;
}
// Close file
fclose(file);
// If dict is loaded, return true
return true;
}
// Returns true if word is in dictionary else false
bool check(const char *word)
{
//hash the word to get hash value
hash_value = hash(word);
//access the linked list
node *cursor = table[hash_value];
//go through the linked list
while (cursor != NULL)
{
//check if the word matches
if (strcasecmp(word, cursor->word) == 0)
{
return true;
}
//move cursor to next node
cursor = cursor->next;
}
return false;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// Check if there are any words
if (word_count > 0)
{
// Return count
return word_count;
}
// Else
return 0;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
// Iterate through buckets
for (int i = 0; i < N; i++)
{
// Set cursor to this each bucket location
node *cursor = table[i];
// If cursor is not NULL, free
while (cursor)
{
// Create temp
node *tmp = cursor;
// Move cursor to next node
cursor = cursor->next;
// Free up temp
free(tmp);
}
// If cursor is NULL
if (i == N - 1 && cursor == NULL)
{
return true;
}
}
return false;
}
未希 諒
Related posts
About media
Ramps Blog は、ノマドによるノマドのためのブログです。日本、香港、シンガポール、タイ、台湾のノマド生活を通じて見えた景色、特に食、カルチャー、テクノロジー、ビジネス、アート、デザインなどについて発信しています。
Recent Posts
安曇野放牧豚を豪快にバンズに挟んだハンバーガーはスーパーナイス!|三六五+二(367)〈松本十帖〉 https://ramps.jp/restaurant/matsumoto-jujo-367-lunch-super-nice-burger/
絶品。
#ハンバーガー #旅行好きな人と繋がりたい #写真好きな人と繋がりたい #ランチ
「INUA」部門シェフによる宿泊客限定の朝食|三六五+二(367)〈松本十帖〉 https://ramps.jp/restaurant/matsumoto-jujo-367-breakfast/
朝食のコンセプトは「ヘルシー&コンシャス」。『ALPS BAKERY』で焼き上げたパンの他、野菜をたっぷりの朝食を堪能。
#旅行好きな人と繋がりたい
#旅行
#写真撮ってる人と繋がりたい
#グルメ旅
「INUA」の部門シェフによる薪火ダイニングのローカルガストロノミー|三六五+二(367)〈松本十帖〉
http://ramps.jp/restaurant/mat…
このレストランを目的に旅をする価値がある。
#ローカルガストロノミー
#noma
#発酵
#ホテルレストラン
#グルメ旅
#ホテル
【ホテル宿泊記】松本十帖|地域活性化の拠点を担うホテルのスイートルーム〈松本・浅間温泉〉 http://ramps.jp/hotel/matsumot…
松本十帖のスイートルームの全貌を紹介。ただ一言、最高だった!
#旅行好きな人と繋がりたい
#写真好きな人と繋がりたい
#写真で伝える私の世界
#ホテル
#旅行記