Try to use trie in pset5

Question

I know if I want to use trie in pset5 to load the dictionary, there should be a struct containing an array of pointers for the alphabets or the apostrophe and a variable of bool. The question is, should I let the array point to NULL when I define the struct in the beginning? (Since we might use NULL to check if we reach the end of the word...).

Thanks!

Answer 1

You can do it. It's a good practice to initialize the values to something, NULL in this case, to prevent any garbage value remaining in the memory from messing with the execution of the code.

I don't know for sure but I think you can't do this in the declaration of the struct, you can implement a function to do that, or since probably you are going to create the trie inside a function by allocating memory on the heap, you can use calloc() instead of malloc().

Here is a short explanation of what calloc() does:

The C library function void *calloc(size_t nitems, size_t size) allocates the requested memory and returns a pointer to it. The difference in malloc and calloc is that malloc does not set the memory to zero whereas calloc sets allocated memory to zero.

EDIT:

According with your struct definition:

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

First you need to create a root struct_node where all the words will begin. You can do it with a pointer, this way:

node* root = calloc(1, sizeof(node));

To make it simple, I am going to use the word "foo" as example.

To store this word first start with the letter "f", since this is the letter number 6 in the alphabet but usually we start counting at 0 I am going to assign to it the index 5, this is arbitrary. Then in the root node if the *arr[5] element is NULL (at this moment arr[5] contains NULL since the node has been created with calloc()) you indicate that there is a word starting with the letter indexed 5 ("f" in this case) creating another node to continue to the next letter, and store in arr[5] a pointer to it, you can do it with a line like this:

root->arr[5] = calloc(1, sizeof(node));

Then in this new node you just created do the same for the next letter ("o" in this case) you can use index 14 to continue with the same convention, if arr[14] is NULL create another node and store the pointer to it in this index. Repeat the same for the last "o". Now you have a structure like this:

• The element root->arr[5] is pointing to another node, lets call it node_1
• The element node_1->arr[14] is pointing to another node, lets call it node_2
• The element node_2->arr[14] is pointing to another node, lets call it node_3

And to indicate that a word ends you only have to set the boolean value in the last node to true (notice that at this moment, since the the node has been created with calloc(), the value of is_word is false):

node_3->is_word = true;

Notice that we are checking if the current letter index is NULL, if is not NULL this means that already exists a node in that index and you don't need to create a new one, you just jump to that node and continue with the next letter. That is why calloc() can be useful in this situation.

You'll have to find the way to move between nodes by looping through the characters of a word. Probably a good way is an auxiliary pointer, just to keep track of the position. I am not going to explain this here, otherwise I am going to spoil a big part of the solution to the problem set.

Answer 2

should I let the array point to NULL when I define the struct in the beginning?

If your struct definition looks like this

struct node
{
    struct node *arr[27];
};

then you actually can't assign a value to arr. And I don't actually recommend having arr declared as a pointer then allocating memory for it on the heap since if you do that you'll need to allocate memory for 27 pointers then allocate memory for each of these pointer as the corresponding char is inserted into this place which would unnecessarily complicate things.

The second thing is that the boolean member is important because if you marked the end of a word by checking whether the elements of the array that is a member of a struct pointed to by the pointer that represents the current char are all NULL, in some cases, some elements of this array are not NULL and the pointer that represents the current struct still the last char in a word in our dictionary.

As an example, consider the words "cat" and "caterpillar" in which case the array member of the struct pointed to by the pointer that represents the letter 't' after an 'a' after a 'c' still has elements that are not NULL (e.g., the 'e', etc.) and yet the 't' is still the end of "cat".