Skip to content

Instantly share code, notes, and snippets.

@tkansa
Created Aug 12, 2017
Embed
What would you like to do?
/**
* Implements a dictionary's functionality.
*/
#include <cs50.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "dictionary.h"
// the multiplier for the hash function
#define MULTIPLIER (37)
// node structure for hashtable to store dictionary
typedef struct sllist
{
//string word;
char* wrd;
struct sllist *next;
}
node;
// functions used
unsigned int hash(const char* s);
node* create(char* w);
node* insert(node* head, char* w);
bool search(node* head, const char* w);
void destroy(node* head);
// max number of linked list head pointers
const int HASH_MAX = 150000;
// the hashtable to put the dictionary in
node* hashTable [150000];
// the number of words in the dictionary
int wordCount = 0;
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char *word)
{
// hash the word
int hashTableNo = hash(word);
bool wordIsInDictionary = false;
if(hashTable[hashTableNo] == NULL)
{
return false;
}
else
{
// print to console to see what's stored in the variables
node* ptr = hashTable[hashTableNo];
printf("Check: The hash number: %i\n", hashTableNo);
printf("Check: The dictionary word: %s\n", ptr->wrd);
printf("Check: The pointer: %i\n", (int)hashTable[hashTableNo]);
printf("Check: The text word: %s\n", word);
wordIsInDictionary = search(ptr, word);
}
// TODO
return wordIsInDictionary;
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char *dictionary)
{
FILE *fp = fopen(dictionary, "r");
if (fp == NULL)
{
printf("Could not open %s.\n", dictionary);
unload();
return 1;
}
char word[LENGTH + 1];
while(fscanf(fp, "%s", word) != EOF)
{
// hash the word
int hashTableNo = hash(word);
if(hashTable[hashTableNo] == NULL)
{
hashTable[hashTableNo] = create(word);
}
else
{
hashTable[hashTableNo] = insert(hashTable[hashTableNo], word);
}
wordCount++;
// print to console to see what's stored in the variables
node* ptr = hashTable[hashTableNo];
while(ptr != NULL)
{
printf("Load: The hash number: %i\n", hashTableNo);
printf("Load: The dictionery word: %s\n", ptr->wrd);
printf("Load: The dictionery word: %s\n", hashTable[hashTableNo]->wrd);
printf("Load: The pointer: %i\n", (int)hashTable[hashTableNo]);
ptr = ptr->next;
}
}
return true;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
return wordCount;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
for(int i = 0; i < 150001; i++)
{
if(hashTable[i] != NULL)
{
destroy(hashTable[i]);
}
}
return true;
}
// hash function adapted from: http://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)HashTables.html?highlight=%28CategoryAlgorithmNotes%29
unsigned int hash(const char* s)
{
unsigned long h;
unsigned const char *us;
// cast s to an unsigned const char
// this ensures that elements of s will be treated as having values >= 0
us = (unsigned const char *) s;
h = 0;
while(*us != '\0')
{
h = h * MULTIPLIER + *us;
us++;
}
return h % HASH_MAX;
}
node* create(char* w)
{
// dynamically allocate space for a new node
node *ptr = malloc(sizeof(node));
//check to make sure we didn't run out of memory
// initialize the node's val field
ptr->wrd = w;
// initialize the node's next field (will be null for the first item added to the list)
ptr->next = NULL;
printf("Create: %s\n", ptr->wrd);
// return the pointer to the newly created sllnode
return ptr;
}
node* insert(node* head, char* w)
{
// dynamically allocate space for a new sllnode
node *ptr = malloc(sizeof(node));
//check to make sure we didn't run out of memory
// populate and insert the node at the beginning of the linked list
ptr->wrd = w;
ptr->next = head;
// return pointer to new head of list
return ptr;
}
bool search(node* head, const char* w)
{
node* ptr = head;
while(ptr != NULL)
{
if(ptr->wrd == w)
{
return true;
}
printf("Search: The checked loaded word: %s\n", ptr->wrd);
printf("Search: The checked word in the text: %s\n", w);
ptr = ptr->next;
}
return false;
}
void destroy(node* head)
{
if(head->next == NULL){
free(head);
return;
}
else
{
node* head2 = head->next;
free(head);
destroy(head2);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment