0

I am working through pset5 using the trie data structure and it has been very challenging. I finally have code that compiles but when I run it against cat.txt using the small dictionary it returns all words as misspelled and 0 words in the dictionary so there is clearly a problem with load. I tried debug 50 but I'm finding it hard to interpret as the action is over check and speller.c, I'm not seeing it read load at all (likely part of/the problem but I'm not sure why it wouldn't be reading it).

There are likely problems other than with load, it's been hard to test functions individually because everything is so interlinked, but I'll start with load. Any suggestions on where the problem might be and/or how to do some more testing/debugging would be appreciated. Check and load below.

// Implements a dictionary's functionality

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


#include "dictionary.h"

//Define struct for trie
typedef struct node
{
    bool is_word;
    struct node *alphabet[27]; //array of node pointers
}
node;

//Define variables
//Keep track of the beginning of the trie, declare as a global variable, never change
node *root = NULL;

//Keep track of number of words in the dictionary
int numworddict = 0;

//Index variable for words
int wordindex = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *trav = root;

//for each letter in input word
    for (int i = 0; i < strlen(word); i++)
    {
        //create index for letters in the trie
        if (isalpha (word[i]))
        {
            //index for letters
            wordindex = tolower(word[i]) - 'a';
        }
        else
        {
            //index for apostrophe
            wordindex = 26;
        }

//go to corresponding element in alphabet in the trie
    //if NULL
    if (trav->alphabet[wordindex] == NULL)
    {
        //word is misspelled
        return false;
    }
    else
    {
        //if not NULL, move to the next letter
        trav = trav->alphabet[wordindex];
    }

//once at end of input word
    if (wordindex == '\n')
    {
        //check if is_word is true
        if (trav->is_word == true)
        {
            //if true return true
            return true;
        }

        //if false it is an invalid word
        else
        {
            return false;
        }
    }
}

return false;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //Allocate memory for root pointer
    root = calloc(1, sizeof(node));

    //Create a node that can traverse through the trie
    node *trav = root;

    //Open the dictionary for reading.
    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    char word[LENGTH + 2]; //word + \0 and \n

    //Scanning through the dictionary one word at a time we'll iterate through the trie
    while (fscanf(inptr, "%s", word) != EOF)
        {
        //iterate over the letters of the word in order to create a word     index
        for (int i = 0, n = strlen(word); i < n; i++)
        {
            //Each element in alphabet array corresponds to a different letter
            //create index for letters in the trie, alphaindex
            if (isalpha (word[i]))
            {
                //index for letters
                wordindex = tolower(word[i]) - 'a';
            }
            else
            {
                //index for apostrophe
                wordindex = 26;
            }

            //check whether you're at the end of a line
            //if you're not at the end of a line, you're not at the end of a word
            if (wordindex != '\n')
            {
            //check the value at alphabet[wordindex]
                //if NULL
                if (trav->alphabet[wordindex] == NULL)
                {
                    //malloc a new node, set it to NULL
                    //have the traversal pointer point to it
                    trav->alphabet[wordindex] = calloc(1, sizeof(node));
                }

                //if not null
                else
                {
                    //move to next node and continue
                    trav = trav->alphabet[wordindex];
                }
            }
            //if you are at the end of a line, you're at the end of a word
            //if at end of line
            else
            {
                //set is_word to true
                trav->is_word = true;
                //increment word count
                numworddict++;
                //set traversal pointer back to the root
                trav = root;
            }
        }
    }
fclose(inptr);
return true;
}
0

Just looking at load:

if (wordindex != '\n') makes no sense to me. '\n' is 13, the index chosen for 'm'.

If you use fscanf, you probably don't have to worry about '\n'. fscanf when used with %s will skip all whitespace before it reads a word, which is read until hitting whitespace or EOF.

So inside your inner loop, you can assume not hitting '\n'. BTW, even if you have to create a node, you still have to traverse, it's not an alternative.

After your inner loop, consider the word complete (hitting whitespace/newline).

2
  • Thank you so much! I removed the if statement regarding the '\n' and I can't believe I forgot to put a statement to traverse when I create a new node, I've added that too. I now have two words in the dictionary when I use dictionaries small which is exactly what it should be. Now on to fixing check.
    – CM23
    Apr 17 '18 at 17:41
  • Thank you again, so much! Using what you said for load I was able to debug check and, miraculously, I have no issues in size or unload. My program passes all check50 checks and I am literally ecstatic.
    – CM23
    Apr 17 '18 at 18:09

You must log in to answer this question.

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