0

I'm currently on pset6 and I'm thinking of using a trie to store the words from the dictionary we're given.

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

node* root;

From the declaration of the node* root, I don't get how root itself can store a letter from the alphabet as shown below:

enter image description here


Shouldn't the case be something like this? (Assuming there are 27 boxes there):
enter image description here


Help would be greatly appreciated!

1

The root of a trie should be an array of node pointers. And the nodes do not store characters. Rather, the index of a node in an array determines which character this node represents.

For example, root[0] could represent the char 'A' as the first char of a word. root[0]->children[25] represents the char 'Z' as the second char of a word preceded by 'A' and so on.

10
  • In that case, then why is root a node* instead of node? – user1742 Dec 4 '14 at 6:04
  • @user1742 because the member named children has to be an array of node *s. So for the sake of consistency the root array should be an array of pointers either. That would make it easier since you wouldn't have to handle the insertion/checking of the first character differently. – kzidane Dec 4 '14 at 11:06
  • So does that mean you only need to use "->" instead of "." ? (With regards to your last sentence) – user1742 Dec 5 '14 at 15:41
  • @user1742 if you're gonna deal with pointers, then you could access a member m of a struct that's pointed to by the pointer p using p->m! – kzidane Dec 5 '14 at 17:01
  • 1
    @user1742 you probably may watch section 7 in order to get the hang of dealing with pointers! – kzidane Dec 6 '14 at 14:58

You must log in to answer this question.

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