0

I've read every post that asks a similar question, and I can't figure out what's wrong. I declared my root node pointer globally. I calloc()ed memory to it in load(), and I used pointers to (try to) traverse the trie in check(). Yet, all the words return misspelled. I ran debug50 and gdb, and I think the problem is with my root node pointer because my conditional statements in my check() function are behaving as though they are receiving NULL pointers. Thoughts?

global declarations:

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

#include "dictionary.h"

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

//create root node pointer for trie
node* root;
//counter for words
unsigned int num = 0;

load():

bool load(const char *dictionary)
{
//open dictionary file for reading
FILE *fp = fopen(dictionary, "r");
if (fp == NULL)
{
    fprintf(stderr, "Could not open dictionary!\n");
    return 1;
}

//allocate space to hold string called word that will hold the current value read by fscanf()
char word[LENGTH];
//allocate space for root node and point to it
root = calloc(1, sizeof(node));
//create a cursor node pointer to traverse trie
node* new;

//read input file one string at a time, storing current string in variable word, until EOF 
while (fscanf(fp, "%s", word) != EOF)
{
    //assign to new the value of root
    new = root;

    //iterate through the current word's letters
    for (int i = 0; i < strlen(word); i++)
    {
        //declare index variable to determine where to place new pointer
        int index;
        //place apostrophes at final index and letters at their corresponding number
        if (word[i] == '\'') 
        {
            index = 26;
        }
        else
        {
            index = tolower(word[i]) - 'a';
        }

        //if the current letter isn't the last letter and the corresponding index value in children is NULL, allocate 
        //a new node and point new to it
        if (new->children[index] == NULL && i < strlen(word) - 1) 
        {
            new->children[index] = calloc(1, sizeof(node));
            new = new->children[index];
        }
        //if the current letter isn't the last letter and the corresponding index value in children is not NULL, point new
        //to where the corresponding index value points
        else if (new->children[index] != NULL && i < strlen(word) - 1)
        {
            new = new->children[index];
        }
        //if the current index is the last letter, allocate a new node if there isn't one, point new to it, and set is_word 
        //to true; iterate word count variable num
        else if (i == strlen(word) - 1) 
        {
            if (new->children[index] != NULL) 
            {
                new->is_word = true;
                num++;
            } 
            else 
            {
            new->children[index] = calloc(1, sizeof(node));
            new = new->children[index];
            new->is_word = true;
            num++;
            }
        }
        else 
        {
            return false;
        }
    }
}
fclose(fp);
//return true if all words load by EOF
return true;
}

check():

bool check(const char *word)
{
node* trav = root;

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

    if (word[i] == '\'') 
    {
        index = 26;
    }
    else
    {
        index = tolower(word[i]) - 'a';
    }

    if (i == strlen(word) - 1 && trav->is_word == false)
    {
        return false;
    }
    else if (trav->children[index] != NULL && i < strlen(word) - 1)
    {
        trav = trav->children[index];
    }
    else if (trav->children[index] != NULL && i == strlen(word) - 1) 
    {
        trav = trav->children[index];
        if (trav->is_word == true) 
        {
            return true;
        }
        else 
        {
            return false;
        }
    }
}
return false;
}
1

You have the problem very similar to this one.

You check

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

Let it be word "a". You are now in the root node, i == strlen(word) - 1 == 0 so you check trav->is_word but its is false! So you return false. In the root node you just can see that "the door" to 'a' is open, it might be "a", might be "age", you don't know yet. You have to step forward and true for "a" is here.

You might say "hey, but I put it in the current node in load()"

else if (i == strlen(word) - 1) 
        {
            if (new->children[index] != NULL) 
            {
                new->is_word = true;
                num++;
            }

but, because dictionaries are all sorted, this condition is never true, so you proceed to next steps where you do everything correctly.

1
  • That's exactly it! Thanks so much! I re-wrote my code, and now it's much more elegant. I had a lot going on in my conditions that was unnecessary. I appreciate it! – ekazubuike Jul 13 '17 at 13:12

You must log in to answer this question.

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