My speller "seems" to work well as compared to the staff's solution: find the correct number of WORDS MISSPELLED (644 of austinpower.txt), correct number of WORDS IN DICTIONARY (143091 of dictionaries/large) and correct number of WORDS IN TEXT (19190 of austinpower.txt), and it also passes the valgrind test (0 errors).
However, it failed the check50 and the error message showed "valgrind tests failed" in every check points. I'm confused. Could anyone point out where the problem is?
My code:
/**
* Implements a dictionary's functionality.
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"
typedef struct node //define the struct of hash table
{
char word[LENGTH+1]; // +1 is for the \0, indicating end of the word
struct node *next;
}
node;
node *hashtable[27]; // create a hash table. 26 buckets of this hashtable (to store entire dictionary) + 1 bucket for apostrophe
// each element of array is a node * (node pointer)
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
int hash_function(char); // implement the hash function
int dic_count = 0; // dictionary count
bool load(const char *dictionary)
{
FILE *dic_ptr = fopen(dictionary, "r"); // open the dictionary
if (dic_ptr == NULL)
{
fprintf(stderr, "Cannot open that dictionary.\n");
return false;
}
char dic_word[LENGTH+1]; // define word for dictionary
while (fscanf(dic_ptr, "%s", dic_word) != EOF) // scan inside the dictionary word by word ?? word in dict??
{
dic_count++;
node *new_node = malloc(sizeof(node)); // create a new node (called new_node) to store the scanned word from dictionary.
if (new_node == NULL) // whenever make a new node, always check that the pointer to that node doesn't return NULL.
{
unload();
return false;
}
strcpy(new_node->word, dic_word); // string strcpy(string destination, string source) --> (new_node, dictionary)
// finish storing the dic_word in the new_node
// start to put it into the hashtable-> linked list
char first_letter = dic_word[0]; // assign the 1st letter of dic_word as a char
int index = hash_function(first_letter); // hash the word: output index (hash_code) from 1st letter via hash_function
// populate the hashtable
// if this bucket's node pointer is not yet assigned, make a head for this bucket
if (hashtable[index] == NULL) // hashtable[index] is the head pointer (if it points to NULL, then:
{
hashtable[index] = new_node;
new_node->next = NULL;
}
else // already have previous node, just link to it
{
new_node->next = hashtable[index]; // new_node point to the pointee of head (both head and new_node point to the same node, aka previous node/word
hashtable[index] = new_node; // then the head point to the new_node
}
}
return true;
}
int hash_function(char c)
{
int x;
if (isalpha(c))
{
char l = tolower(c);
int x = l - 97; // a is 0, b is 1, c is 2... so on
return x; // x = index (hash_code)
}
else if (c == '\'') // apostrophe
{
x = 26; // put in the hashtable[26]
return x;
}
else
{
x = 30; // not fit in the hashtable with 27 buckets
return x;
}
}
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char *word) // this "word" is from text
{
// transform to lowercase
char buffer[LENGTH+1];
strcpy(buffer, word);
for (int i = 0; word[i] != '\0'; i++)
{
if (isalpha(word[i]))
{
buffer[i] = tolower(word[i]);
}
else if (word[i] == 39) // ASCII for the apostrophe
{
buffer[i] = '\'';
}
}
int index = hash_function(word[0]); // 1st letter
node *cursor = hashtable[index]; // create the cursor, then go to the
correct bucket
while (cursor != NULL)
{
int x = strcmp(buffer, cursor->word);
if (x == 0)
{
return true; // the same!
}
else // x != 0
{
cursor = cursor->next; // go to the next node
}
}
return false;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
return dic_count;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
for (int i = 0; i < 26; i++)
{
node *cursor = hashtable[i];
while (cursor != NULL)
{
node *temp = cursor;
cursor = cursor->next;
free(temp);
}
}
return true;
}
Thank you in advance!
