what does double pointer mean?

[Bluga]

If i have a TreeNode stucture like following:

typedef struct TreeNode{

int num;
int *keys;
struct TreeNode **Children;

}TREENODE

 

[TangDN]

**Children is a pointer to a pointer of type struct TreeNode.

Why its done, how it works, I have NO CLUE. i hate programming.

 

[PCHPlayer]

In this case Children is a pointer to an array of TreeNodes. You would use it like this:

addChildren(TreeNode children[], int numChildren)
{
node.Children = (TreeNode **)malloc(sizeof(TreeNode *) * numChildren);
for (int i = 0; i < numChildren; i++)
node.Children\ = children\; // this should be subscript i for both, but the forum software keeps turning it into italics
}

Pointers can be a real pain. That's one of the reasons why C++ STL comes in handy and why Java has no pointers.

 

[Bluga]

so the Childern is a pointer to an array of type TreeNode? What type is the Chidren pointer? Thank you.

 

[Bluga]

ttt

 

[Bluga]

bump.

 

[PCHPlayer]

In C/C++ an array and a pointer are treated the same. So if you have a routine that takes a TreeNode *, the compiler will accept either of the following.

TreeNode nodes[10];
TreeNode node;
TreeNode *node_ptr;

routine(nodes);
routine(&node);
routine(node_ptr);

So a double pointer is a pointer to either one of these. In some cases it is a pointer to a pointer:

TreeNode *node;
routine(&node); // In this case "routine" will most likely modify what node points to

And in some cases it is a pointer to an array:

TreeNode nodes[10];
routine(&nodes); // This is not normal, but in this case the contents on "nodes" is probably of interest to "routine"

It just depends on the application.

In your case, if Children was declared as struct TreeNode *Children[]; (An array of pointers) it probably would have been clearer, but since you do not know how many pointers you have you must allocate all the memory dynamically.

I could go on here, but this post would get way too long. I hope these examples help.

 

[Bluga]

Thank you very much guys. I'm trying to build a simple m-way search tree (no need to balance, m is given), does the following function look correct? (How can i move to next child node if the curent is full?)

===================================================
typedef struct TreeNode {

int num_of_keys;
int *keys;
struct TreeNode **children;

} TREENODE;

/* Insert(...) inserts key into the N-way search tree pointed to by root. It returns NULL if key already exists*/

struct TreeNode* Insert(struct TreeNode *root, int key)
{


if ( root == NULL )
{
root = (TreeNode **)malloc(sizeof(TreeNode *) * num_of_keys);
root->keys[0] = key;
root->num_of_keys = root->num_of_keys - 1;
}
else
{
for ( s=0; (s<root->num_of_keys); s++ );
{
if ( key == root->keys )
return NULL;

else
{
if (key<root->keys)
keys[s+1] = keys; /***shift****/
else{
key[s+1] = key;
s = s+1;
}

}

}

}

}

 

[Bluga]

bump.

 

[Bluga]

ttt

 

[Bluga]

^^^

 

[TangDN]

best way i've found to make a tree was to make it recursive. that way any changes to root would be taken care of rather easily.