Created
January 26, 2023 05:19
-
-
Save Tomi-3-0/62841601b8eeaf8ade8c12915a941e96 to your computer and use it in GitHub Desktop.
My implementation of `dictionary.c` from CS50's speller week 5 problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Implements a dictionary's functionality | |
#include <ctype.h> | |
#include <stdbool.h> | |
#include <strings.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <stdio.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; | |
//count variable | |
int count = 0; | |
// Hash table | |
node *table[N]; | |
// Returns true if word is in dictionary, else false | |
bool check(const char *word) | |
{ | |
// TODO | |
//hash word to obatain a hash value | |
int hashed = hash(word); | |
//Access linked list at that index | |
node *n = table[hashed]; | |
if (n == NULL) | |
{ | |
return 1; | |
} | |
//Traverse linked list looking for new word | |
while (n != NULL) | |
{ | |
if (strcasecmp(n->word, word) == 0) | |
{ | |
return true; | |
} | |
n = n -> next; | |
} | |
return false; | |
} | |
// Hashes word to a number | |
unsigned int hash(const char *word) | |
{ | |
// TODO: Improve this hash function | |
unsigned int num = 0; | |
//loop through each word | |
for (int i = 0; i < strlen(word); i++) | |
{ | |
// num += toupper(word[i] - 'A'); | |
//capitalise each word and multiply by | |
num += toupper(word[i] * 26) * num; | |
} | |
num = num % N; | |
return num; | |
} | |
// Loads dictionary into memory, returning true if successful, else false | |
bool load(const char *dictionary) | |
{ | |
// TODO | |
//Open dictionary file | |
FILE *file = fopen(dictionary, "r"); | |
//check null | |
if (dictionary == NULL) | |
{ | |
printf("Could not open%s\n", dictionary); | |
return 1; | |
} | |
char buffer[LENGTH + 1]; | |
//read strings from file into buffer | |
while (fscanf(file, "%s", buffer) != EOF) | |
{ | |
//allocate space and create new node for each word | |
node *n = malloc(sizeof(node)); | |
//check for NULL | |
if (n == NULL) | |
{ | |
return 1; | |
} | |
//copy word into node using strcpy | |
strcpy(n->word, buffer); | |
n->next = NULL; | |
//Use the hash function to hash words | |
int hashed = hash(buffer); | |
//set node pointer to current head | |
n->next = table[hashed]; | |
//then set head to point to the new node | |
table[hashed] = n; | |
count++; | |
} | |
fclose(file); | |
return true; | |
} | |
// Returns number of words in dictionary if loaded, else 0 if not yet loaded | |
unsigned int size(void) | |
{ | |
// TODO | |
return count; | |
} | |
// Unloads dictionary from memory, returning true if successful, else false | |
bool unload(void) | |
{ | |
// TODO | |
//loop over hash tables | |
for (int i = 0; i < N; i++) | |
{ | |
//set cursor to first item in node | |
node *cursor = table[i]; | |
//keep moving cursor until you get to NULL | |
while(cursor != NULL) | |
{ | |
//assign temporary node | |
node *tmp = cursor; | |
cursor = cursor->next; | |
//free up memory | |
free(tmp); | |
} | |
if (cursor == NULL) | |
{ | |
if (i == N - 1) | |
{ | |
return true; | |
} | |
} | |
} | |
return false; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Declares a dictionary's functionality | |
#ifndef DICTIONARY_H | |
#define DICTIONARY_H | |
#include <stdbool.h> | |
// Maximum length for a word | |
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis) | |
#define LENGTH 45 | |
// Prototypes | |
bool check(const char *word); | |
unsigned int hash(const char *word); | |
bool load(const char *dictionary); | |
unsigned int size(void); | |
bool unload(void); | |
#endif // DICTIONARY_H |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Implements a spell-checker | |
#include <ctype.h> | |
#include <stdio.h> | |
#include <sys/resource.h> | |
#include <sys/time.h> | |
#include "dictionary.h" | |
// Undefine any definitions | |
#undef calculate | |
#undef getrusage | |
// Default dictionary | |
#define DICTIONARY "dictionaries/large" | |
// Prototype | |
double calculate(const struct rusage *b, const struct rusage *a); | |
int main(int argc, char *argv[]) | |
{ | |
// Check for correct number of args | |
if (argc != 2 && argc != 3) | |
{ | |
printf("Usage: ./speller [DICTIONARY] text\n"); | |
return 1; | |
} | |
// Structures for timing data | |
struct rusage before, after; | |
// Benchmarks | |
double time_load = 0.0, time_check = 0.0, time_size = 0.0, time_unload = 0.0; | |
// Determine dictionary to use | |
char *dictionary = (argc == 3) ? argv[1] : DICTIONARY; | |
// Load dictionary | |
getrusage(RUSAGE_SELF, &before); | |
bool loaded = load(dictionary); | |
getrusage(RUSAGE_SELF, &after); | |
// Exit if dictionary not loaded | |
if (!loaded) | |
{ | |
printf("Could not load %s.\n", dictionary); | |
return 1; | |
} | |
// Calculate time to load dictionary | |
time_load = calculate(&before, &after); | |
// Try to open text | |
char *text = (argc == 3) ? argv[2] : argv[1]; | |
FILE *file = fopen(text, "r"); | |
if (file == NULL) | |
{ | |
printf("Could not open %s.\n", text); | |
unload(); | |
return 1; | |
} | |
// Prepare to report misspellings | |
printf("\nMISSPELLED WORDS\n\n"); | |
// Prepare to spell-check | |
int index = 0, misspellings = 0, words = 0; | |
char word[LENGTH + 1]; | |
// Spell-check each word in text | |
char c; | |
while (fread(&c, sizeof(char), 1, file)) | |
{ | |
// Allow only alphabetical characters and apostrophes | |
if (isalpha(c) || (c == '\'' && index > 0)) | |
{ | |
// Append character to word | |
word[index] = c; | |
index++; | |
// Ignore alphabetical strings too long to be words | |
if (index > LENGTH) | |
{ | |
// Consume remainder of alphabetical string | |
while (fread(&c, sizeof(char), 1, file) && isalpha(c)); | |
// Prepare for new word | |
index = 0; | |
} | |
} | |
// Ignore words with numbers (like MS Word can) | |
else if (isdigit(c)) | |
{ | |
// Consume remainder of alphanumeric string | |
while (fread(&c, sizeof(char), 1, file) && isalnum(c)); | |
// Prepare for new word | |
index = 0; | |
} | |
// We must have found a whole word | |
else if (index > 0) | |
{ | |
// Terminate current word | |
word[index] = '\0'; | |
// Update counter | |
words++; | |
// Check word's spelling | |
getrusage(RUSAGE_SELF, &before); | |
bool misspelled = !check(word); | |
getrusage(RUSAGE_SELF, &after); | |
// Update benchmark | |
time_check += calculate(&before, &after); | |
// Print word if misspelled | |
if (misspelled) | |
{ | |
printf("%s\n", word); | |
misspellings++; | |
} | |
// Prepare for next word | |
index = 0; | |
} | |
} | |
// Check whether there was an error | |
if (ferror(file)) | |
{ | |
fclose(file); | |
printf("Error reading %s.\n", text); | |
unload(); | |
return 1; | |
} | |
// Close text | |
fclose(file); | |
// Determine dictionary's size | |
getrusage(RUSAGE_SELF, &before); | |
unsigned int n = size(); | |
getrusage(RUSAGE_SELF, &after); | |
// Calculate time to determine dictionary's size | |
time_size = calculate(&before, &after); | |
// Unload dictionary | |
getrusage(RUSAGE_SELF, &before); | |
bool unloaded = unload(); | |
getrusage(RUSAGE_SELF, &after); | |
// Abort if dictionary not unloaded | |
if (!unloaded) | |
{ | |
printf("Could not unload %s.\n", dictionary); | |
return 1; | |
} | |
// Calculate time to unload dictionary | |
time_unload = calculate(&before, &after); | |
// Report benchmarks | |
printf("\nWORDS MISSPELLED: %d\n", misspellings); | |
printf("WORDS IN DICTIONARY: %d\n", n); | |
printf("WORDS IN TEXT: %d\n", words); | |
printf("TIME IN load: %.2f\n", time_load); | |
printf("TIME IN check: %.2f\n", time_check); | |
printf("TIME IN size: %.2f\n", time_size); | |
printf("TIME IN unload: %.2f\n", time_unload); | |
printf("TIME IN TOTAL: %.2f\n\n", | |
time_load + time_check + time_size + time_unload); | |
// Success | |
return 0; | |
} | |
// Returns number of seconds between b and a | |
double calculate(const struct rusage *b, const struct rusage *a) | |
{ | |
if (b == NULL || a == NULL) | |
{ | |
return 0.0; | |
} | |
else | |
{ | |
return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) - | |
(b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) + | |
((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) - | |
(b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec))) | |
/ 1000000.0); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment