/dictionary.c Secret
Last active
August 7, 2016 02:19
Star
You must be signed in to star a gist
dictionary.c - shared from CS50 IDE
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
/** | |
* dictionary.c | |
* | |
* Computer Science 50 | |
* Problem Set 5 | |
* | |
* Implements a dictionary's functionality. | |
*/ | |
#include <stdbool.h> | |
#include <ctype.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <strings.h> | |
#include "dictionary.h" | |
#define HASH_MAX 27 | |
typedef struct node | |
{ | |
char word[LENGTH + 1]; | |
struct node* next; | |
} | |
node; | |
/** | |
* Hash function | |
*/ | |
unsigned int hash(const char* str) | |
{ | |
int sum = 0; | |
for (int j = 0; str[j] != '\0'; j++) | |
sum += str[j]; | |
return sum % HASH_MAX; | |
} | |
// the hashtable | |
node* hashtable[HASH_MAX]; | |
// dictionary size | |
unsigned int dictionary_size = 0; | |
/** | |
* Returns true if word is in dictionary else false. | |
*/ | |
bool check(const char* word) | |
{ | |
// copies word into word2 because we can't change a const | |
int len = strlen(word); | |
// allocating memory for word2 | |
char* word2 = malloc(len * sizeof(char)); | |
// makes all of word2's characters lowercased | |
for (int i = 0; i < len; i++) | |
word2[i] = tolower(word[i]); | |
// getting bucket number | |
int bucket = hash(word2); | |
// declaring a traversal pointer pointing to the head of the linked list aka bucket | |
node* trav = hashtable[bucket]; | |
while (trav != NULL) | |
{ | |
// compare the two strings | |
if (strcmp(trav->word, word2) == 0) | |
return true; | |
//move to the next element | |
trav = trav->next; | |
// printf("trav->word: %s word2: %s\n", trav->word, word2); | |
} | |
return false; | |
} | |
/** | |
* Loads dictionary into memory. Returns true if successful else false. | |
*/ | |
bool load(const char* dictionary) | |
{ | |
// declaring a dictionary word | |
char dictionary_word[LENGTH + 1]; | |
// openging the file | |
FILE* file = fopen(dictionary, "r"); | |
if (file == NULL) | |
{ | |
printf("Could not open dictionary"); | |
return false; | |
} | |
while (fscanf(file, "%s\n", dictionary_word) != EOF) | |
{ | |
// hashing the word | |
int index = hash(dictionary_word); | |
// allocating memory for new node | |
node* new_node = malloc(sizeof(node)); | |
// checking if we ran out of memory | |
if (new_node == NULL) | |
{ | |
return false; | |
} | |
// checks if the element of the array is pointing to nothing | |
if (hashtable[index] == NULL) | |
{ | |
// pointing the array's elements to the new node we malloc'ed | |
hashtable[index] = new_node; | |
// makes the new node points to NULL | |
new_node->next = NULL; | |
} | |
// if it's pointing to something | |
else | |
{ | |
// inserting a new node at the start of the linked list | |
new_node->next = hashtable[index]; | |
// makes the new node the head of the linked list | |
hashtable[index] = new_node; | |
} | |
// putting the dictionary word into the new node | |
strcpy(new_node -> word, dictionary_word); | |
dictionary_size++; | |
} | |
fclose(file); | |
return true; | |
} | |
/** | |
* Returns number of words in dictionary if loaded else 0 if not yet loaded. | |
*/ | |
unsigned int size(void) | |
{ | |
return dictionary_size; | |
} | |
/** | |
* Unloads dictionary from memory. Returns true if successful else false. | |
*/ | |
bool unload(void) | |
{ | |
for (int i = 0; i < HASH_MAX; i++) | |
{ | |
node* cursor = hashtable[i]; | |
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