0

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:

Staff's results My results

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 ): enter image description here

and

https://sandbox.cs50.net/checks/d83c7088f59d4536b081054359509358

E.g. enter image description here

1

Running this through debug50 with a 143,091 word dictionary and a 19,190 word text would be....pick a word.....daunting. Try debugging with a one word file used as dictionary and text (something like ./speller word.txt word.txt).

Put a break point at check. Add a watch expression for word_copy[i] and step through.

Or study this code carefully to figure out why word_copy is never populated correctly:

for ( int i = 0; i < length; i++)
    {
       if (isupper(word_copy[i]))
        {   
            word_copy[i] = tolower(word_copy[i]);
        }

        else
        {
            word_copy[i] = word_copy[i];
        }
    } 

But wait there's more!

I cannot explain why the screen shots show the correct number of "words in dictionary". This while (!feof(fp)) will always do an extra read on the file. The best explanation can be found around 7:30 in this short (from last year). Better to make sure that fscanf(fp, "%s", word_dic) != EOF. You could incorporate it into your while loop or add another if condition.

Have a closer look at the (corrected) code in check:

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';

If the word is 'cat', it has length 3, indexes 0-2, with null terminator in index 3. Where is it putting the null terminator here word_copy[length] = '\0'?

3
  • Thank you! I've corrected the part you've highlighted and played around with smaller text sizes and dictionary cout and the number of misspelled words has dramatically decreased just as it should. 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 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, and I am really lost in figuring out what's wrong. – beiyingseah Jul 20 '17 at 4:26
  • More hints added to answer. – DinoCoderSaurus Jul 20 '17 at 14:24
  • Thank you so much for your explanation and patience! Correcting the extra read by the while (!feof(fp)) did it!! – beiyingseah Aug 8 '17 at 9:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .