0

I am using tries to complete the spellcheck but I just can't keep up with the logic. I've implemented load() and check() as much as I could but I'm sure it has some logic flaw. The unload() function is a mess; I don't know how it works. The walkthorughs told me nothing about the size(), so that's not going to be completed anytime soon. I also have no idea how to travel through the tries -- how to go from one letter to the next.

I've watched all the shorts and walkthroughs more than once. Over two weeks now and it's getting very annoying and boring since I don't have a solid understanding of its logic.

If someone could guide me from here and perhaps maybe give me some hints, I would appreciate it. I have really hit a wall here. Anything would be helpful. Thanks.

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

#include <stdbool.h>
#include <stdio.h>

#include "dictionary.h"

// create a variable to count number of words loaded
int wordCounter = 0;

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

// create root for starting point
node *root = malloc(sizeof(node));
if (root == NULL)
{
    unload();
    return false;
}

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

    // iterate through letters in word
    for (int i = 0, x < strlen(word2); i < x; i++)
    {
        // calculate the letter placement
        if (isalpha(word2[i]))
        {
            int placement = tolower(word2[i]) - 97;
        }
        else if (word2[i] == '\'')
        {
            int placement = 26;
        }

        // check for misspelled word first
        if (cursor->children[i] == NULL)
        {
            printf("Misspelled word.\n");
            return false;
        }
        // otherwise move to next letter
        else
        {
            cursor = cursor->children[placement];
        }
    }
    // check if that word exists once done iterating
    if (cursor->is_word == true)
    {
        return true;
    }

    return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    // open dictionary
    FILE *openDictionary = fopen(dictionary, "r");
    if (openDictionary == NULL)
    {
        fprintf(stderr, "Could not open Dictionary.\n");
        return false;
    }

    // the longest word (45 chars) + 1 char for null terminator
    char word[46];

    /*
    * scan dictionary word by word
    */
    while (fscanf(openDictionary, "%s", word) != EOF)
    {
        // iterate through the characters of the source word
        for (int i = 0, x = strlen(word); i < x; i++)
        {
            // calculate the place in child to place the chararcter
            if (isalpha(word[i]))
            {
                int placeChild = tolower(word[i]) - 97;
            }
            else if (word[i] == '\'')
            {
                int placeChild = 26;
            }

            // there's no character in the root child
            if (root->children[placeChild] == NULL)
            {
                // malloc a node * for the new character
                node *new_node = malloc(sizeof(node));
                if (new_node == NULL)
                {
                    unload();
                    return false;
                }

                // add character from source to the new child
                strcat(new_node->children[placeChild], tolower(word[i]));

                // make the latest linked child point to the new node *
                root->children[placeChild] = new_node;

                // move to that child
                root = root->children[placeChild];
            }
            // if there's already a character in array of trie
            else
            {
                // move to next child
                root = root->children[placeChild];
            }
        }
        // mark character as word's final letter
        new_node->is_word = true;

        // increment word counter
        wordCounter++;
    }
    // dictionary sucessfuly loaded
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    // the counter has had some variable change (denotes the running of load())
    if (wordCounter > 0)
    {
        return wordCounter;
    }
    // load() has not yet been loaded (based on counter variable change)
    else
    {
        return 0;
    }
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    node *cursor =  root;
    while (cursor != NULL)
    {
        node *tmp = cursor;
        cursor = cursor->next;
        free(tmp);
    }

    // unload unsuccessful
    return false;
}
1

sizeof(word2) will give you the size of a pointer on your system, in bytes, most likely 8 for a 64 bit system. You probably meant strlen(word2). The comparison makes no sense in the initialisation part of the for loop, I would expect something like int i = 0, x = strlen(word2); i < x; i++.

atoi is used to parse a string that contains characters forming a human-readable integer. char itself is already an integer of 8 bit (could be more, but all systems I am aware of do use 8 bit).

You don't treat the apostrophe ' in any way. It should be considered part of a word like any letter.

root should not be used as a cursor, but stay the same all the time, as it's the root of the tree, and if you lose its value, you won't be able to go back. Use a different (function-local) variable to walk the tree. Applies to all functions.

It's weird that you define your node structure in a function. Place the definition on top, over all the functions.

malloced memory initially contains arbitrary values. Either initialise the structure, or use for example calloc, which writes zeroes into the memory.

In load, again use strlen, not sizeof.

I don't see where you declared word, but it should contain enough memory, for example by being declared as char word[LENGTH+1]; (+1 for the null terminator).

strcpy is not to be used with nodes or characters, it has no place in the whole function.

Now I'm confused. Up to this point, I was convinced you tried to implement a trie. strcpy is something you would use for a linked list. And your unload also seems to assume a single linked list.

So which one do you try to implement? I think the usual choices are hashmap (an array of linked lists) or a trie.

(btw, size can just return the number of words added in load, use a global counter variable for that)

| improve this answer | |
  • I updated the code as much as I could. I don't think I'm treating ' any different from other letters. I'm just assigning it to the end of the array of root. I created a different node for root on check() but I don't really know what to change on load(). In psets up until now I haven't heard about the value of malloc. What difference would it make to initialize it? I replaced strcpy with strcat. My aim is to assign the char from the source word to the new node. I am trying to implement tries. unload() is a mess. I just copied the code from the walkthrough. – stackedbooks Sep 4 '17 at 13:55
  • In a trie, the word is not stored in the node, it is encoded in the position of the node within the trie. So the word "the" would be found at node root->children[19]->children[7]->children[4]. The ' needs special treatment as you probably want to map it to index 26, and not '\''-'a'. new_node makes no sense in check. – Blauelf Sep 4 '17 at 14:07
  • I have not used '\''-'a' for '. I have simply put it to the last place of the array, before the null terminator and after all the alphabetic letters (which is 26). I fixed new_node in check(). – stackedbooks Sep 4 '17 at 14:59
  • In check, there is no test for '! – Blauelf Sep 4 '17 at 15:09
  • And have a global variable root that you assign to exactly once at the beginning of load. Do not have other variables root. Do not assign to root again. strcat makes as little sense as strcpy does. Both are meant to operate on strings. – Blauelf Sep 4 '17 at 15:12

You must log in to answer this question.

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