Skip to main content
Completed answer.
Source Link

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.

SUGGESTION #1

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.

You can jump to SUGGESTION for quick answer.

SUGGESTION

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

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.

SUGGESTION #1

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.

Source Link

You can jump to SUGGESTION for quick answer.

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

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