1

So I'm not getting load to work properly in PSET5. Any tips on what I'm doing wrong?

My method now:

  1. Scan char by char in file until EOF; increment index (global)
  2. Insert each item into the trie from the root (global) -> this also updates the pointer so the next character in the loop starts from that pointer
  3. Continuing will insert at the previous node recursively (I think).
  4. When you reach end of word, return the trie pointer to head and set index to 0;

Here's what that looks like FYI what most people call 'nodes' I've labled as 'trie' (struct with bool isWord and trie* children[27] (edit - mistyped here. it should be 27 because of the '\'' character slot):

    trie* wordPtr = head;
for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            wordPtr = insert(c, wordPtr);
            index++;
        }

        else if (index > 0)
        {
           // update counter
            num_words++;
            endword(wordPtr);
            wordPtr = head;
            index = 0;
        }
    }

I've searched the forums and this 'insert' method seems to be pretty standard, but here's the code for it:

trie* insert(char c, trie* ptr)
{
    if (c == '\'' && ptr->children[26] == 0)
    {
        ptr->children[26] = calloc(1, sizeof(trie));
        return ptr->children[26];
    }
    else if (c == '\'' && ptr->children[26] != 0)
    {
        return ptr->children[26];
    }
    if (ptr->children[c -'a'] == 0)
    {
        ptr->children[c - 'a'] = calloc(1, sizeof(trie));
        return ptr->children[c - 'a'];
    }
    else
    {
        return ptr->children[c - 'a'];
    }
}

endword indeed just sets the ptr->isWord to true.

Any idea what I'm doing wrong? Can I update wordPtr in the way that I've done it (passing it to the a function and updating it on when that function returns)?

Thanks!

1

You can skip until the QUICK ANSWER at the end.

I was running your program with gdb. Before I tell you what I found I would like to ask you, what is endword()?

I assumed it is something like this:

void endword(trie* ptr){
     ptr->isWord = true;    
}

I found two things that could be causing problems:

1.- I think you mean 25 everywhere you have 26 in the insert function. Since you can only access up to the 25th index (starting with the 0th index) of an array of 26 elements.

2.- I tracked a Segmentation fault running your program like this:

./speller texts/austinpowers.txt

If I run it with gdb I see it failing at line:

if (ptr->children[c -'a'] == 0)

This is because the first word in the large dictionary is "a". Before any words are loaded the head pointer is NULL.

wordPtr becomes a copy of head here:

trie* wordPtr = head;

and ptr becomes a copy of wordPtr when you pass it as an argument:

wordPtr = insert(c, wordPtr);

and then it gets stored in ptr in the first line of the function:

trie* insert(char c, trie* ptr)

So the value of ptr on the first word on the first letter to be loaded is NULL. And then we have this line (since the first letter is not a single quote):

if (ptr->children[c -'a'] == 0)

The problem with this line is that you are trying to access the array children contained in the struct that ptr is pointing to. But at the first letter of the first word ptr is not pointing to anything yet.

QUICK ANSWER

I suggest these changes to you:

Change 26 by 25 everywhere in your insert function.

Add this line:

head = calloc(1, sizeof(trie)); 

before this one:

trie* wordPtr = head;

So you have a trie to start messing with.

UPDATE AFTER LOOKING AT WHOLE CODE

I noticed that your load function always returns false at the end.

SECOND UPDATE

There is this piece of code on speller.c:

bool loaded = load(dictionary);

// some lines in between.

// abort if dictionary not loaded
if (!loaded)
{
    printf("Could not load %s.\n", dictionary);
    return 1;
}

So, I think load() needs to return true in case of success.

6
  • Thanks for the look - really appreciate it. A couple of clarifications: endword functions as you specified and I have 27 pointers in my code not 26 to handle the apostrophe (') character. Also I have in fact I have calloc'ed a trie before as well; I have assigned head to a valid pointer to a trie: see full code here pastebin.com/DAj6fiXr . So assuming the 26 is correct and the pointer is assigned - any other problems? – borker Oct 24 '16 at 15:22
  • Thanks for the link. I've updated my answer. – Ricardo David Antonetti Oct 24 '16 at 15:47
  • Hey Ricardo - that appears to be by design. In speller.c the code is \\ if (!loaded) then show error \\ this means that you should return false if it WAS loaded, correct? – borker Oct 24 '16 at 16:04
  • I updated my answer since it is easier to add code to the answer than to the comments. If loaded is false it will trigger the error message. !false is true, and true triggers the if. – Ricardo David Antonetti Oct 24 '16 at 16:30
  • That makes me laugh and cry at the same time. I suspect it's loading properly now that I've set it to return true. But let me continue to make sure then I'll accept the answer. – borker Oct 24 '16 at 16:35

You must log in to answer this question.

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