I'm stuck with load and check and have several issues.
At the top of my code I have the following:
typedef struct node
{
bool is_word;
struct node* children[27];
}
node;
node* root;
node* trav;
int numwords;
My issues with load:
Using gdb (GUI on the IDE) I see that after my for
loop is done I have words in my trie. Some of the words go all the way to the end and have the is_word
on the last node set to true
. Some words don't go all the way to the end. The last word in the dictionary doesn't seem to have it's is_word
set to true
ever and doesn't go all the way to the end. Another issue with load is that the numwords
counter always gives me back a number that is one greater than the actual number of words. I have gone over my code with pen and paper and still can't figure out what's wrong with it. Here's my load
:
bool load(const char* dictionary)
{
node* root = malloc(sizeof(node)); //root of the trie
node* trav = malloc(sizeof(node));
char* buff = malloc(45);
char* wordbuf = malloc(45); //buffer for words being loaded
int letterin;
int numwords = 0;
FILE* dicto = fopen(dictionary, "r"); //open dictionary file
if (dicto == NULL)
{
return false;
return 1;
}
for (int b = 0; b < 27; b++) //setting each children to NULL
{
root -> children[b] = NULL;
}
while(true)
{
if (feof(dicto))
{
//return false;
return 1;
break;
}
else
{
trav = root; //traversal pointer for navigating
fgets(buff, 45, dicto);
sscanf(buff, "%s", wordbuf);
char len = strlen(wordbuf);
for(int i = 0; i < len; i++)
{
if (strcmp(&wordbuf[i], "\'") == 0)
{
letterin = 26; //assigning apostrophe to last place in the array
}
else if (isalpha(wordbuf[i]))
{
letterin = wordbuf[i] - 97;
}
if (trav -> children[letterin] == NULL)
{
trav -> children[letterin] = (node*)calloc(1, sizeof(node));
}
trav = trav -> children[letterin];
if (len - i == 1) //end of word
{
trav -> is_word = true;
numwords++;
}
}
}
}
return true;
}
I've read that using feof
in a control loop is not a good idea which is why I don't have it in the while
loop, but would still like to know if the way I'm using it is correct. Even with these issues load
compiles and has no seg faults according to valgrind. That's where check
comes in.
bool check(const char* word)
{
node *trav = root;
char len = strlen(word);
int letterin = 0;
for (int i = 0; i < len; i++) //start traversing trie looking for word
{
bool is = isalpha(word[i]); //this was for debugging
if (strcmp(&word[i], "\'") == 0)
{
letterin = 26; //assigning apostrophe to last place in the array
}
else if (is)
{
letterin = tolower(word[i]) - 97; //convert letter to corresponding alphabet index
}
if (trav -> children[letterin] == NULL)
{
return false;
break;
}
trav = trav -> children[letterin];
}
if ((trav -> is_word) == true)
{
return true;
}
return 0;
}
Again, checking with gdb I see that setting trav = root
only gives me one node with all its children set to NULL
. Is there something else I should have done to get the trie I ended up with after load
? And here is where I get my seg fault
if (trav -> children[letterin] == NULL)
{
return false;
break;
}
After what I saw I have for trav
I would have expected it to return false
, not a seg fault. Why is this happening? (Also, is my use of break
correct? Would I get the same if I return 1
?)
I'm at a loss and need the fresh set (and more experienced) set of eyes. Any help is appreciated.