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

@CraigRodrigues CraigRodrigues 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