0

I am working on "speller.c", and I think I understand the basic concept of trie data structure. But I can barely translate my idea into C language. So here is what I coded with my understanding of this question. Basically, there is a dictionary you need to load into a trie structure. The staff already write most of the code, all we need to do is to insert words.

Here is my code, and I write my thoughts in it. I am hoping someone may understand my thoughts and maybe point out the incorrect part, most importantly give me some hint of how to translate my idea into C language.

bool load(const char *dictionary)
{
    // Initialize trie
    root = malloc(sizeof(node));
    if (root == NULL)
    {
        return false;
    }
    root->is_word = false;
    for (int i = 0; i < N; i++)
    {
        root->children[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];


    // Insert words into trie
    while (fscanf(file, "%s", word) != EOF)
    {
        // TODO
        // for every letter in the word from file pointer
        for (int i = 0, n = strlen(word); i < n; i++)
        {
            // create space for later use
            next_root = malloc(sizeof(node));
            if (next_root == NULL)
            {
                return false;
            }
            next_root->is_word = false;
            for (int i = 0; i < N; i++)
            {
                next_root->children[i] = NULL;
            }

            // to my understanding "word" is a string 
            // I'd like it to be number so that I can use to iterate in children
            // ex. a = 0, b = 1, c = 2..., z = 25, '\' = 26; totally 27 numbers
            int idofletter = word[i];

            // so if the id of the i th letter in word
            // turns out in children[id] is a NULL
            // which means that letter has never been added to the trie
            if (children[idofletter] == NULL)
            {
                // so here I point the pointer of the root to children[id] array
                // and point the pointer of the array(children[i]) to next_root
                // then make it NULL
                root -> children[idofletter];
                children[idofletter] -> next_root = NULL
            }

            // if it is not NULL
            // simply point the pointer of the root to children[id]
            // and then follow the pointer
            else
            {
                root -> children[idofletter];
                children[idofletter] -> next_root;

            }

            // when it comes to end of the words
            // the i th letter will be '\0'
            if (word[i] == '\0')
            {
                // turn the bool is_word to true
                // letting later fuction knows it is a word
                root -> is_word = true;
            }
        }
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}
  • No. Basically, you'll have to implement the check-function (and the size-function). The check function should be as fast as possible. And to make it work, you'll have to build a load-function and an unload-function. The staff has built (or will build) some application which uses the helper module you'll build. The staff has already defined the interface, that is the part of helper.c which is already there. But you have to implement it. – Peter Pesch Oct 13 '18 at 4:19
  • This means that you should not call unload within your module; The application will take care of that. – Peter Pesch Oct 13 '18 at 4:21
  • And of course: It is impossible for us to help you "translate your idea into C" if you don't tell us what your idea is. Please DO tell us your idea. – Peter Pesch Oct 13 '18 at 4:27
0

Please do remember that the lecture video shows several data structures which could handle this. The Trie is the most difficult one to implement ...


Let's start with your inner loop, and assume that word points to a string containing one word.

Basically, you'll want to add the word in your data structure, unless the word has already been added earlier.

    // for every letter in the word from file pointer
    for (int i = 0, n = strlen(word); i < n; i++)
    {
        // create space for later use
        next_root = malloc(sizeof(node));
        if (next_root == NULL)
        {
            return false;
        }
        next_root->is_word = false;
        for (int i = 0; i < N; i++)
        {
            next_root->children[i] = NULL;
        }
        ...
    }

That doesn't work. Your code will create a node for every letter it reads. In most cases you will not need that node, so this will lead to lots of memory leaks ...


And further on in your code:

        // to my understanding "word" is a string 
        // I'd like it to be number so that I can use to iterate in children
        // ex. a = 0, b = 1, c = 2..., z = 25, '\' = 26; totally 27 numbers
        int idofletter = word[i];

That doesn't work either.

If you want to convert a (and A) to 0, you will have to code (program) those conversions. Now you'll probably end up with 97 or 65 in stead of 0, which will probably lead to segmentation faults, or worse.


Looking at the amount of errors I see before even looking at the algorithm, I would advise you to try one of the easier algorithm's first. You'll encounter most of these same problems there, and you will be able to concentrate on solving them without having to think about the data structure.

Once you've got that working, you can always make a backup and try to change it into a version which uses a more difficult algorithm. You'll find that you can reuse much of the code ...


Finally, to quote Cliff B:

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

| improve this answer | |

You must log in to answer this question.

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