0

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.

0

There are a number of issues, mostly with load.

Load:

Moving the EOF test from the while construct to an if statement immediately following it as you did is exactly the same as having it in the while construct. The reason for not having it in the while loop is that the EOF needs to be detected by the fread command or immediately after. The sequence of events in your code is to read a line from the dictionary, process the line, AND THEN check for the EOF. It processes an extra read, putting unpredictable data in the dictionary, along with an extra increment on the word counter, before terminating the loop. That's garbage data in the trie and accounts for your one-off word count.

The fread should be incorporated into the while loop and check for the EOF from the return value from the fread.

Next, you use an if/else form in your while loop to either terminate the loop or to process the next line. The else clause is redundant when you put a return in the IF side. If it returns, no further code will execute in the function. If it doesn't return, the code that would follow the if statement will execute no matter what, making the else clause redundant. While technically valid, it is bad form as it introduces unnecessary code and the possibility for error if the code is ever altered later. (Of course, this becomes a moot point if you fix the while construct.)

There's still another problem with that code. When the EOF is reached, the IF test passes, and the code returns. Your comment says // return false but the code says return 1; which is a return true. If you return numerics, 0 represents false. True, usually 1, has various representations, depending on the programming language and the architecture. This is often misunderstood because it is also standard practice to return 0 when a program succeeds and a non-zero to represent various error or unexpected conditions. For that reason, it is always best to use TRUE or FALSE when returning a bool, and not a number.

Interesting thing about fgets(). It will read a line from a file and put it in the target (in this case, buff), INCLUDING the line feed character. for example, if you read in "cat" then the string "cat\n" will go into the buffer. strlen() will return 4, not 3. I started to say that the code isn't handling the end of each word correctly because of this, but the sscanf is negating the effect.

The code copies each word from the input file into buff and then from buff into wordbuf. Wordbuf is redundant and unnecessary. All of the processing can be done with buff.

Now for a small error that makes a really big problem. root is re-declared inside of load. This is called declaring a shadow variable. The shadow var takes precedence and all the actions will be taken on the local, shadow variable, while the global remains set to whatever it contains. Since it wasn't initialized to anything, the global root will contain garbage data, most likely leading to a seg fault. Also, when load finishes, the local root will cease to exist, so load will have done nothing that can be used later.

check:

Same problem with returning numeric values instead of true/false.

A break statement (or any statement) following an unconditional return statement is dead code. It will never be executed because the return statement will immediately transfer control back to the calling function.

There may be other issues, and with this many changes, more may be introduced into the program, but this will get you going again.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

4
  • Thank you very much for your answer. I already have the code running by fixing almost everything you mentioned :) I learned a great deal with this pset, mostly by making these mistakes. – jetgo Apr 12 '16 at 19:28
  • Your comments about root apply to my code - but I don't know how to fix it. I tried using calloc before the code starts but I get an error. Should I allocate memory for root inside of dictionary.h? – Brendan Rafferty Apr 23 '16 at 15:39
  • When creating global vars like root, you can declare them outside of main or a function, maybe even do a simple initialization like assigning a numeric value to an int, but you can't do a malloc or calloc. That has to be done inside of a function or main. – Cliff B Apr 23 '16 at 16:25
  • Thanks Cliff. The point I was missing was that root needed to be on the stack - no calloc or malloc required, just a plain old structure stored on the stack. There is 5 hours of my life I will not get back! – Brendan Rafferty Apr 24 '16 at 3:28

You must log in to answer this question.

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