I'm very puzzled my program seems to work correctly apart from one thing, when I run speller with large dictionary, the letter "s" is treated as a correctly-spelled word. I ran a test using the alphabet separated by spaces as my text to spell check, sure enough the program reported 23 mis-spelled words, with the 3 correct words being "a", "i" and "s".
My first thought was, words ending with ('s) were confusing my load function to store s as a valid word, however adding "cat's" to dictionaries small and running speller works just fine.
I used printf to print the address of node containing matching word whenever there was a match and sure enough the program reported "s" is stored in a node and returned an address in memory. Am I missing something? ascii code quirks?
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>
#include "dictionary.h"
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
// Global variables & functions
// Number of buckets in hash table
const unsigned int N = 17576;
unsigned int wordcount = 0;
// Hash table
node *table[N];
// Main functions
// Returns true if word is in dictionary else false
bool check(const char *word)
{
node *current_node;
node *node_temp;
char *wordlowercase = calloc(LENGTH + 1, sizeof(char));
for (int i = 0; i <= LENGTH; i++) // make lowercase copy of input string
{
if (word[i] == '\0')
{
break;
}
else
{
wordlowercase[i] = (word[i] | ' ');
}
}
unsigned int index_no = hash(wordlowercase); // generate hash bucket
if (table[index_no] == NULL) // no entry in hash table, non-valid word
{
free(wordlowercase);
return false;
}
if (strcasecmp(table[index_no]->word, wordlowercase) == 0) // first node match
{
free(wordlowercase);
return true;
}
current_node = table[index_no];
while (strcasecmp(current_node->word, wordlowercase) != 0) // Look at all nodes in linked list for match
{
if (current_node->next == NULL) // no more nodes, word is mis-spelled
{
free(wordlowercase);
return false;
}
node_temp = current_node->next; // move to next node, check again
current_node = node_temp;
}
printf("CORRECT SPELLING, input word (%s) matches word (%s) stored at node in linked list at address %p\n",wordlowercase, current_node->word, current_node);
free(wordlowercase);
return true;
}
// Hashes word to a number
unsigned int hash(const char *word) //djB2 hash function
{
unsigned int hash = 5381;
int c;
while ((c = *word++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash % N;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
FILE *open_dictionary;
open_dictionary = fopen(dictionary, "r"); // file pointer to dictionary
char current_character;
char *current_word = calloc(1, sizeof(char[45]));
node *nodetracker;
while (fgets(current_word, 45, open_dictionary) != NULL) // read each word from input dictionary
{
// replace '\n' with '\0'
int space_char = strcspn (current_word, "\n");
current_word[space_char] = '\0';
wordcount++;
long index_no = hash(current_word); // hash function
if (table[index_no] == NULL) // Hash table bucket unused
{
table[index_no] = calloc(1, sizeof(node));
strcpy(table[index_no]->word, current_word);
}
else if (table[index_no] != NULL) // hash table already occupied
{
nodetracker = calloc(1, sizeof(node));
strcpy (nodetracker->word, current_word);
nodetracker->next = table[index_no];
table[index_no] = nodetracker;
}
}
free(current_word);
return true;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
return wordcount;
return 0;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
node *node_temp = NULL;
node *node_tracker = NULL;
for (int i = 0; i < N - 1; i++)
{
if (table[i] == NULL)
{
continue;
}
node_tracker = table[i];
table[i] = NULL;
while (node_tracker->next != NULL)
{
node_temp = node_tracker->next;
free(node_tracker);
node_tracker = node_temp;
}
free(node_tracker);
}
return true;
}