Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
cs50 pset5: Speller
// 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