1

Salutations, good people.

Been at this pset for a week and am at wit's end. I could really use some assistance. I've dug through a load of answered questions in hopes of finding a solution for myself, but with so many different approaches people have taken to this problem, I find myself even more confused and doubtful of my code than before and still without a solution.

I've run my program through debug50 and have identified the code breaking in the load function at line 133 (else trav = *trav.children[c];) because the variable c is equal to -1 at this point, but I can't figure out why (whether this is the ultimate cause of the seg fault or not, I am also unsure). I'm speculating it's because the character being subtracted is equal to either 64 or 96 in ASCII, but there are neither symbols (@ and `, respectively) in the dictionary text.

PLEASE help--I'm beyond frustrated but will continue banging my head against a wall trying to figure this out for myself in the meantime. Thanks in advance. Here is my code:

     /**
     * Implements a dictionary's functionality.
     */

    #include <stdlib.h>
    #include <stdbool.h>
    #include <ctype.h>
    #include <stdio.h>
    #include <sys/resource.h>
    #include <sys/time.h>
    #include "dictionary.h"

    /**
     * Returns true if word is in dictionary else false.
     */

    // create global node structure for a trie
        typedef struct node
        {
            bool is_word;
            struct node* children[27];
        }
        node;

    // create root node
        node root;

    // create node to traverse through the trie with
        node trav;

    // create pointer to root
        node* rootptr = &root;

    // create global word count for dictionary file
        int count = 0;

    bool check(const char *word)
    {
        // set traversal node to root node
        trav = root;

        // set count
        int counter = 0;

        // for each letter in input word
        while (word[counter] != EOF)
        {
            // keep track of text characters
            int c = word[counter];

            // convert text characters into alphabetic numbers corresponding to elements in children
            if (islower(c))
            {
                c -= 97;
            }

            else if (isupper(c))
            {
                c -= 65;
            }

            // go to corresponding element in children; if NULL, word is misspelled
            if (trav.children[c] == NULL)
            {
                return false;
                counter++;
            }

            // if not NULL, move to next letter
            else
            {
                trav = *trav.children[c];
                counter++;
            }

            // once at end of input word, check if is_word is true
            if (c == '\n')
            {
                if (trav.is_word == true)
                {
                    return true;
                }
                else return false;
            }
        }

        return false;
    }

    /**
     * Loads dictionary into memory. Returns true if successful else false.
     */
    bool load(const char* dictionary)
    {
        // set traversal node equal to root
        trav = root;

        // create count
        int c = 0;

        // open dictionary
        FILE *dict = fopen(dictionary, "r");
        if (dict == NULL)
        {
            printf("Could not open %s.\n", dictionary);
            unload();
            return 1;
        }

        // for every dictionary word, iterate through the trie
        while (c != EOF)
        {
            // keep track of dictionary characters
            int c = fgetc(dict);

            // each element in children corresponds to a different letter
            if (isalpha(c) && islower(c))
            {
                c -= 97;
            }
            else if (isalpha(c) && isupper(c))
            {
                c -= 65;
            }

            // check the value at children[c]; if NULL, malloc a new node, have children[c] point to it
            if (trav.children[c] == NULL)
            {
                trav.children[c] = malloc(sizeof(node));
            }

            // if not NULL, move to new node and continue
            else trav = *trav.children[c];

            // if at end of word, set is_word to true
            if (c == '\n')
            {
                trav.is_word = true;
                count++;
            }
        }

        // close dictionary file after loading
        fclose(dict);
        return false;
    }

    /**
     * Returns number of words in dictionary if loaded else 0 if not yet loaded.
     */
    unsigned int size(void)
    {
        // return count if there is one
        if (count > 0)
        {
            return count;
        }
        else return 0;
    }

    /**
     * Unloads dictionary from memory. Returns true if successful else false.
     */
    bool unload(void)
    {
        // create a tracker for filled nodes
        int tracker = 1;

        // point traversal node to root node
        trav = *rootptr;

        // check children
        while (tracker != 0)
        {
            for (int i = 0; i < 27; i++)
            {
                // free empty nodes and point back to root
                if (trav.children[i] == NULL)
                {

                    free(&trav);
                    trav = *rootptr;
                }
                else

                // go to filled nodes and reset inner loop through children
                {
                    trav = *trav.children[i];
                    i = 0;
                }

                // if root has been emptied, end outer loop
                if (rootptr == NULL)
                tracker = 0;
            }
        }

        return false;
    }
1

It's really a simple problem, but you're probably looking for it in all the wrong places. ;-)

Think about what happens when the code reaches the end of the dictionary, paying special attention to when the EOF condition is detected. The while loop checks for EOF to terminate. The problem lies in precisely when that happens. When the last word is read, the pointer moves to the location just after the last char. The problem is that EOF isn't detected until an attempt is made to read past the end of the file. A good analogy is this (no disparagement intended) - a blind person walks to the end of a diving board. He doesn't know he's at the end until he takes one more step and falls into the water. The logic of this code is the same. Until that last read is made, it doesn't know that it has reached EOF.

The consequence of this is that the code will check for EOF, not find it, and then will attempt a read past the end of the file, and will continue processing it. Since the content is unpredictable, you usually get a seg fault. The code needs to process the EOF after the read, but before trying to process the data retrieved.

There are more issues to follow, but you probably haven't had a chance to investigate them. I'll give you a freebie though. What do you think happens after the code successfully processes the dictionary, but hits the return false statement at the end?

Give it another "trie". ;-) Happy coding!

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

2
  • Cliff, again, you’re the man 🙌. MANY thanks.Your analogy made perfect sense. No disparagement taken, although I feel not only blind but also deaf and dumb too, at this point hah. I swapped 'fget(dict)' in place of 'c' in the while loop, so that the code is reading and checking the data before processing it. Seems to have done the trick, although now I’m faced with my program not reading (outputting?) the last word in the text file, marking all words as misspelled, and then failing to unload the dictionary file. Basically, my program doesn’t work at all, but at least it’s not seg faulting 😅 – Foxhole Sep 4 '17 at 23:36
  • Well, at least you're making progress. ;-) The good news is that you've discovered that implementing the read in the while loop setup is the way to go. – Cliff B Sep 4 '17 at 23:39

You must log in to answer this question.

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