CS50,pset5,load ()

Question

While implementing TRIES in the load(),there is an array of node* pointing to other arrays and so on.Then where the letter if encountered will go because the only other structure member is_bool,there is no field for the character.Answer please

Answer 1

There's no place to put the letter because it isn't necessary. The node represents the character indirectly. Look at the structure definition:

typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

node* root;

To add a word, say "cat" you start at the root node, which doesn't represent any letter. From there, you go to the node that represents "c", which would be root->children[2] because a is 0, b is 1 and c is 2. From there, you go to the node under the c node that represents "a", or root->children[2]->children[0]. From there, you go to the "t" node, or root->children[2]->children[0]->children[19]. Now that you've found that node, are you loading or checking? IF you're loading, then you would set the value of the bool variable root->children[2]->children[0]->children[19]->is_word to true. If you're in check() then you look to see if this is the end of the word by checking whether is_word is true.

The chain of pointers may look a bit intimidating, but that's easily dealt with. As you traverse the trie, you can use a variable to walk through it. You could do something like node* nodeptr = root; to start and then reassign it as you go, with something like nodeptr = nodeptr->children[letter - 'a']. But I'll leave it to you to design the code.

This should get you started. If you still don't understand, perhaps a review of the class lecture and short videos will help.

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