Skip to content

Instantly share code, notes, and snippets.

/dictionary.c Secret

Last active August 7, 2016 02:19
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save anonymous/9dcb901f2007d09ae1c9c4fa934f13df to your computer and use it in GitHub Desktop.
dictionary.c - shared from CS50 IDE
/**
* 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