PSET5: Trying to implement dictionary.c using trie. But segmentation fault in check()

Question

My implementation compiles but I am getting a segmentation fault when I execute. My program is working fine through the load function because the output screen shows this

"~/pset5/speller/ $ ./speller texts/lalaland.txt

MISSPELLED WORDS

Segmentation fault"

Here is my code is attached below. When I use the debugger, the first word it is checking is "LA" and I noticed that my trie pointer trav's value doesn't become &root. The segmentation fault happens right when it enters the following line: int test = strcasecmp(trav->word, word)

I am not sure what is going wrong. I sat with paper and traced the code and can't seem to figure out where I am going wrong. Any help is greatly appreciated.

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <strings.h>

#include "dictionary.h"

// Represents a node in a hash table
typedef struct trie
{
    char word[LENGTH + 1];
    struct trie *paths[27];
}
trie;


// Number of words in dictionary
unsigned int words = 0;

// Hash table
// node *table[N];
//
trie root;

// Returns true if word is in dictionary else false
bool check(const char *word)
{

        int i = 0;

        trie *trav = &root;
        int letterVal;
        while (word[i] != '\0')
        {
            letterVal = word[i];

            if (letterVal >= 65 && letterVal <= 90)
            {
                letterVal = letterVal + 32;
            }


            if (letterVal == 39)
            {
                trav = trav->paths[26];
            }
            else
            {
                trav = trav->paths[letterVal - 97];
            }

            if (word[i+1] == '\0')
            {
                int test = strcasecmp(trav->word, word);
                if (test == 0)
                {
                    return true;
                }
            }

            i++;
        }

        return false;



}

// Will not be using this function as I am not using a hash table and trying to solve the same problem with a Trie.
unsigned int hash(const char *word)
{
    return 0;
}




// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    char str[LENGTH + 1];

    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        // Could not load dictionary, return false.
        return false;
    }


    while (fscanf(dict, "%s", str) != EOF)
    {
        int i = 0;

        trie *trav = &root;
        while (str[i] != '\0')
        {
            trie *n = malloc(sizeof(trie));

            if (n == NULL)
            {
                printf("Error allocating memory for new node");
                return false;
            }

            // ASCII for apostrophe( ' ) is 39. If theres ever an apoptrophe go down last path, path 26.
            if (str[i] == 39)
            {
                trav->paths[26] = n;
            }
            // Else if it is a lower case letter, subtract 97 from it go get array value. ie; a = 97, so 97 - 97 = 0. 
            // So go down paths[0]. The words will always be in lower case in the dictionaries per the directions.

            else
            {
                trav->paths[str[i] - 97] = n;
            }

            trav = n;
            // If we are on the character right before the terminal character "\0", copy str into trav->word
            if (str[i+1] == '\0')
            {
                strcpy(trav->word, str);
                words++;
            }
            i++;
        }
    }

    fclose(dict);
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    return words;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TO DO
    return false;

}

Answer 1

One question: is trav null at that point? If it is, trav->word doesn't exist. That will cause a seg fault.

Kudos for trying to do a trie, but this isn't that. A trie uses a node structure that records the address of the next node and a flag that says whether the current node is the end of a word, i.e., isWord. Nowhere does this code mark the end of a word in the trie. Finally, it does not have a copy of the word because certain words can follow the same path, at least part of the way. Which word would you write in the node??? Think about that and the words cab, car, cat, cater, caterpillar, cats, and so on.

Further, storing the word in a node isn't needed in a trie. The index of the node (0 to 26) maps to the letter, i.e., 0 is for a or A. By extension, there's no need or reason to do a strcasecmp.

Also, keep in mind that with a trie, it's possible to go off the end of a branch. For example, say you had a 1 word dictionary with the word "cat" and you were checking the word "cater". After the "t" node, the code is looking for an "e" node in the trie, but it doesn't exist. There needs to be code to handle this. (It would mean that the word is misspelled.)

Keep at it though, but go back and review the material on how to construct a trie.

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