I've looked through everyone with the same problem, the common answer seems to be lower-case issues in the hash function or freeing pointers before you are actually done using them. I have tried playing around with everything I can think of in this code, but still get almost all my words as misspelled. I still believe the problem to be within my check/hash-function, as my load seemed to work fine when I checked that. Anyone have any pointers?
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#include "dictionary.h"
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// Number of buckets in hash table
const unsigned int N = 676; // for now looking at two first letters 26*26
// Hash table
node *table[N];
// Dictionary word-counter
int dictionary_word_count = 0;
// Returns true if word is in dictionary else false
bool check(const char *word)
{
int n = strlen(word);
char copy_word[n + 1];
strcpy(copy_word, word);
char lwrcase_word[n + 1];
for (int i = 0; i < n; i++)
{
lwrcase_word[i] = tolower(copy_word[i]);
}
int index = hash(lwrcase_word); // hash word to find linked list's index
node *trav = malloc(sizeof(node)); // create a node that can traverse from the start through linked list, looking for matching word.
if (trav == NULL)
{
return 1;
printf("Not enough memory");
}
trav->next = table[index];
while(trav->next != NULL)
{
if (strcmp(trav->word, lwrcase_word) == 0) // if match found, word is not misspelled, function returns true
{
return true;
}
trav = trav->next; // else keep looking for a match
}
return false;
}
// Hashes word to a number
// hash-function credit to http://www.cse.yorku.ca/~oz/hash.html
unsigned int hash(const char *word)
{
unsigned long hash = 5381;
int c;
while ((c = *word++)) // could be - while ( assign(&c, *word++) != '\0' )
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash % N; // to keep values within hashtable
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
for(int i = 0; i < N; i++)
{
table[i] = NULL; // initializing hashtable pointers, to avoid garbage values
}
char word[LENGTH + 1]; // create string for word to be read into
FILE *file = fopen(dictionary, "r"); // open dictionary
if (file == NULL)
{
printf("File could not be opened\n");
return false;
}
while (fscanf(file, "%s", word) != EOF) // read one string at a time from dictionary into word array
{
node *n = malloc(sizeof(node)); // allocate memory for new node
if (n == NULL)
{
printf("Not enough memory\n");
return false;
}
int index = hash(n->word); // find index node will be placed at with hashfunction
strcpy(n->word, word); // the dictionary word will be put into node
dictionary_word_count++; // counting words
if (table[index] != NULL) // if there is a collision
{
n->next = table[index]; // FIRST point node to the old head index was pointing at
table[index] = n; // then point index at node, now new head
}
else
{
table[index] = n; // if index is empty, node is head
n->next = NULL;
}
}
return true;
fclose(file);
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
return dictionary_word_count;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
for(int i = 0; i < N; i++)
{
node *trav = malloc(sizeof(node)); // create two travellers that can go over hashtable
node *tmp = malloc(sizeof(node));
if (trav == NULL || tmp == NULL)
{
printf ("Memory is full!");
return false;
}
trav = table[i]; // They will both start at index of linked list
tmp = table[i];
while(trav != NULL) // trav will go through list until NULL
{ // tmp will free node after trav has moved on, then proceed to be in travs place
trav = trav->next;
free(tmp);
tmp = trav;
}
}
return true;
}
