• Advertisement
Sign in to follow this  

pointer doubt...

This topic is 4648 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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 - :[

Share this post


Link to post
Share on other sites
well... the insert function inserts the item in the list, where the list is a binary search tree...

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)

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
ok, sorry... its something like:


struct node
{
Item item;
struct node *left;
struct node *right;
};

typedef struct node *List;


Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Quote:
Original post by deffer
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
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);

Cheers
-Danu

Share this post


Link to post
Share on other sites
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... ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by deffer
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... ;)
I 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.
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]

Share this post


Link to post
Share on other sites
Ooooooh, now I got it...
So I completely misunderstood your post, heh
;)

Share this post


Link to post
Share on other sites
hmm... lets see if I understood it: if I define my List as typedef node **List, it will work (in C), right? and then work with it like (*lst)->left, etc?

Share this post


Link to post
Share on other sites
Quote:
Original post by FreJa
hmm... lets see if I understood it: if I define my List as typedef node **List, it will work (in C), right? and then work with it like (*lst)->left, etc?
yep, you've got it.

basic explination:
a pointer is a memory address, which can be considered like this:
[pointer A]
|
deref
|
+-[Memory]
when you pass a pointer to a function, it is treated as a
pointer inside the local function scope, ie. the pointer is copied to a
local pointer variable!! (like how you pass in an int by value!)
If we try and allocate space in pointer A, we're just going to change where
it points too, and once the function returns, that memory will be lost
(the local pointer goes out of scope -- leak!)

so we need to do this:

[pointer B]
|
deref
|
+-[pointer A]
|
deref
|
+-[Memory]

by doing this, even though the address is copied, it is the address of another
pointer, so when we dereference pointer B, we get access to pointer A
and thus access to where it points to...

hope I didnt confuse you...

Cheers
-Danu

Share this post


Link to post
Share on other sites
huge thanks... just one more thing...
these are the functions I'm using to handle my list (tree):


List new()
{
List lst = (struct node **)malloc(sizeof(List));
*lst = (struct node *)malloc(sizeof(struct node));
(*lst)->item = NULLitem;
(*lst)->left = (*lst)->right = NULL;

return lst;
}

void print(List lst)
{
struct node *node = *lst;
if(node != NULL)
{
printf("%d\n", node->item);
print(&(node->left));
print(&(node->right));
}
}

void insert(List lst, Item it)
{
struct STnode *node = *lst;
if(node->item == NULLitem)
node->item = it;
else if(key(it) < key(node->item))
{
if(node->left != NULL)
insert(&(node->left), it);
else
{
node->left = (struct node *)malloc(sizeof(struct node));
node->left->item = it;
node->left->left = NULL;
node->left->right = NULL;
}
}
else if(key(it) >= key(node->item))
{
if(node->right != NULL)
insert(&(node->right), it);
else
{
node->right = (struct node *)malloc(sizeof(struct node));
node->right->item = it;
node->right->left = NULL;
node->right->right = NULL;
}
}
}

void delete(List lst, Key v)
{
struct node *node = *st;
struct node *temp;

if(node != NULL)
{
if(v < key(node->item))
delete(&(node->left), v);
else if(v > key(node->item))
delete(&(node->right), v);
else if(node->left && node->right)
{
temp = FindMin(&(node->right));
node->item = temp->item;
delete(&(node->right), key(node->item));
}
else
{
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp);
}
}
}



new() creates a new instance of the tree, print(), prints all the elements of the tree... Now, if, in my main function, I do this:


insert(lst1, 3);
insert(lst1, 2);
insert(lst1, 5);

print(lst1);

delete(lst1, 2);

print(lst1);



the first print works just fine... however in the second one, I get an 'Object reference not set to an instance of an object' error inside my print function when I do node->item... I guess this happens because node isn't NULL (so it passes the if), however, it SHOULD be NULL, cause I called delete...
I believe delete is correct, but maybe not... any help?

Huge thanks again

Share this post


Link to post
Share on other sites
Hi, I cant see where you use your new function... ?
and is List a typedef of node** ?

Share this post


Link to post
Share on other sites
Yes list is a typedef of node**...

I use new in my main function, like:

List lst1 = new();

and then:

insert(lst1, ...);
...

Share this post


Link to post
Share on other sites
ok, i think your still a little confused about how the pointer-pointer thing
works, and thats ok.. it took me a while too :)

hopefully the code will clear things up, you should be using better
names as well, consider you're coding in C! tisk tisk!

you really only need to be passing around pointer-pointers when you need
to allocate memory (mostly, there might be other situations though)

struct node {
};

typedef struct node *LPNODE; // pointer to a node

LPNODE list_create() {
LPNODE ret = (LPNODE) malloc(sizeof(node));
ret->item = NULL_Item;
ret->left = ret->right = NULL;
return ret; // we can do this, because all we need is the memory address
// we dont need to operate on any objects or pointers, just need
// the address of memory we can use.
}

void list_print( LPNODE list ) {
if( list = NULL ) return;
printf("%d\n", node->item );
print( node->left );
print( node->right );
}

void list_insert( LPNODE list, Item it )
{
// do insert stuff
}

void list_remove( LPNODE list, Key v ) {
LPNODE p = list_find_by_key( v );
if( !p ) return;

list_recursive_free( p->left );
list_recursive_free( p->right );
free( p );

list_find_and_nullify( list, p );
}

some pseudo code mixed in there, you should be able to figure it out
having a look at all your code might be a bit more helpfull too..

Share this post


Link to post
Share on other sites
silvermace: but that way I would be back to my original problem: insert wouldn't change the list...

Share this post


Link to post
Share on other sites
Forgive me but since when did a List ADT represent a hierarchical structure [smile], List == Sequence maybe changing it to a more appropriate name [grin].

Are you sure wont a list and not a binary search tree.

Share this post


Link to post
Share on other sites
@silvermace:
Your code is ok, but one function:

void list_insert( LPNODE *list, Item it ) // <-- HERE, *
{
// do insert stuff
}



that way we can have:


#define EMPTY_LIST NULL

void f()
{
LPNODE lst = EMPTY_LIST;

list_insert( &lst, 3 );
list_insert( &lst, 4 );

print_list(lst);

delete_list(lst);
// and maybe:
lst = EMPTY_LIST;
};



In insert code you check for null like in my previous code posted.

Cheers.
/def

Share this post


Link to post
Share on other sites
but what about my earlier post, and the functions I posted there? wouldn't they work? The insert works fine... but remove doesn't seem to be working...

Share this post


Link to post
Share on other sites
I suppose they would, but they are somewhat overcomplicated.
And also, you have to rewrite your new() function (and also, rename it ;)), it's messed in the malloc(sizeof(node**)) part.

I'm against typedefing List as node**, rather as node*(LPNODE), as you don't have to (and don't want to) pass node** everywhre to use your nodes.
Where you should be passing node**, do it explicite, by LPNODE*. That happens, in functions, that may get the main node of your list, and change it. Like when you have empty list, and after insert, one-node list. In your new() function, you are proposing using, so called, guard. This is what I call overcomplicating stuff. A simple NULL pointer is enough.

What your guard does really? It allows you to pass empty list to insert function without seg-fault. How? By passing a <location>, where the real "NULL-something" is, that is, where you check for NullItem, and overwrite it, if necessary.
Instead, you can pass a location to a real NULL pointer, and overwite it, if necessary.

Check my previous code posted (with insert(node** ppNode, Item i)).

Cheers.
/def

Share this post


Link to post
Share on other sites
bah, you're right deffer I wasnt paying attention >_< i had just got back from Uni had a 2 hour test and my brain hurts!

You if want to manipulate a pointer in one scope from another scoep then you
should use a pointer-pointer...

Cheers,
-Danu

Ps. appologies for my idiocy, I hope that didn't throw you off too much -_-'

Share this post


Link to post
Share on other sites
IMHO, I think your design apporach is all wrong FreJa a few things:
you are treating a linked list like it is a tree, and even in doing so you
haven't updated the name... so this is isn't healping solve your issue

I'm really tired atm, and Im usually not good at explinations anyway..
but i can show you how i would implement a Binary Tree in C

scroll down to the bottom to see the main() function and the test case.
I have only implemented "insert", remove should be trivial as i have
provided functions that traverse the nodes and shown you how to completly
avoid the pointer-pointer issues!


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

//----------------------------------------------------------------------------------------------
// declarations

typedef int ItemType;

// the node of our tree, notice the nice clean naming !!
typedef struct BinaryTreeNode
{
union
{ // allow us to access the same pointers but with some optional flexibility
struct { struct BinaryTreeNode *left, *right; };
struct { struct BinaryTreeNode *less_than_this, *more_than_this; };
};
ItemType data;
int dataInstances; // for when we have two datum the same in the same tree

} BinaryTreeNode;

// tree data structure, avoid nasty pointer-pointer issues
// using ecapsulation where ever possible
typedef struct BinaryTree
{
BinaryTreeNode *root;
int numElements;

} BinaryTree;

// help us out here
typedef BinaryTree *LPBINARYTREE;
typedef BinaryTreeNode *LPBINARYTREENODE;

//----------------------------------------------------------------------------------------------
// function declarations
LPBINARYTREENODE bintree_create_node ( LPBINARYTREE tree, ItemType data );
LPBINARYTREENODE bintree_insert ( LPBINARYTREE tree, ItemType data );
LPBINARYTREE bintree_create ( );
void bintree_print_node ( LPBINARYTREENODE node, int level, const int numLayers, int pos );
void bintree_print ( LPBINARYTREE tree );

//----------------------------------------------------------------------------------------------
// creats a single node, returns address
LPBINARYTREENODE bintree_create_node( LPBINARYTREE tree, ItemType data )
{
LPBINARYTREENODE ret = (LPBINARYTREENODE) malloc( sizeof(BinaryTreeNode ) );
ret->dataInstances++;
ret->data = data;
ret->left = ret->right = NULL;
tree->numElements++;
return ret;
}

//----------------------------------------------------------------------------------------------
// creates a tree, returns address
LPBINARYTREE bintree_create()
{
// allocate tree and root node
LPBINARYTREE ret = (LPBINARYTREE) malloc( sizeof( BinaryTree ) );
ret->root = NULL;
return ret;
}

//----------------------------------------------------------------------------------------------
// recursively print out a node and its non-null subnodes
// pos = 0 its a center node, -1 its a left node, 1 its a right node
void bintree_print_node( LPBINARYTREENODE node, int level, const int numLayers, int pos )
{
int i = 0;
char desc[4] = "C\000";

if( node == NULL ) return;

if( pos == -1 ) strncpy( desc, "L\000", 4 );
if( pos == +1 ) strncpy( desc, "R\000", 4 );

for( i=0; i<level; i++ )
printf(" ");
printf( "%s%i: %i\n", desc, level, node->data );

++level;
bintree_print_node( node->left, level, numLayers, -1 );
bintree_print_node( node->right, level, numLayers, +1 );
}

//----------------------------------------------------------------------------------------------
// print out a tree
void bintree_print( LPBINARYTREE tree )
{
int numLayers = 0;

if( tree == NULL )
return;

numLayers = (int)log( (double)tree->numElements );
bintree_print_node( tree->root, 0, numLayers, 0 );
}

//----------------------------------------------------------------------------------------------
// returns a pointer to the newly inserted node
LPBINARYTREENODE bintree_insert( LPBINARYTREE tree, ItemType data )
{
LPBINARYTREENODE cur = tree->root;
int done = 0;

if( cur == NULL ) // no root node
{
tree->root = bintree_create_node( tree, data );
tree->numElements++;
return tree->root;
}

// if done == -1 insertion occured on a left node
// if done == +1 insertion occured on a right node
while( done == 0 )
{
// saftey check
if( cur == NULL )
break;

// if its less than either follow the left node
// or add it to the null left node
if( data < cur->data ) {
if( cur->less_than_this != NULL )
cur = cur->less_than_this;
else {
cur->less_than_this = bintree_create_node( tree, data );
done--;
}
}
else // if its greater than, do the opposite
if( data > cur->data ) {
if( cur->more_than_this != NULL )
cur = cur->more_than_this;
else {
cur->more_than_this = bintree_create_node( tree, data );
done++;
}
}
else
{ // it must be equal, since its already in the tree
// just increment the data-instance counter
cur->dataInstances++;
done = -2;
}
}

tree->numElements++;
return cur;
}


// our test function
int main()
{
/*
example binary tree:

6
.-----------+-----------.
3 10
.-------+-------. .-------+-------
2 5 7
--+-- --+---.
9

application output:

C0: 6
L1: 3
L2: 2
R2: 5
R1: 10
L2: 7
R3: 9
*/


LPBINARYTREE myTree = bintree_create();

bintree_insert( myTree, 6 );
bintree_insert( myTree, 10 );
bintree_insert( myTree, 3 );
bintree_insert( myTree, 2 );
bintree_insert( myTree, 7 );
bintree_insert( myTree, 9 );
bintree_insert( myTree, 5 );

bintree_print( myTree );

return 0;
}











Compile Command: GCC v3.3.1 i386 Win32
gcc -W -Wall bintree.c -o bintree

Good Identifier Naming Goes A Long Way In Making Good Code.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement