5

Before posting, I've searched a lot here and there on the Internet to find the answers to my questions myself and I did code something that eventually works.

My issue is that I've re-rewrote some parts of my code based on working bits of code I've found to debug my program, I totally understand some of them while some others are still mysterious to me.

Here are the two I can't figure out how their logic works.

1. The trie logic

So here's my struct for the trie I've used for this pset:

//dictionary.h

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

I think nearly everybody coding a trie for this pset wrote this down as CS50's walkthrough gave this clue.

In dictionary.c, I use this struct as it follows:

if (isalpha(letter))
{
    if (newptr->children[letter - 'a'] == NULL)
    {
        newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
    }
    newptr = newptr->children[letter - 'a'];
}

Before this part of the code, here's my pseudo:

GLOBAL VARIABLE
create a node* called "root"

------------------------------------------------------------------------------

bool load(const char* dictionary)

open and read dictionary

malloc space memory for the root node
get each character in the dictionary

put the caracter in a "word" array and get to the next character
repeat this until the end of the word

  if the word is finished
  add \n to the last slot of the array "word"

  create a node* called "newptr" to be equal to "root".

    for each character written in "word" array
    char "letter" equals the ith letter of the array "word"

    if (isalpha(letter))
    {
        if (newptr->children[letter - 'a'] == NULL)
        {
            newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
        }
        newptr = newptr->children[letter - 'a'];
    }

My code checks here if it's a letter or something else (could be an apostrophe or the end of the word) and then check

newptr->children[letter - 'a'] 

is NULL.

If it is, I allocate enough space memory (size of a node) to

newptr->children[letter - 'a'].

In my head, here's what I visualize:

Step 1 : creation of a node* called "root".
Step 2 : chunk of memory of size of a node allocated to "root". 
Step 3 : creation of a node* called "newptr" equals to "root".

Pause : inside "newptr", there are two parts

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[27];
        where in children[27] no slot of the array has been filled so far.

Step 4 : checking if the ith position in the children array is filled with a character. 
         NULL: we give to children[27] a chunck of memory of size node.

Pause : we have now "newptr" to look like this

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[27];

                Inside children[27] of "newptr" we have now room for a new node unnamed yet:

                UNNAMED
                Part 1: bool is_word;
                Part 2: struct node* children[27];

Step 5 : "newptr" node is equal to the children[ith] of "newptr" node.

Pause : How does look "newptr" now? Assume "letter" is a 'b' so we have 'b' - 'a' = 98 - 97 = 1.

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[1];
                UNNAMED
                Part 1: bool is_word;
                Part 2: struct node* children[27];

Step 6 : Next letter is a 'i', we start a new loop.
         Checking if the ith position in the children array is filled with a character.
         NULL: we give to children[27] a chunck of memory of size node.

Pause : Visualization of the node "newptr":

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[1];
                UNNAMED
                Part 1: bool is_word;
                Part 2: struct node* children[27];

                        Inside children[27] of "unnamed" we have now room for a new node also unnamed yet: 

                        UNNAMED
                        Part 1: bool is_word;
                        Part 2: struct node* children[27];

Step 7 : "newptr" node is equal to the children[ith] of "newptr" node.

Pause : How does look "newptr" now? We assumed "letter" is now 'i' so we have 'i' - 'a' = 105 - 97 = 8.

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[1];
                UNNAMED
                Part 1: bool is_word;
                Part 2: struct node* children[8];
                        UNNAMED
                        Part 1: bool is_word;
                        Part 2: struct node* children[27];

To be fair, this last representation of the three nodes connected to each others doesn't make sense to me. In my code, I don't create new nodes, I only work with the "newptr" node. That makes sense to me for the first node where I assigned the letter 'b' but then, how can I connect this first node to the second for the letter 'i'?

I'm visualizing something like this:

First iteration for the 'b' letter:

NEWPTR
Part 1: bool is_word;
Part 2: struct node* children[1];

Second iteration for the 'i' letter:

NEWPTR
Part 1: bool is_word;
Part 2: struct node* children[8];

instead of

NEWPTR
Part 1: bool is_word;
Part 2: struct node* children[1];
        UNNAMED
        Part 1: bool is_word;
        Part 2: struct node* children[8];

In my mind, there's is a missing

struct node* next;

to connect nodes between each others as we've seen it with the linked list and the programs list-0.c and list-1.c of week 5's second lecture.

How can

struct node* children[27];

can point to the next node?

To me, I can't see how can I link two nodes without declaring a node* "next" in the struct

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

To be able then to connect nodes like this:

node* root = (struct node*) malloc(sizeof(node));
node* newptr = (struct node*) malloc(sizeof(node));
newptr->next = NULL;
if (root == NULL)
    root = newptr;
newptr->children['b' - 'a'] = 'b';
node* newptr2 = (struct node*) malloc(sizeof(node));
nexptr->next = newptr2;
newptr2->children['i' - 'a'] = 'i';

When I read

newptr = newptr->children[letter - 'a'];

I guess it's all about recursion but I can't figure out it works step by step.

2. Assigning "letter" to the children[index]

I go back to this chunck of code:

if (isalpha(letter))
{
    if (newptr->children[letter - 'a'] == NULL)
    {
        newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
    }
    newptr = newptr->children[letter - 'a'];
}

and take again the example of the first iteration with "letter" is 'b'.

I do the math at the line

newptr->children[letter - 'a'] == NULL

and find this

newptr->children[98 - 97] == NULL

so

newptr->children[1] == NULL

In this case, it is NULL as nothing is written in the children array. I allocate memory space size of a node to be able to write 'b' at the 2nd position of the children array.

Then, this happens (again):

newptr = newptr->children[1];

How do I know letter 'b' is equals to newptr->children1 ?

Here again in my mind, I'd have imagined more something like this:

letter = newptr->children[1];

When I try to figure this out, I wonder: "When did I store 'b' in "newptr" ?" Because if "newptr" hasn't 'b' stored inside itself, how newptr->children1 can successfully be linked to 'b'?

When I first tried to write this code, the first thing I've written as a global variable was a const char "alphabet" array of size 27 containing the 26 letters and alphabet[26] = '\''

I was thinking that as soon as I've calculated the index of the "children" array, I'll use this same index to map the "alphabet" array and see what letter is stored at the given position to copy it to children[index].

I've never found a correct way to code that and found instead a working bit of code with this method... that I still doesn't get.

3. Conclusion

Long post short (if you've read everything so far, thanks for your time!), this one single line of code is driving me really mad:

newptr = newptr->children[letter - 'a'];

I can feel there's a recursive trick underneath the hood but I can't draw it step by step on a piece of paper.

When I'm stuck, my method is to find a bit of working code somewhere on the internet, comment it line after line to get everything and then re-write the code with my own logic and variable names.

That's what I've done for instance to understand the linked list: I've completely commented code sheets of list-0.c and list-1.c to understand how nodes dynamically behave (insertion, sorting, deletion, etc).

But here, even after fully understanding how linked lists work, I can figure out what's going on in this trie and how it works.

If you have understood my logical issues and got where I'm thinking wrong, please tell me! Thanks.

# EDIT 1 #

I've just watched this video (I shouldn't skip sometimes Zamyla's walkthrough videos...)

Pset 5 Walthrough: Load

When she takes the "fox" example, here's her logic:

f: root->children[5];
o: root->children[5]->children[15]
x: root->children[5]->children[15]->children[23]

Alright, this can make sense to me and I start getting why a

struct node* next;

as used in linked lists is not necessary.

But the question remains: how

newptr (or "root" for Zamyla) = newptr->children[5];

then

newptr = newptr->children[15];

can be equal to

newptr = newptr->children[5]->children[15];

and finally

newptr = newptr->children[23];

can be equal to

newptr = newptr->children[5]->children[15]->children[23];

?

Could someone please explain me how recursion works here? Meanwhile, I'm heading back to my books to read chapters on that topic. If I find anything, I'll post a second edit. Thanks!

# EDIT 2 #

I'VE GOT IT!

Recursion is really tricky but now I see.

Here's my explanation and please, if someone can just say "yes it's correct", it'd lift a weight off my shoulders.

So let's take again Zamyla's fox example (see Edit 1).

Letter after letter, it works like this:

f: root->children[5];
o: root->children[5]->children[15]
x: root->children[5]->children[15]->children[23]

In a code form, using recursion, we write this:

f: root = root->children[5];
o: root = root->children[15];
x: root = root->children[23];

Alright, first loop for 'f' is easy to get: we ask to update itself by assigning the letter 'f' to its pointer children[5].

That means now that root stands for root->children[5].

Let's move on 'o' and compare Zamyla's path to ours:

Zamyla
o: root->children[5]->children[15]

Us
o: root = root->children[15];

At first sight, the part for 'f' is gone in our version. When we think back, we said that root was a shortcut for root->children[5] meaning that we can replace root in our code like this:

root = root->children[5]
^^^^   *****************

o: root = root->children[15]
          ^^^^
        = root->children[5]->children[15]
          *****************

and now root stands for root->children[5]->children[15]

Last recursion for 'x':

root = root->children[5]->children[15]
^^^^   *******************************

x: root = root->children[23]
          ^^^^
        = root->children[5]->children[15]->children[23]
          *******************************

Now, root stands for root->children[5]->children[15]->children[23], the three nodes of "fox".

I should have been more mathematical to understand how recursion was working. As soon as you replace the name root its value, everything makes sense!

I hope this will eventually help someone else.

# FINAL EDIT #

Here again, we're taking Zamyla's "fox" example:

f: root->children[5];

and we compare this logic to this chunck of code:

if (isalpha(letter))
{
    if (newptr->children[letter - 'a'] == NULL)
    {
        newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
    }
    newptr = newptr->children[letter - 'a'];
}

OK so let's pass the letter 'f'. First, the if condition: is 'f' a letter? Yes it is so let's go inside. When we do the math, we find that

newptr->children[letter - 'a']
=
newptr->children[5]

We allocate memory space to the pointer children[5] of its size: node.

Once there, we have this:

newptr = newptr->children[5];

First of all, Cliff B mentionned in a post below something very important: for the first node, we need a root for our trie. If we lose the first node of the trie, we lose everything!

To avoid such a disaster, it's important to save this first node, let's call it "root" here and then, only use one temporary pointer, "newptr", to build the trie. To be sure to not meet any problem with our trie, let's amend this line of code:

newptr = root->children[5];

Alright so now let's figure out why root->children[5] refers to 'f' even if 'f' or letter is not explicitly mentionned in this line of code.

Well, here's my tip to help yourself with pointer (at least in this case, pointers are tricky).

children[5] is a pointer of type node* and that's why we use a -> instead of a .. So at the end, after making sure 'f' is a letter and we have allocated enough memory space, we end up with this result: "newptr" can be found at this address: root->children[5].

Let's take now the process backward and assume that we read the result first: newptr = root->children[5]. How we made it to that result? Maybe we needed to allocate memory space, maybe not. But there's one thing that is absolutely unavoidable to get to this result: the if condition must verify that letter is a 'f' and not any other letter.

As we use the same mathematical method to find the index of "children", index 5 can only refers to 'f'. If we pass a number in the if condition, the condition is not verified and no node will be created. If we pass the letter 'c', we'll do the math and find out that children's index is 2. Every single argument that pass successfully the if condition will get one unique index, from 0 to 26.

That's how now I consider the logic: instead of looking for where 'f' has been told to be assigned to root->children[5], better understand how root->children[5] made it to exist.

I think my explanation isn't a top answer but still, I hope it'll help someone who one day lost him/herself in this same logical maze.

  • +1 for the really detailed question and the exact specifications. – ChrisG Aug 18 '15 at 21:31
  • Hey thanks @ChrisG! – DFATPUNK Aug 18 '15 at 22:34
6

Your understanding is correct, but your example has a dangerous flaw if you were to implement it. Look back at your question as a whole. You have two important variables, root and newptr. root is the pointer that actually points to, well, the literal root of the trie. It's critical that you never reassign this pointer. If you do, you'll lose the root of the trie!

Next, newptr is another pointer to nodes. It can be set to point to root or to any other node in the trie! This is your floater, your temoporary pointer that will let you traverse down the tree to either load or check for a word. In your Edit #2, you'd use it like this:

f: newptr = root->children[5];       
o: newptr = newptr->children[15];   // = root->children[5]->children[15]
x: newptr = newptr->children[23];   // = root->children[5]->children[15]->children[23]

So, you use a temporary pointer, such as newptr, to traverse along the trie while maintaining root as the permanent starting point.

BTW, your very detailed explanation looked fine to me, with one exception. In your pseudocode, you mentioned adding '\n' to the end of the string that holds the word you just got from the dictionary file, one character at a time. However, you made no mention of adding an end of string marker, \0 to the end of the string. Also, what purpose will inserting the '\n' into the string serve?

So, yes, you've pretty much got it. ;-)

| improve this answer | |
  • Pset5 says : "From top to bottom, the file is sorted lexicographically, with only one word per line (each of which ends with \n).". From that statement, I check for this '\n' to know when a word is over and turn bool is_word on TRUE in the load function of dictionary.c. However, when it comes to the check function, I've implemented a while loop with the condition (word[index] != 0) to spell and check the word and once the loop's over, I check the if condition (bool is_word == TRUE) given by '\n' in the load function. If I modify '\n' by '\0' in the load function, I get a seg fault. – DFATPUNK Aug 18 '15 at 22:48
  • I forgot to thank you for you reply, I totally get what you mean about the root, that makes a lot of sense and I'm going to modify my code right now about that, thanks! Do you have a clue about my second concern? How do we know, if I take your bit of code in your answer, how root->children[5] can be assign to 'f'? Why not coding root->children[5] = 'f' for instance? – DFATPUNK Aug 18 '15 at 22:55
  • It takes some getting used to. There's no need to assign 'f' to it because it is a pointer, not a char. Think about it. root[5] represents 'f', so it doesn't really need to have the letter stored there. The idea of the trie is to store a chain of nodes that represent words in order to get to the end of the chain and see if it's marked as the end of a word. So, when you want to check if 'to' is a word, you go to the node in root for t, and then the node for o pointed to by the t node, and finally check the flag to see if it's a word. You never actually check if a letter is stored anywhere. – Cliff B Aug 19 '15 at 2:15
  • I'm totally aware that children[5] is pointer of type node but what indicates us that this pointer is actually pointing to 'f'? if (isalpha(letter)) // letter = 'f' { if (newptr->children[5] == NULL) { newptr->children[5] = (struct node*) malloc(sizeof(node)); } newptr = newptr->children[5]; } letter 'f' is indeed a letter so malloc memory space size node children[5]. But then, where in newptr = newptr->children[5] we can see that it effectively points to 'f'? Do you see what I mean @Cliff B? – DFATPUNK Aug 19 '15 at 14:24
  • Yes, I see what you mean. What I'm saying is that it isn't necessary. [5] points at 'f' simply by definition. For any given node, 0 is a, 1 is b, and so on. Once the program is written, no human is looking at it and the computer doesn't care. If you really wanted to, you could add an extra char element to the structure to store the letter, but it would be totally unnecessary. – Cliff B Aug 19 '15 at 16:28

You must log in to answer this question.

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