Pset5 dictionary.c is not producing correct output

Question

I've implemented my load and check functions using tries. The program works fine and produces the output, but when I compared it against the output from staff's implementation, I found out that there were some discrepancies. For example, let's say we load the "large" dictionary and check "tolstoy.txt". I expected my program to write out the words that were exclusive to tolstoy.txt, but instead, it's the other way around.

My program returns words that are exclusive to "large" dictionary and cannot be found on tolstoy.txt. Have a look at my program.

#define Alphabet 27    

struct node
{    
    bool end;
    struct node* children[Alphabet];    
}; 


/**
 * Returns true if word is in dictionary else false.
 */

bool check(const char* word)
{
    struct node* move = head;
    int index = 0;
    int j = 0;

    while (word[j] != '\0')
    {
        if(word[j] == '\'')
        {
             index = Alphabet - 1;
        }
        else
        {
            index = toupper(word[j]) - 'A';
        }
        if(move->children[index] != NULL)
        {
            move = move->children[index];
            j++;
        }
        else
        {
            move->end = false;
            //printf("Not Found\n");
            break;
        }
    }
    if(word[j] == '\0' && move->end == true)
    {
        return true;
    }
    else
    {
        return false;
    }

}

[edit: unrelated code removed for Honor Code compliance.]

I've been solving this problem non-stop for a week now and I'm thoroughly exhausted. Any help would mean the world to me. Thanks!

Answer 1

Interesting problem. It's actually showing a mix of words from both files as a side effect of the problem. Your check() code is actually altering the dictionary trie instead of just reading it. My guess is that you put some kind of a notation in and it became code (or it was the middle of the night...).

Here's the problem.

else
    {
        move->end = false;
        //printf("Not Found\n");
        break;
    }

This one is hard to explain, so follow closely. When there is a word in the check file that doesn't exist in the dictionary, but the leading letters do appear as a word, AND the dictionary word is the longest in the trie that also appears in the word being checked, the code will change the node->end marker to false in the dictionary.

For example, let's say that your word being checked is caterpillar. The dictionary contains the words cat and cater, but not caterpillar. When you check caterpillar, it will change the end of word marker for cater to false. After that, if cater is in the check text, it will show up as not a word.

Simple solution, which I think you were really intending to do:

    else
    {
        return false;
    }

Also, a couple of little details. You use a LOT of blank lines in your code. It would be more readable if you cut back. Try running your code through style50. I think you'd benefit a lot from it. Finally, for future questions, please explore the help tab at the top of this page for info on how to post code. It will help you here, and make it a lot easier for those that try to help you.

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