11 Replies - 1133 Views - Last Post: 03 December 2009 - 08:15 AM Rate Topic: -----

#1 homemade-jam  Icon User is offline

  • Gabe's Nemesis
  • member icon

Reputation: 11
  • View blog
  • Posts: 1,300
  • Joined: 17-March 08

Binary Tree Struct

Posted 03 December 2009 - 07:34 AM

hello...a classic topic in CS for C programming courses...

I'm designing a binary tree using a struct which has pointers to the left and right children.

Have these two structs....
Node *Top = malloc(sizeof(Node));	 
Node **Home = malloc(sizeof(Node));

I want to be able to return to the top so that I can search through it later...
*Home =Top;
...here I want to return to the top...
 Top = *Home;			// Go back to the to of the tree  


My code used to behave and now it's stopped - I think there is a problem with returning to the top of the tree, could anyone enlightenment as to why the assignment *Home = Top; isn't right?

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Tree Struct

#2 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Binary Tree Struct

Posted 03 December 2009 - 07:38 AM

Quote

My code used to behave and now it's stopped



What does that really mean?
Was This Post Helpful? 0
  • +
  • -

#3 homemade-jam  Icon User is offline

  • Gabe's Nemesis
  • member icon

Reputation: 11
  • View blog
  • Posts: 1,300
  • Joined: 17-March 08

Re: Binary Tree Struct

Posted 03 December 2009 - 07:41 AM

Well it used to return to the top of my tree as it should but now it doesn't appear to do that...is it to do with the code above? Are the assignments to get back to the top the right sort of thing?
Was This Post Helpful? 0
  • +
  • -

#4 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: Binary Tree Struct

Posted 03 December 2009 - 07:42 AM

This:
Node **Home = malloc(sizeof(Node));
ain't right. Think about what you're allocating space for there.
Was This Post Helpful? 0
  • +
  • -

#5 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Binary Tree Struct

Posted 03 December 2009 - 07:45 AM

int main(){
	int** doublePtr;
	int* ptr;
	int x = 75;
	ptr = &x;
	doublePtr = &ptr; //do it this way

	cout << x << endl;
	cout << *ptr << endl;
	cout << **doublePtr << endl;
	return 0;
}



The way you did it would be fine if the ptr was initialized prior to assignment.
Was This Post Helpful? 0
  • +
  • -

#6 homemade-jam  Icon User is offline

  • Gabe's Nemesis
  • member icon

Reputation: 11
  • View blog
  • Posts: 1,300
  • Joined: 17-March 08

Re: Binary Tree Struct

Posted 03 December 2009 - 07:46 AM

View PostJackOfAllTrades, on 3 Dec, 2009 - 01:42 PM, said:

This:
Node **Home = malloc(sizeof(Node));
ain't right. Think about what you're allocating space for there.

Well I'm trying to allocate a pointer to a pointer so I am allocating too much space there? :ph34r:
Was This Post Helpful? 0
  • +
  • -

#7 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Binary Tree Struct

Posted 03 December 2009 - 07:52 AM

You need allocate space for a Node pointer (not a Node object), since head is just a pointer to a pointer:

struct Node{
	int data;
};

//sample implementation
int main(){
	Node** head;
	Node* top;
	head = (Node**)malloc(sizeof(Node*));
	top = (Node*)malloc(sizeof(Node));

	head = &top;
	top->data = 100;

	cout << top->data << endl;
	cout << (*head)->data << endl;

	free(top);
	free(head);
	
	return 0;
}


This post has been edited by KYA: 03 December 2009 - 07:53 AM

Was This Post Helpful? 1
  • +
  • -

#8 homemade-jam  Icon User is offline

  • Gabe's Nemesis
  • member icon

Reputation: 11
  • View blog
  • Posts: 1,300
  • Joined: 17-March 08

Re: Binary Tree Struct

Posted 03 December 2009 - 07:59 AM

Cheers, it's nearly there - it just the returning to the top section that I can't get quite right now.

I think I want to assign the address pointed by the pointer of the pointer Home to the address pointed to by Top.

....so Top = *Home;?
Was This Post Helpful? 0
  • +
  • -

#9 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Binary Tree Struct

Posted 03 December 2009 - 08:11 AM

Yes. Are you running tests to verify your hypothesis?

struct Node{
	int data;
};

//sample implementation
int main(){
	Node** head;
	Node* top, *temp;
	head = (Node**)malloc(sizeof(Node*));
	top = (Node*)malloc(sizeof(Node));
	temp = (Node*)malloc(sizeof(Node));

	head = &top;
	top->data = 100;
	temp->data = 50;

	head = &temp;
	top = *head;

	cout << top->data << endl;
	cout << (*head)->data << endl;

	free(temp);
	free(top);
	free(head);
	
	return 0;
}



It takes ~5 secodns to see if you're right or not.
Was This Post Helpful? 0
  • +
  • -

#10 homemade-jam  Icon User is offline

  • Gabe's Nemesis
  • member icon

Reputation: 11
  • View blog
  • Posts: 1,300
  • Joined: 17-March 08

Re: Binary Tree Struct

Posted 03 December 2009 - 08:13 AM

Yeah I'm doing almost trial and error but I keep getting seg. faults when I pass it to my insert or find function....
int insert(Node **n_Top, char cName[MAXBUF], char iNumber[MAXBUF])

All these pointers are doing my head in...as far as I can see it should work...urgh.
Was This Post Helpful? 0
  • +
  • -

#11 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • Joined: 14-September 07

Re: Binary Tree Struct

Posted 03 December 2009 - 08:15 AM

Break it down into a small module. Get that piece to work, add another small module, repeat.
Was This Post Helpful? 0
  • +
  • -

#12 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: Binary Tree Struct

Posted 03 December 2009 - 08:15 AM

The way to think about malloc and sizeof is this: you're always creating a pointer, so you need to allocate the space for what's being pointed at. So, always drop off an asterisk to determine what you're getting the size of.

Node *myNode = malloc(sizeof(Node)); // drop a *

Node **myNodes = malloc(sizeof(Node*)); //drop a *

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1