0

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;
8
  • check() appears to be working fine. It's very common that what appears to be a problem with check is actually a hidden problem in load(). Less common is a hash function that doesn't provide the same result in load that it does in check. I would look at load first though. – Cliff B Jun 8 '16 at 17:24
  • Thanks for replying - I have found the following while changing things in check.. I was checking the end of line character in load, I was told to remove that. when I add in the line wordlower[strlen(word)] = '\0'; It passes check50 But it fails terribly with austinpowers.txt If I change: if(strcmp(checker->word, wordlower) == 0) to if(strcmp(checker->word, wordlower)) the program seems to work with larger files when that doesn't have the ==0 but it doesn't work with the smaller files?! I don't know what else to change in check to get this to work – clomas Jun 9 '16 at 0:28
  • strcmp() depends on the presence of the end of string marker \0 being present so that it knows where the string ends. Also, strcmp returns any one of 3 answers - a positive number if the second string is "greater" (lexicographically), a negative number if the first string is "greater", or 0 if they are the same. The problem in your change is that if the two strings are identical, strcmp() returns 0, which evaluates as false, introducing another error into your program. I still think the problem lies in load and not in check. – Cliff B Jun 9 '16 at 0:39
  • Have you verified what you are loading with each word? Is it possible that you are leaving the \n at the end of each word? This wouldn't show if your test text file is one word per line. Here's a test. Create a short test dictionary, then a short test file using all the same words in the dictionary, but all on one line, separated by spaces. If it fails, there's a good chance it's the \n problem. If you can't find the problem, please edit the question and add load and any hash function, along with anything else required for load and check. – Cliff B Jun 9 '16 at 0:42
  • Here's my load function pastebin.com/wyLdwn4d Here's my hash function pastebin.com/ybcK7T0d – clomas Jun 9 '16 at 1:22
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. ;-)

1
  • That definitely helped with my issues, the program seems to work a lot better. Thanks for pointing out the variable name issues. I've fixed that now. HASHSIZE was a lower number just for the initial stages of testing my program. I still have a problem though. All the long texts seem to work properly. But when I use my own txt file and dictionary. text: Where is the last word of this dictionary: where is the last word of this I get WORDS IN DICTIONARY: 7 WORDS IN TEXT: 6 if I put a question mark on the end however, it works fine! – clomas Jun 12 '16 at 8:52

You must log in to answer this question.

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