0

I have been working on this error for couple days, but still cannot figure out what the problem is. The program compiles and finds the misspelled words in the beginning, but after printing out about 3/4 of the misspelled words it suddenly stopped working. There are probably errors in my unload function. I haven't really worked on the unload function because every time I run valgrind it gives me this problem, but in case it is related, I also upload the code of unload function. I used trie here. Can anyone please take a look at my code and give me some advice? Thank you in advance!

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

typedef struct node
{
    bool is_word;
    struct node * children[27];
}
node;

node *root;

int count;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *trav = root;
    for (int i = 0; i < strlen(word); i++)
    {
        int indexarray;
        if (isalpha(word[i]))
        {
            indexarray = tolower(word[i]) - 'a';
        }
        else
        {
            indexarray = 26;
        }
        trav = trav->children[indexarray];
        if (!trav)
        {
            return false;
        }

        if (i == strlen(word) - 1)
        {
            if (trav->is_word)
            {
                return true;
            }
        }
    }
    return false;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    count = 0;
    FILE *dictionaryfile = fopen(dictionary, "r");
    if (!dictionaryfile)
    {
         return false;
    }

    char word[LENGTH + 1];
    root = calloc(1, sizeof(node));

    node *trav = root;
    if (!root)
    {
        return false;
    }

    while (fscanf(dictionaryfile, "%s", word) != EOF)
    {
        for (int i = 0; i < strlen(word); i++)
        {
            int indexarray;
            if (isalpha(word[i]))
            {
                indexarray = word[i] - 'a';

            }
            else
            {
            indexarray = 26;
            }

        if (!trav->children[indexarray])
        {
            trav->children[indexarray] = calloc(1, sizeof(node));
            if (!trav->children[indexarray])
            {
                return false;
            }
        }

        trav = trav->children[indexarray];

        if (i == strlen(word) - 1)
        {
            trav->is_word = true;
            count++;
        }
    }
    trav = root;
}
fclose(dictionaryfile);
return true;
}

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

bool freetrie(node *ptr);
bool checknull(node *ptr);

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *cursor = root;

    if (freetrie(cursor))
    {
        free(cursor);
        return true;
    }
    return false;
}

bool freetrie(node *ptr)
{
    node *trav = ptr;
    while (ptr)
    {
        for (int i = 0; i < 27; i++)
        {

            ptr = trav->children[i];
            if (ptr)
            {
                if (checknull(ptr))
                {
                    free(ptr);
                }
                else
                {
                    freetrie(ptr);
                }
            }
        }
    }
    return true;
}

// check if all children are null
bool checknull(node *ptr)
{
    while (ptr)
    {
        int j = 0;
        while (j < 27)
        {

            if (!ptr->children[j])
            {
                j++;
            }
            else
            {
                return false;
            }
        }
    }
    return true;
}

Here is how it looks like when I compare my answer to the solution.

When I run check50, it shows that it could not find the misspelled words.

Here is how it looks like when I compare my answer to the solution. When I run check50, it shows that it could not find the misspelled words.

1

I'm not sure it is related to incomplete output, but your unload function indeed is wrong. In your recursive function, you should not change ptr, which points to the subtrie to unload. You should not even traverse the trie by other means than recursive calls. No need for having the value to pass in an extra variable first.

A trie node can be freed safely when all its children are either NULL or have been unloaded recursively. Makes one for loop with an if.

Also, you frequently put things in the loop for the last iteration. Why not move that out of the loop, where execution will continue? Saves you another if.

And be careful about while. In case of checknull, that is an infinite loop for certain nodes.

4
  • All good advice. When I ran the code above, it took too long to execute, so tests failed. I altered the unload function to simply return true and it ran well, except for the final test.
    – Cliff B
    Sep 14 '18 at 10:22
  • Blauelf and Cliff, thank you so much for your help! The problem indeed lies within my unload function. I fixed my unload function and it runs fine now.
    – Stella. H
    Sep 14 '18 at 21:45
  • I do have one more question regarding the unload function. After the recursive function is done and the root is freed, if I want to use if function to check if the root is NULL, it always return false. When I run valgrind, it does show every byte is freed. Why does if (!root) return false?
    – Stella. H
    Sep 14 '18 at 22:27
  • free does not change the pointer. It only changes the allocated memory it is pointing to. If you want to have NULL everywhere, you would have to assign it after each call to your recursive function (in the calling code!), or use pointers to pointers.
    – Blauelf
    Sep 17 '18 at 15:11

You must log in to answer this question.

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