pset5 Misspellings - passes check50 - doesn't work with larger text file

Question

I've been pulling my hair out over Misspellings and I've finally got it to the point where is passes check50. Though when I run the code with austinpowers.txt for example, it says I have 19188 misspelled words.

I'm pretty sure that my load function works okay, I believe the issue might be with check, sometimes the custom text files I'm testing check with will miss the last word in the file depending of the length of the file. I'm really stuck, any help would be amazing. Here is my check function:

bool check(const char* word)

char wordlower[LENGTH + 1];
int wordlength = strlen(word);    

for (int i = 0; i <= wordlength; i++)
{
    if(isalpha(word[i]))
    {
        wordlower[i] = tolower(word[i]);
    }
    else
    {
        wordlower[i] = word[i];
    }
}

node* checker = hashtable[hash(wordlower)];

while (checker)
{
    if(strcasecmp(checker->word, wordlower) == 0)
    {
        return true;
    }
    checker = checker->next;
}

return false;

Answer 1

My suspicions were correct. The problem lies in load(), not check(). It is a very subtle logic problem.

If you were to write a function to traverse your dictionary after load finished, you would find that it would contain a maximum of 26 words, depending on the dictionary - exactly 1 word for each hash number from 0 to 25. The problem lies in the following code, lines 121 thru 125:

    else
    {
        new_node->next = hashtable[hashindex]->next;
        hashtable[hashindex] = new_node;
    }

When the tree is empty, hashtable[x]->next is null. It remains null when the first word is loaded for hash = x. When the second word for hash=x is loaded into the dictionary, it is put in the root of the linked list, pointed to by hashtable[x]. Now here's where the problem arises. The pointer at hashtable[x]->next, which is still null, is put into new_node->next. This causes the previously loaded word, pointed to by hashtable[x] to be lost.

Instead of hashtable[x]->next, the pointer that should be copied is hashtable[x] itself. Once I made this change, it ran successfully with holmes.txt.

However, it was quite slow. This may cause a timeout when check50 executes. If not, it will pass. I didn't run valgrind or analyze it for the performance issues, that's for your enjoyment. I did go back and look at your hash function. With this hash, you can use a much larger hash size than 26. I changed it to 1024 and the speed increase was dramatic. You can play around with that and see for yourself.

One side note: You use "word" for vars in at least 3 different ways - a global var, part of a global structure, and a local var, not to mention "words". This is not a good practice. It can lead to confusion and to scope issues. You might want to address this in your code.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)