Code passed check50, but the output does not match staff output and the code fails valgrind

Question

``Thanks for your help so far on pset5. I have been able to implement pset5, the code is working properly, passed check50 but the output does not match the staff output. For instance, when tested with alice.txt, my code gives over 1,000 errors while that of the staff gives just 644 errors. Moreover, valgrind shows quite a lot of memory loss. Please check through my code and advice me where I got it wrong. Thanks so much.

/**
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 */

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"
#define ALPHABETS 27

typedef struct node
{
    bool is_word;
    struct node* children[ALPHABETS];
} node;
node* root = NULL;
int counter =0;


/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    // TODO
    node* current = root;
    int w_index;

    int w_len = strlen(word);
    for(int i = 0; i < w_len; i++)
    {

        if(isalpha(word[i]))
        {
            if(isupper(word[i]))
                w_index = (tolower(word[i])) - 'a';
            else
                w_index = word[i] - 'a';
        }

        else if (word[i] == '\'')
        {
            w_index = 26;
        }
        if(current->children[w_index] == NULL)
        {
            current->is_word = false;
            return false;
        }
        else
            current = current->children[w_index];
    }

    if(current->is_word == true)
        return true;
    else
        return false;

    return true;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // TODO


    char d_word[LENGTH +1];
    root = (node*)malloc(sizeof(node));
    if(root)
    {
        int i;
        root->is_word = false;
        for(i = 0; i < ALPHABETS; i++)
            root->children[i] = NULL;
    }

    FILE* file = fopen(dictionary, "r");
    if (file == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        unload();
        return 1;
    }

    int index;
    while(fscanf(file, "%s", d_word)!= EOF)
    {
        node*trav = root;
        int length = strlen(d_word);
        for(int j = 0; j < length; j++)
        {
            if(isalpha(d_word[j]))
                index = d_word[j] - 'a';
            else if(d_word[j] == '\'')
                index = 26;
            if(trav->children[index] == NULL)
                trav->children[index] = malloc(sizeof(node));

            trav = trav->children[index];
        }
        trav->is_word = true;
        counter++;
    }

    fclose(file);
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    // TODO
    return (counter);
}


/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    // TODO

    node* temp;
    node* cursor = root;
    for(int i = 0; i < ALPHABETS; i++)
    {

        if (cursor->children[i] != NULL)
        {
            temp = cursor;
            cursor = cursor->children[i];
            continue;
        }

        else if(temp != NULL)
        {
            free(temp);
            temp = NULL;
        }

    }
    return true;
    //return false;
}

Answer 1

You can jump to SUGGESTION #1 for quick answer on wrong number of misspelled words.

You can jump to SUGGESTION #2 for quick answer memory leaks.

I am still working on the memory leaks. However, I found why your number of misspelled words don't match the staff's implementation.

Line 54:

current->is_word = false;

You do not want to change any variables' values in your trie under the check() function. You only want to read data on check(), not write (or overwrite).

While debugging I found that "not" is a word that your speller marks as misspelled.

I tested with a dictionary that has only one line:

not

And a text that has three lines:

not
nothing
not

The speller would take the first not as correctly spelled and second one as misspelled. Why?

Because line 54 is setting not's boolean to false if the next node is NULL. It does this while evaluating the word nothing.

SUGGESTION #1

Delete line 54. You can return false as you are already doing, but you don't want to edit anything on the check() function. It will look something like this:

bool check(const char* word)
{
    // TODO
    node* current = root;
    int w_index;

    int w_len = strlen(word);
    for(int i = 0; i < w_len; i++)
    {

        if(isalpha(word[i]))
        {
            if(isupper(word[i]))
                w_index = (tolower(word[i])) - 'a';
            else
                w_index = word[i] - 'a';
        }

        else if (word[i] == '\'')
        {
            w_index = 26;
        }
        if(current->children[w_index] == NULL)
        {
            // Line 54 used to be here overwriting booleans.
            return false;
        }
        else
            current = current->children[w_index];
    }

    if(current->is_word == true)
        return true;
    else
        return false;

    return true;
}

UPDATE

I looked at your unload function and it seems that things are out of control in the loop. For instance, you go to the next node and you increment your counter:

cursor = cursor->children[i];
continue;

That will be like saying:

We have a word that starts with "a". Good, then check for words that start with "ab".

We have a word that starts with "ab". Good, then check for words that start with "abc".

We have a word that starts with "abc". Good, then check for words that start with "abcd".

... And so on.

And when cursor->children[i] is indeed NULL, temp gets freed. At that point temp is just the previous node.

This will execute ALPHABETS times (27). And with the large dictionary the process will look like the below. I am going to display with letters what will be happening in the code with the nodes:

a
ab
abc
abcd false

free this node a->b->(c)

abcde false

free this node a->b->(c)

abcdef false

free this node a->b->(c)

abcdefg false

free this node a->b->(c)

abcdefgh false

free this node a->b->(c)

And so on until you get to:

abcdefghijklmnopqrstuvwxyz' false

free this node a->b->(c)

free this node a->b->(c)

SUGGESTION #2

So, since I don't really know how to unload a trie with an iterative approach, I will show you a recursive approach that I copied and pasted from someone in CS50 Stack Exchange more than a year ago:

void FreeNode(node* ptr);

bool unload(void)
{
    // TODO
    FreeNode(root);
    return true;
}

void FreeNode(node* ptr)
{
    if (ptr != NULL)
    {   
        for(int i = 0; i < ALPHABETS; i++)
        {   
            FreeNode(ptr->children[i]);
        }   
        free(ptr);
    }   
}

If you need an explanation on how it works let me know. I am very fond of this function. I think is simple and tenacious.

Depending on how you load your dictionary you might still get errors with valgrind. However, these errors refer to dangerous practices. It will still say that no leaks are possible.