pointer doubt...
Hi,
I want to insert some items into a list (in C), for that I use the function void insert(List lst, Item i).
In my main function, I'm doing something like:
insert(lst1, 4);
insert(lst1, 3);
now, lst1, after calling these, has only the item 3... I suppose this is because I didn't pass as a parameter the pointer to the list... right?
but without changing the parameters of insert, is there any way I can make this work?
Thanks
Quote:Original post by FreJa
but without changing the parameters of insert, is there any way I can make this work?
But without seeing the actual implementation of your list...
Is there any way you could post it?
Cheers.
/def
PS: No, I don't think you could pass your list by value (that copying it), and try to change it in your function... By reference would be great, since it does not change the usage semantics, but since this is pure C - :[
well... the insert function inserts the item in the list, where the list is a binary search tree...
but something like this:
(this is not exactly my code... I dont have it with me right now... I took this one from the web... but it does the same things)
but something like this:
if(key< leaf->key_value) { if(leaf->left!=NULL) insert(key, leaf->left); else { leaf->left=new node; leaf->left->key_value=key; leaf->left->left=NULL; //Sets the left child of the child node to null leaf->left->right=NULL; //Sets the right child of the child node to null } } else if(key>=leaf->key_value) { if(leaf->right!=NULL) insert(key, leaf->right); else { leaf->right=new node; leaf->right->key_value=key; leaf->right->left=NULL; //Sets the left child of the child node to null leaf->right->right=NULL; //Sets the right child of the child node to null } }
(this is not exactly my code... I dont have it with me right now... I took this one from the web... but it does the same things)
Ekhm...
The list (tree) declaration would be much more helpful ;)
EDIT: Oh,oh,oh, I just read into your code closer, and get the declaration from it. There is an insert function with semantics:
void insert(int key, list* pNode);
Why aren't you using it?
The list (tree) declaration would be much more helpful ;)
EDIT: Oh,oh,oh, I just read into your code closer, and get the declaration from it. There is an insert function with semantics:
void insert(int key, list* pNode);
Why aren't you using it?
ok, sorry... its something like:
struct node{ Item item; struct node *left; struct node *right;};typedef struct node *List;
I assume your empty list is just a NULL pointer. Then, no, you can't pass it as a value to any function ;)
To sum the things up, if you declare:
typedef node* List; (or #define List node*)
everything would be great. Except for that you would be writing lst->left instead of lst.left, but that only inside of your implementation.
EDIT: I think your semantic should look like:
void insert(node** pNode, Item i);
so that you could pass NULL pointer as a parameter, and it will create a node there.
Cheers.
/def
To sum the things up, if you declare:
typedef node* List; (or #define List node*)
everything would be great. Except for that you would be writing lst->left instead of lst.left, but that only inside of your implementation.
EDIT: I think your semantic should look like:
void insert(node** pNode, Item i);
so that you could pass NULL pointer as a parameter, and it will create a node there.
Cheers.
/def
Quote:Original post by defferIt should also be mentioned that every time you access the element pNode you need to dereferece twice either:
EDIT: I think your semantic should look like:
void insert(node** pNode, Item i);
so that you could pass NULL pointer as a parameter, and it will create a node there.
Cheers.
/def
(*(*pNode)).left or (*pNode)->left you can avoid changing your code at all by passing a reference to a pointer (this will let the compiler do the defeferencing op for you) the funtion declaration is:
void insert(node*& pNode, Item i);
Cheers
-Danu
Quote:Original post by silvermace
It should also be mentioned that every time you access the element pNode you need to dereferece twice either:
(*(*pNode)).left or (*pNode)->left you can avoid changing your code at all by passing a reference to a pointer (this will let the compiler do the defeferencing op for you) the funtion declaration is:
void insert(node*& pNode, Item i);
The OP mentioned it is written in C, so I think the references are out of the way.
Also, AFAIK, *& and ** are the same for the compiler, in terms of code-generation. And that most of the time the compiler cannot dereference anything on his own unless explicitly told to - because of potential aliasing. But implementator can do this explicitly. For example:
void insert(node **ppNode, Item i){ node *pNode = *ppNode; // dereference once here. if (pNode == NULL) { *ppNode = new node(i); return; } else { // proceed using "pNode" // ... insert( &(pNode->left), i ); // recursion (?) return; };}
And most likely the compiler will create the tail-recursion there, so really there will be only one _inevitable_ additional dereferencing.
Hope I'm right... ;)
Quote:Original post by defferI saw new and assumed C++, my bad [smile]What i meant by the compiler dereferencing is more like what *appears* like the compiler doing it automagically.Quote:Original post by silvermace
It should also be mentioned that every time you access the element pNode you need to dereferece twice either:
(*(*pNode)).left or (*pNode)->left you can avoid changing your code at all by passing a reference to a pointer (this will let the compiler do the defeferencing op for you) the funtion declaration is:
void insert(node*& pNode, Item i);
The OP mentioned it is written in C, so I think the references are out of the way.
Also, AFAIK, *& and ** are the same for the compiler, in terms of code-generation. And that most of the time the compiler cannot dereference anything on his own unless explicitly told to - because of potential aliasing. But implementator can do this explicitly. For example:
*** Source Snippet Removed ***
And most likely the compiler will create the tail-recursion there, so really there will be only one _inevitable_ additional dereferencing.
Hope I'm right... ;)
void foo(pNode*& n) { n = new node(); n->left = NULL;}
that is perfectly valid in C++, and it will behave as though pNode** was passed without the explicit first dereference from pointer-pointer to pointer. [smile]This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement