Created
October 8, 2018 12:29
-
-
Save choaimeloo/fa37314cc4f278f284a10fbc48cca3b1 to your computer and use it in GitHub Desktop.
cs50 pset5: Speller
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 <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <strings.h> | |
#include "dictionary.h" | |
#define HASHTABLE_SIZE 10000 | |
// Defines struct for a node | |
typedef struct node | |
{ | |
char word[LENGTH + 1]; | |
struct node *next; | |
} | |
node; | |
node *hashtable[HASHTABLE_SIZE]; | |
// Hashes the word (hash function posted on reddit by delipity) | |
// The word you want to hash is contained within new node, arrow, word. | |
// Hashing that will give you the index. Then you insert word into linked list. | |
int hash_index(char *hash_this) | |
{ | |
unsigned int hash = 0; | |
for (int i = 0, n = strlen(hash_this); i < n; i++) | |
{ | |
hash = (hash << 2) ^ hash_this[i]; | |
} | |
return hash % HASHTABLE_SIZE; | |
} | |
// Initializes counter for words in dictionary | |
int word_count = 0; | |
// Loads dictionary into memory, returning true if successful else false | |
bool load(const char *dictionary) | |
{ | |
// Opens dictionary | |
FILE *file = fopen(dictionary, "r"); | |
if (file == NULL) | |
{ | |
return false; | |
} | |
// Scans dictionary word by word (populating hash table with nodes containing words found in dictionary) | |
char word[LENGTH + 1]; | |
while (fscanf(file, "%s", word) != EOF) | |
{ | |
// Mallocs a node for each new word (i.e., creates node pointers) | |
node *new_node = malloc(sizeof(node)); | |
// Checks if malloc succeeded, returns false if not | |
if (new_node == NULL) | |
{ | |
unload(); | |
return false; | |
} | |
// Calculates index for insertion into hashtable | |
int h = hash_index(word); | |
// Copies word into node if malloc succeeds | |
strcpy(new_node->word, word); | |
// Inserts word into list (at the beginning & without losing any links) | |
node *head = malloc(sizeof(node)); | |
head = hashtable[h]; | |
new_node->next = head; | |
// If bucket is empty, insert the first node | |
if (head == NULL) | |
{ | |
head = new_node; | |
word_count++; | |
} | |
else | |
{ | |
new_node->next = head; | |
head = new_node; | |
word_count++; | |
} | |
} | |
fclose(file); | |
return true; | |
} | |
// Returns true if word is in dictionary else false | |
bool check(const char *word) | |
{ | |
// Creates lowercase copy of word on which hash function can be performed | |
int n = strlen(word); | |
char word_copy[LENGTH + 1]; | |
for (int i = 0; i < n; i++) | |
{ | |
word_copy[i] = tolower(word[i]); | |
} | |
// Initializes index for hashed word | |
int h = hash_index(word_copy); | |
// Mallocs a node for the head of a linked list | |
node *head = malloc(sizeof(head)); | |
// Sets cursor to point to same location as head | |
node *cursor = head; | |
// Sets head to point to an element in the hashtable array | |
head = hashtable[h]; | |
// if the word exists, you should be able to find in dictionary data structure | |
// check for word by asking, which bucket would word be in? hashtable[hash(word)] | |
// While cursor does not point to NULL, search dictionary for word | |
while (cursor != NULL) | |
{ | |
// if strcasecmp returns true, then word has been found | |
if (strcasecmp(cursor->word, word_copy) == 0) | |
{ | |
return true; | |
} | |
// else word has not yet been found, advance cursor | |
else | |
{ | |
cursor = cursor->next; | |
} | |
} | |
// cursor has reached end of list and word has not been found in dictionary so it must be misspelled | |
return false; | |
} | |
// Returns number of words in dictionary if loaded else 0 if not yet loaded | |
unsigned int size(void) | |
{ | |
return word_count; | |
} | |
// Unloads dictionary from memory, returning true if successful else false | |
bool unload(void) | |
{ | |
node *head = malloc(sizeof(node)); | |
node *cursor = head; | |
// freeing linked lists | |
while (cursor != NULL) | |
{ | |
node *temp = cursor; | |
cursor = cursor->next; | |
free(temp); | |
} | |
return true; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment