0

I can't, for the life of me, figure out why my check function doesn't work properly. I have triple-checked my load() every way I know how and believe the data structure is properly setup. Why doesn't the below function properly check my trie?

My check function (where I believe the issue lies):

bool check(const char *word)
{

    trav = root;

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

        char c = tolower(word[i]);
        int c_index;

        if(c=='\'')
        {
            c_index = 26;
        } else {
            c_index = c - 'a';
        }

        if(trav->children[c_index] == NULL) {
            return false;
        } else if(trav->is_word == true && i == n-1) {
            return true;
        }

        trav = trav->children[c_index];


    }
    return false;
}

My trie data structure (declared at global scope within dictionary.c):

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

node* root;
node* trav;

My load function:

bool load(const char *dictionary)
{
    root = calloc(1, sizeof(node));
    trav = root;

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

    // printf("---LOAD TEST BEGIN---\n");

    int c_index;

    for (char c = tolower(fgetc(dictptr)); c != EOF; c = tolower(fgetc(dictptr)))
    {

        // Catch new line

        if (c == '\n')
        {
            trav->is_word = true;
            dict_size++;
            trav = root;
        }

        //Catch apostrophe
        else if (c == '\'') {
            // printf("%c, 26\n",c);
            if(trav->children[26] == NULL)
            {
                trav->children[26] = calloc(1, sizeof(node));
                trav = trav->children[26];
            } else {
                trav = trav->children[26];
            }
            // printf("APOSTROPHE LOCATED\n");
        }

        else if (isalpha(c) != 0) {
            c_index = c - 'a';
            // printf("%c, %i\n", c, c_index);
            if(trav->children[c_index] == NULL)
            {
                trav->children[c_index] = calloc(1, sizeof(node));
                trav = trav->children[c_index];
            } else {
                trav = trav->children[c_index];
            }
        } else {
            return false;
        }
    }


    fclose(dictptr);
    return true;
}
1

The problem is that you do not check is_word of the current node as your loop is over at the moment when your are in the right place.

let's suppose it is word "a". So n= strlen(a) = 1. You check trav == root. trav -> children[a] != NULL. Then, you immediately check trav -> is_word. but it is not "true". "true" is in the next node.

Then you step forward (where "true" is), but do not check it. You return to the top of your loop and do i++. i < n is now false, so loop is over and you return false.

You need to make step forward BEFORE checking is_word, immediately after you see that you can go there (trav -> children[a] != NULL)

| improve this answer | |
  • Yes! Thank you so much. You nailed it. I won't spoil the answer here, but I appreciate the help. I had the wrong diagram drawn out of my trie, but this makes much more sense and actually works! – Finesse Upscale Jul 7 '17 at 12:24

You must log in to answer this question.

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