0

In the tutorial video Zamyla states to "check the value at children[i]"

Which will return NULL or not NULL.

What does check the value mean?

Cheers

Adam

1
  • Also the example implies that the children array is not filled with characters but pointers. root -> children[5] -> children[15] -> children[24] My initial understanding was that each index of the array was a structure containing a character and a node though this seems misinformed – Adam Wilson Aug 14 '14 at 12:11
1

What Zamyla meant, is that you need to inspect the value stored in children[i], and perform some action depending on whether the value is NULL. Basically this equates to an if statement:

if (children[i] == NULL)
{
    // children[i] does not point to anything
}
else 
{
    // children[i] points to something
}

Also the example implies that the children array is not filled with characters but pointers. root -> children[5] -> children[15] -> children[24] My initial understanding was that each index of the array was a structure containing a character and a node though this seems misinformed

The array does contain pointers to structs, and not structs themselves. This is done for efficiency.

Storing only pointers in the array means that the program can allocate a struct for each item in the array as needed. So if a specific position in the array is never filled, then the memory for that spot never needs to be allocated. Yes, it will waste the space for the pointer (4 bytes), but this is less than the space required to store the struct.

While you could use an array of structs, each instance of the array would take up the amount of memory required to store 26 structs, even if they do not contain any data, with the result that a large percentage of the memory will be wasted. Allocating and deallocating all this memory takes time, which will also impact performance.

Another thing to consider is exactly how the circular reference caused by using an array of structs might affect how the trie is loaded into memory. If the struct contained an array of structs, each of the structs in the array would also contain an array of structs, and so on.

Your program would just go on allocating memory to store these structs until it ran out of memory. While I have not tried this myself, my guess is that the compiler would be intelligent enough to detect if your code would do such a thing, and probably would not even allow this to compile. If the program did compile and run, it would crash as soon as it enters the stack frame where the first struct is allocated (be that global or a function call).

You must log in to answer this question.

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