Created
September 8, 2016 00:10
-
-
Save CraigRodrigues/61b8e504e9855a9d156a5a17ab82c720 to your computer and use it in GitHub Desktop.
CS50 Problem Set 5 - Mispellings
This file contains hidden or 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
/** | |
* 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hash table implementation.