Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
CS50 Problem Set 5 - Mispellings
/**
* dictionary.c
*
* Computer Science 50
* Problem Set 5
*
* Implements a dictionary's functionality.
*/
#include <stdbool.h>
#include "dictionary.h"
// global variables
struct node* hashtable[SIZE];
int dicSize = 0;
char word[LENGTH +1];
void Push(struct node** headRef, const char* word) {
struct node* newNode = malloc(sizeof(struct node));
strcpy(newNode->word, word);
if (*headRef == NULL)
*headRef = newNode;
else
{
newNode->next = *headRef;
*headRef = newNode;
}
}
void PrintList(struct node* head) {
struct node* current = head;
while (current != NULL) {
printf("%s ", current->word);
current = current->next;
}
printf("\n");
}
void DeleteList (struct node** headRef) {
struct node* current = *headRef;
struct node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
*headRef = NULL;
}
/**
* Hash function. 2nd one found here: https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9nlkn
*
* 1st one found here: http://codereview.stackexchange.com/questions/85556/simple-string-hashing-algorithm-implementation
*
*/
/**
int hash(char* word) {
unsigned int hash = 0;
while (*word)
hash = (hash * 10) + *word++ - '0';
return hash % SIZE;
}
*/
int hash(char* word) {
unsigned int hash = 0;
for (int i = 0, n = strlen(word); i < n; i++)
hash = (hash << 2) ^ word[i];
return hash % SIZE;
}
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
// convert word to lowercase since all words in dictionary are lowercase
int len = strlen(word);
char tempWord[len+1];
strcpy(tempWord, word);
for (int i = 0; i < strlen(tempWord); i++) {
if (tempWord[i] != '\'')
tempWord[i] = tolower(tempWord[i]);
}
// get the hash value of the passed in word
int index = hash(tempWord);
// go to that index and search for the word
struct node* current = hashtable[index];
// if word is found return true
while (current != NULL) {
if (strcmp(current->word, tempWord) != 0) {
current = current->next;
}
else {
return true;
}
}
return false;
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char* dictionary)
{
// open the dictionary
FILE* dic = fopen(dictionary, "r");
if (dic == NULL)
return false;
// scan through the dictionary word by word
while (fscanf(dic, "%s\n", word)!= EOF)
{
dicSize++;
int index = hash(word);
Push(&hashtable[index], word);
}
fclose(dic); // close the dictionary file
return true;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
return dicSize;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
// iterate through entire SIZE of the hashtable array
for (int i = 0; i < SIZE; i++) {
if (hashtable[i] != NULL) // if something is there then delete the entire list there
DeleteList(&hashtable[i]);
}
return true;
}
@CraigRodrigues

This comment has been minimized.

Copy link
Owner Author

commented Sep 8, 2016

Hash table implementation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.