Initial Problem
I have cleaned up my code but I still can't seem to solve the problem of my speller.c returning all the words in a text file as misspelled. Checking my solution against the staff's with austinpowers.txt, I get the following comparison:
I am guessing the fault lies in check, that somehow word_dic in the hashtable data structure is never the same as word_copy from the text files. I've spent days trying to figure it out. ): Any help would be greatly appreciated.
Below is my code for dictionary.c
#include "dictionary.h"
// create struct for node (value-pointer pair) for words
typedef struct node
{
char word[LENGTH + 1]; // (max) LENGTH defined as 45 in dictionary.h
struct node *next; // point to next node
}
node;
// create array of pointer-to-nodes
node *hashtable[HASHTABLE_SIZE];
// global variable for tracking dictionary size
unsigned int word_count = 0;
// global boolean for tracking load/unload dictionary operations (need to connect load and unload dictionary operations for speller.c)
bool loaded = false; // when loaded = false, it means dictionary is unloaded from memory.
// hash function credit to reddit user, delipity
// reference:
https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/
int hash_it(char *needs_hashing) // declare the function, hash_it
{
unsigned int hash = 0;
for (int i = 0, n = strlen(needs_hashing); i < n; i++)
{
hash = (hash << 2) ^ needs_hashing[i];
}
return hash % HASHTABLE_SIZE;
}
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char *word)
{
// create array to store a copy of word
int length = strlen(word) + 1;
char word_copy[length];
// convert word to lowercase and store it in word_copy
for ( int i = 0; i < length; i++)
{
word_copy[i] = tolower(word[i]);
}
// add null-terminator to mark end of string since strlen doesn't include the NULL character to its length
word_copy[length] = '\0';
// obtain index from hash function for copy of word in text
// Note: The hash value is fully determined by the data being hashed. The hash value is just the sum of all the input characters. So make sure that word_copy and word_dic are the same words, their strings have to similar in all respects, e.g. they both contain '\0' and are of the same length.
int h = hash_it(word_copy);
// create traversal pointer and assign it to first node/element
node *traversal_pointer = hashtable[h];
// check until end of linked list
while ( traversal_pointer != NULL)
{
if (strcmp(traversal_pointer->word, word_copy) == 0)
{
// word is in dictionary
return true;
}
else
{
// check next node
traversal_pointer = traversal_pointer->next;
}
}
return false;
// check the input with the last word in each bucket, i.e. when traversal_pointer == NULL
if (traversal_pointer == NULL)
{
if (strcmp(traversal_pointer->word, word_copy) == 0)
{
// word is in dictionary
return true;
}
else
{
return false;
}
}
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char *dictionary)
{
// make all hash table elements null
for (int i = 0; i < HASHTABLE_SIZE; i++)
{
hashtable[i] = NULL;
}
// open dictionary
FILE *fp = fopen(dictionary, "r");
if ( fp == NULL ) // if pointer to file is NULL
{
printf("Could not open dictionary.\n");
return false;
}
while (!feof(fp)) // while file can be opened
{
// array to hold the word from dictionary, + 1 to include '\0'
// create array to store a copy of word. As fscanf always stores a null character in addition to the characters matched (so the argument array must have room for at least width+1 characters)
char word_dic[LENGTH + 1];
// read words from file and store word to a new_node
fscanf(fp, "%s", word_dic);
// increase word count once word 'becomes' a node
word_count++;
// implement hash function
int h = hash_it(word_dic);
if (hashtable[h] == NULL) // if pointer to 1st element of array points to a NULL value
{
// allocate space for node along index of hashtable
hashtable[h] = malloc(sizeof(node));
// check if pointer points to NULL value
if (hashtable[h] == NULL)
{
printf("Could not malloc a new node. Error in memory allocation.\n"); // not enough memory to be allocated
return false;
}
// copy word variable as the first member of node struct
strcpy(hashtable[h]->word, word_dic);
// pointer in node set to NULL
hashtable[h]->next = NULL;
}
else // if bucket isn't empty, hashtable[h] != NULL
{
// attach node to front of list
// design choice: unsorted linked list to minimise load time rather than sorted list to minimise check time
// malloc a node for each word to be imported into hash-table dictionary
node *new_node = malloc(sizeof(node));
// check if pointer points to NULL value
if (new_node == NULL)
{
printf("Could not malloc a new node.\n"); // not enough memory to be allocated
return false;
}
// copy word variable as the first member of node struct
// use strcpy because arrays do not support assignment (=) operator
strcpy(new_node->word, word_dic);
// point new node pointer to where index node is pointing
new_node->next = hashtable[h];
// point index node's pointer to new node, hence, inserting new node at front of the list
hashtable[h] = new_node;
}
}
// close dictionary
fclose(fp);
loaded = true;
return true;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
if (loaded)
{
return word_count;
}
else
{
return 0;
}
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
for (int i = 0; i < HASHTABLE_SIZE; i++)
{
node *traversal_pointer = hashtable[i];
while (traversal_pointer != NULL)
{
node *temp = traversal_pointer;
traversal_pointer = traversal_pointer->next; // point
traversal_pointer to next node on the list
free(temp);
}
}
loaded = false;
return true;
}
Edited parts
for ( int i = 0; i < length; i++)
{
word_copy[i] = tolower(word[i]);
}
Update
After correcting the part of my code @DinoCoderSaurus pointed out, the number of words in my dictionary and in the the text matches the staff's output but I am still unable to get the number of misspelled words. Check50 points out another error, that is, a greater number of words in my dictionary. I am confused as Check50 seems contradictory to the discrepancies between my output and that of the staff's? I know I'm so close to passing check50!! I still can't figure out what's wrong with my code ):
and
https://sandbox.cs50.net/checks/d83c7088f59d4536b081054359509358
E.g.
