0

So, for my load function in pset6, I'm creating a new node for the current char if it isn't found in the children.

node* node_cur = &root_node;

loop iterate over chars in word
{
    if(node_cur->children[c] == NULL)
    {
        node new_node;
        node_cur->children[c] = &new_node;
        node_cur = &new_node;
    }
}

Should I now initialise the content of new_node? Because, possibly the new node is filled with garbage values, am I right? With some code like this

node_cur->is_word = false;
for(int i = 0; i < 27; i++)
{
    node_cur->children[i] = NULL;
}

Also, there should be a way to make it more smooth using malloc, but I don't really know this works.

Could I replace the code at the top of my question with this?

    if(node_cur->children[c] == NULL)
    {
        node* new_node = malloc(sizeof(node));
        node_cur->children[c] = new_node;
        node_cur = new_node;
    }

EDIT: outside the load function I defined the type, and declared the root as follows:

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

node root_node;
node* root= &root_node;
1

If root_node is a pointer, why are you setting node_cur to point to root_node itself instead of setting it to point to the struct pointed to by root_node?

If you wanna set a node to point to the same memory location as another node of the same type, you just write something like

newNode = oldNode;

Not

newNode = &oldNode;

Also, you're iterating over the chars of the word checking whether node_cur->children[c] is equal to NULL without checking whether node_cur itself is equal to NULL. This could lead to segmentation fault.

And yes, you're right about initializing the pointers to NULL before checking their values.

I see there's no reason for creating an additional pointer (new_node). You could directly allocate memory for node_cur->children[c] if there's no memory allocated for it already.

Also, what happens in case node_cur->children[c] is not equal to NULL. Do you just wanna do nothing?

Lastly, the root of a trie should be an array of pointers. Here's some pseudocode to help you with the insertion process

NOTE: please don't try to translate this pseudocode to code without trying your best first to get it working or without completely understanding this pseudocode!

Assuming the root is declared as an array of pointers to node,

create a pointer to a node named temp and set it to NULL

// insert word
for each char in the word
    calculate the index of the current char and store it in index

    // insert the first char
    if the current char is the first char

        if root[index] points to NULL
            allocate memory for root[index]
            set the flag of root index to false
            set all the children of root index to NULL

        // update temp
        set temp to root[index]

    // insert the next chars
    else

        if temp->children[index] points to NULL
            allocate memory for temp->children[index]

            if the current char is the last char in the word
                set the flag of temp->children[index] to true;
            else
                set the flag of temp->children[index] to false;

            set all the children of temp->children[index] to NULL

        // update temp
        set temp to temp->children[index]

Hope that helps!

You must log in to answer this question.

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