Programming Forums > Application Development > C++

nnxion · Mar 31st, 2006, 3:48 AM

Re-explain shortly in clear words what you want insertSpot and realInsert to do? You need to reread what The Dark said. Also try to name your variables different, because you are confusing yourself with i's declared in your for loops etc.

Before adding insertSpot, or realInsert, you should test your code like this:

(Toggle Plain Text)

#include <iostream>
using namespace std;

class heapNode
{
	private:
		int value;
		//heapNode *left;
		//heapNode *right;

	public:
		heapNode *left;
		heapNode *right;

		heapNode(int newValue)
		{
			value = newValue;
			left = NULL;
			right = NULL;
		}

		int getValue()
		{
			return value;
		}

		heapNode* getRight()
		{
			return right;
		}

		heapNode* getLeft()
		{
			return left;
		}

		void setValue(int newValue)
		{
			value = newValue;
		}

		void setRight(heapNode *newRight)
		{
			right = newRight;
		}

		void setLeft(heapNode *newLeft)
		{
			left = newLeft;
		}

}; // end of heapNode class

class heap
{
	private:
		heapNode *root;
		int counter;

	public:
		heap()
		{
			counter = 0;
			root = new heapNode(0);
		}

		// get root
		heapNode* getRoot()
		{
			return root;
		}
};

int main()
{
	heap *myHeap;

	myHeap = new heap();

	int value = 0, left = 0, right =0;

	cout << "Please enter a value for your first heap node: ";
	cin >> value;

	// get the root heapnode, and set the value of the root heapnode
	heapNode *hnRoot = myHeap->getRoot();
	hnRoot->setValue(value);

	cout << "Please enter a value for right child of your first heap node: ";
	cin >> right;
	
	// make root's right child and add it
	heapNode hnRight(0);
	hnRight.setValue(right);
	hnRoot->setRight(&hnRight);

	cout << "Please enter a value for right child of your first heap node: ";
	cin >> left;

	// make root's left child and add it
	heapNode hnLeft(0);
	hnRoot->setLeft(&hnLeft);
	hnLeft.setValue(left);

	// print values
	cout << "Value of root heapnode is: " << hnRoot->getValue() << endl;
	cout << "Value of root's right child is: " << hnRoot->getRight()->getValue() << endl;
	cout << "Value of root's left child is: " << hnRoot->getLeft()->getValue() << endl;

	return 0;
}

The Dark · Mar 31st, 2006, 4:03 AM

@nnixion: In that loop, i gets set to -1 and then the loop exits, (the loop still continues when i is 0, as shown by the fact that it prints it out).

@cwl157: I can't see how that change would fix up your segfault. The infinite recursion is still there as you only changed the code after the recursion occurs.

I still don't get the whole bit-checking thing. I can't see how this could ever make a min-heap, as one of the properties of a min-heap is that each parent node is less than all of its child nodes.

nnxion · Mar 31st, 2006, 4:10 AM

Quote:

Originally Posted by The Dark

@nnixion: In that loop, i gets set to -1 and then the loop exits, (the loop still continues when i is 0, as shown by the fact that it prints it out).

Oh yeah, of course, can't believe I forgot that, it's still early you know.

By the way Peter, how do you pronounce my nickname? :p

The Dark · Mar 31st, 2006, 5:39 AM

en-nixion (oops) :o
Thats how it sounds in my head, sometimes my fingers listen to my brain instead of typing by themselves.

nnxion · Mar 31st, 2006, 5:51 AM

Quote:

Originally Posted by The Dark

en-nixion (oops) :o
Thats how it sounds in my head, sometimes my fingers listen to my brain instead of typing by themselves.

Haha, yeah I get that too sometimes. My nickname was nnx as if it were an abbreviation. So the letters were to sound apart. Later I registered at AIM and I needed a six letter nick, so I put "ion" behind it.

cwl157 · Mar 31st, 2006, 10:32 AM

insertSpot is supposed to take a counter and find the next spot to add a value based on the counter. The realInsert is supposed to actually insert the new node in the right spot.

nnxion · Mar 31st, 2006, 12:17 PM

Quote:

Originally Posted by cwl157

insertSpot is supposed to take a counter and find the next spot to add a value based on the counter. The realInsert is supposed to actually insert the new node in the right spot.

Okay, take my code and have a good look, then add the code The Dark gave you and return with the new code. We might then be able to help you further.

cwl157 · Mar 31st, 2006, 1:04 PM

wait so just this... I do not get what this is supposed to do? I get that the code gives a value to root and then to the right and left child and it prints it so it works but then how do i add more and make it look like a tree and stuff?

(Toggle Plain Text)

#include <iostream>
using namespace std;

class heapNode
{
	private:
		int value;
		//heapNode *left;
		//heapNode *right;

	public:
		heapNode *left;
		heapNode *right;

		heapNode(int newValue)
		{
			value = newValue;
			left = NULL;
			right = NULL;
		}

		int getValue()
		{
			return value;
		}

		heapNode* getRight()
		{
			return right;
		}

		heapNode* getLeft()
		{
			return left;
		}

		void setValue(int newValue)
		{
			value = newValue;
		}

		void setRight(heapNode *newRight)
		{
			right = newRight;
		}

		void setLeft(heapNode *newLeft)
		{
			left = newLeft;
		}

}; // end of heapNode class

class heap
{
	private:
		heapNode *root;
		int counter;

	public:
		heap()
		{
			counter = 0;
			root = new heapNode(0);
		}

		// get root
		heapNode* getRoot()
		{
			return root;
		}

void realInsert(int ar, int pos, int newValue)
  {
    heapNode *newNode;
    newNode = new heapNode(newValue);   
    if(newNode->left != NULL)           
    {
      realInsert(ar, pos-1, newValue);

      if(newNode->left->getValue() < newNode->getValue())
        newNode->setValue(newNode->left->getValue());
    }
    else if(newNode->right != NULL)
    {
      realInsert(ar, pos-1, newValue);
      if(newNode->right->getValue() < newNode->getValue())
        newNode->setValue(newNode->right->getValue());
    }
  }
};

int main()
{
	heap *myHeap;

	myHeap = new heap();

	int value = 0, left = 0, right =0;

	cout << "Please enter a value for your first heap node: ";
	cin >> value;

	// get the root heapnode, and set the value of the root heapnode
	heapNode *hnRoot = myHeap->getRoot();
	hnRoot->setValue(value);

	cout << "Please enter a value for right child of your first heap node: ";
	cin >> right;
	
	// make root's right child and add it
	heapNode hnRight(0);
	hnRight.setValue(right);
	hnRoot->setRight(&hnRight);

	cout << "Please enter a value for right child of your first heap node: ";
	cin >> left;

	// make root's left child and add it
	heapNode hnLeft(0);
	hnRoot->setLeft(&hnLeft);
	hnLeft.setValue(left);

	// print values
	cout << "Value of root heapnode is: " << hnRoot->getValue() << endl;
	cout << "Value of root's right child is: " << hnRoot->getRight()->getValue() << endl;
	cout << "Value of root's left child is: " << hnRoot->getLeft()->getValue() << endl;

	return 0;
}

#include <iostream>
using namespace std;

class heapNode
{
	private:
		int value;
		//heapNode *left;
		//heapNode *right;

	public:
		heapNode *left;
		heapNode *right;

		heapNode(int newValue)
		{
			value = newValue;
			left = NULL;
			right = NULL;
		}

		int getValue()
		{
			return value;
		}

		heapNode* getRight()
		{
			return right;
		}

		heapNode* getLeft()
		{
			return left;
		}

		void setValue(int newValue)
		{
			value = newValue;
		}

		void setRight(heapNode *newRight)
		{
			right = newRight;
		}

		void setLeft(heapNode *newLeft)
		{
			left = newLeft;
		}

}; // end of heapNode class

class heap
{
	private:
		heapNode *root;
		int counter;

	public:
		heap()
		{
			counter = 0;
			root = new heapNode(0);
		}

		// get root
		heapNode* getRoot()
		{
			return root;
		}

void realInsert(int ar, int pos, int newValue)
  {
    heapNode *newNode;
    newNode = new heapNode(newValue);   
    if(newNode->left != NULL)           
    {
      realInsert(ar, pos-1, newValue);

      if(newNode->left->getValue() < newNode->getValue())
        newNode->setValue(newNode->left->getValue());
    }
    else if(newNode->right != NULL)
    {
      realInsert(ar, pos-1, newValue);
      if(newNode->right->getValue() < newNode->getValue())
        newNode->setValue(newNode->right->getValue());
    }
  }
};

int main()
{
	heap *myHeap;

	myHeap = new heap();

	int value = 0, left = 0, right =0;

	cout << "Please enter a value for your first heap node: ";
	cin >> value;

	// get the root heapnode, and set the value of the root heapnode
	heapNode *hnRoot = myHeap->getRoot();
	hnRoot->setValue(value);

	cout << "Please enter a value for right child of your first heap node: ";
	cin >> right;
	
	// make root's right child and add it
	heapNode hnRight(0);
	hnRight.setValue(right);
	hnRoot->setRight(&hnRight);

	cout << "Please enter a value for right child of your first heap node: ";
	cin >> left;

	// make root's left child and add it
	heapNode hnLeft(0);
	hnRoot->setLeft(&hnLeft);
	hnLeft.setValue(left);

	// print values
	cout << "Value of root heapnode is: " << hnRoot->getValue() << endl;
	cout << "Value of root's right child is: " << hnRoot->getRight()->getValue() << endl;
	cout << "Value of root's left child is: " << hnRoot->getLeft()->getValue() << endl;

	return 0;
}

nnxion · Mar 31st, 2006, 2:48 PM

You haven't changed anything to what The Dark said, it calls recursively. Why are you? What is supposed to happen to the insert? When is it supposed to swap the values or which value goes left and which goes right? Why are you checking to see if the nodes are NULL when they always are? Think about how it should go, work it out on paper if you have to. I'll try to work it out tomorrow, got to go to sleep now. Good luck!

EDIT: Maybe this will help you understand.

cwl157 · Mar 31st, 2006, 2:58 PM

i thought calling it recursively is the easiest way to do it. The number is supposed to be inserted in the next available spot going left to right. So the number the user entered is supposed to be added to the next available spot and then you compare that node with all the nodes before it and if its smaller than the parent node you swap the values because the lowest value has to be the root. I am checking when they are null because when one is null thats where the new value goes or something like that? Like i get the idea of inserting and swapping and stuff on paper with a picture of a tree and stuff but i have no clue how it should be programmed or anything.

Mar 31st, 2006, 3:48 AM	#21
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	Re-explain shortly in clear words what you want insertSpot and realInsert to do? You need to reread what The Dark said. Also try to name your variables different, because you are confusing yourself with i's declared in your for loops etc. Before adding insertSpot, or realInsert, you should test your code like this: (Toggle Plain Text) #include <iostream> using namespace std; class heapNode { private: int value; //heapNode left; //heapNode right; public: heapNode left; heapNode right; heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } int getValue() { return value; } heapNode* getRight() { return right; } heapNode* getLeft() { return left; } void setValue(int newValue) { value = newValue; } void setRight(heapNode newRight) { right = newRight; } void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: heap() { counter = 0; root = new heapNode(0); } // get root heapNode getRoot() { return root; } }; int main() { heap myHeap; myHeap = new heap(); int value = 0, left = 0, right =0; cout << "Please enter a value for your first heap node: "; cin >> value; // get the root heapnode, and set the value of the root heapnode heapNode hnRoot = myHeap->getRoot(); hnRoot->setValue(value); cout << "Please enter a value for right child of your first heap node: "; cin >> right; // make root's right child and add it heapNode hnRight(0); hnRight.setValue(right); hnRoot->setRight(&hnRight); cout << "Please enter a value for right child of your first heap node: "; cin >> left; // make root's left child and add it heapNode hnLeft(0); hnRoot->setLeft(&hnLeft); hnLeft.setValue(left); // print values cout << "Value of root heapnode is: " << hnRoot->getValue() << endl; cout << "Value of root's right child is: " << hnRoot->getRight()->getValue() << endl; cout << "Value of root's left child is: " << hnRoot->getLeft()->getValue() << endl; return 0; } #include <iostream> using namespace std; class heapNode { private: int value; //heapNode left; //heapNode right; public: heapNode left; heapNode right; heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } int getValue() { return value; } heapNode* getRight() { return right; } heapNode* getLeft() { return left; } void setValue(int newValue) { value = newValue; } void setRight(heapNode newRight) { right = newRight; } void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: heap() { counter = 0; root = new heapNode(0); } // get root heapNode getRoot() { return root; } }; int main() { heap myHeap; myHeap = new heap(); int value = 0, left = 0, right =0; cout << "Please enter a value for your first heap node: "; cin >> value; // get the root heapnode, and set the value of the root heapnode heapNode hnRoot = myHeap->getRoot(); hnRoot->setValue(value); cout << "Please enter a value for right child of your first heap node: "; cin >> right; // make root's right child and add it heapNode hnRight(0); hnRight.setValue(right); hnRoot->setRight(&hnRight); cout << "Please enter a value for right child of your first heap node: "; cin >> left; // make root's left child and add it heapNode hnLeft(0); hnRoot->setLeft(&hnLeft); hnLeft.setValue(left); // print values cout << "Value of root heapnode is: " << hnRoot->getValue() << endl; cout << "Value of root's right child is: " << hnRoot->getRight()->getValue() << endl; cout << "Value of root's left child is: " << hnRoot->getLeft()->getValue() << endl; return 0; } __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates Last edited by nnxion; Mar 31st, 2006 at 4:03 AM. Reason: You had a mistake in setLeft

Mar 31st, 2006, 1:04 PM	#28
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 327 Rep Power: 4	wait so just this... I do not get what this is supposed to do? I get that the code gives a value to root and then to the right and left child and it prints it so it works but then how do i add more and make it look like a tree and stuff? (Toggle Plain Text) #include <iostream> using namespace std; class heapNode { private: int value; //heapNode left; //heapNode right; public: heapNode left; heapNode right; heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } int getValue() { return value; } heapNode* getRight() { return right; } heapNode* getLeft() { return left; } void setValue(int newValue) { value = newValue; } void setRight(heapNode newRight) { right = newRight; } void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: heap() { counter = 0; root = new heapNode(0); } // get root heapNode getRoot() { return root; } void realInsert(int ar, int pos, int newValue) { heapNode newNode; newNode = new heapNode(newValue); if(newNode->left != NULL) { realInsert(ar, pos-1, newValue); if(newNode->left->getValue() < newNode->getValue()) newNode->setValue(newNode->left->getValue()); } else if(newNode->right != NULL) { realInsert(ar, pos-1, newValue); if(newNode->right->getValue() < newNode->getValue()) newNode->setValue(newNode->right->getValue()); } } }; int main() { heap myHeap; myHeap = new heap(); int value = 0, left = 0, right =0; cout << "Please enter a value for your first heap node: "; cin >> value; // get the root heapnode, and set the value of the root heapnode heapNode hnRoot = myHeap->getRoot(); hnRoot->setValue(value); cout << "Please enter a value for right child of your first heap node: "; cin >> right; // make root's right child and add it heapNode hnRight(0); hnRight.setValue(right); hnRoot->setRight(&hnRight); cout << "Please enter a value for right child of your first heap node: "; cin >> left; // make root's left child and add it heapNode hnLeft(0); hnRoot->setLeft(&hnLeft); hnLeft.setValue(left); // print values cout << "Value of root heapnode is: " << hnRoot->getValue() << endl; cout << "Value of root's right child is: " << hnRoot->getRight()->getValue() << endl; cout << "Value of root's left child is: " << hnRoot->getLeft()->getValue() << endl; return 0; } #include <iostream> using namespace std; class heapNode { private: int value; //heapNode left; //heapNode right; public: heapNode left; heapNode right; heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } int getValue() { return value; } heapNode getRight() { return right; } heapNode* getLeft() { return left; } void setValue(int newValue) { value = newValue; } void setRight(heapNode newRight) { right = newRight; } void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: heap() { counter = 0; root = new heapNode(0); } // get root heapNode getRoot() { return root; } void realInsert(int ar, int pos, int newValue) { heapNode newNode; newNode = new heapNode(newValue); if(newNode->left != NULL) { realInsert(ar, pos-1, newValue); if(newNode->left->getValue() < newNode->getValue()) newNode->setValue(newNode->left->getValue()); } else if(newNode->right != NULL) { realInsert(ar, pos-1, newValue); if(newNode->right->getValue() < newNode->getValue()) newNode->setValue(newNode->right->getValue()); } } }; int main() { heap myHeap; myHeap = new heap(); int value = 0, left = 0, right =0; cout << "Please enter a value for your first heap node: "; cin >> value; // get the root heapnode, and set the value of the root heapnode heapNode *hnRoot = myHeap->getRoot(); hnRoot->setValue(value); cout << "Please enter a value for right child of your first heap node: "; cin >> right; // make root's right child and add it heapNode hnRight(0); hnRight.setValue(right); hnRoot->setRight(&hnRight); cout << "Please enter a value for right child of your first heap node: "; cin >> left; // make root's left child and add it heapNode hnLeft(0); hnRoot->setLeft(&hnLeft); hnLeft.setValue(left); // print values cout << "Value of root heapnode is: " << hnRoot->getValue() << endl; cout << "Value of root's right child is: " << hnRoot->getRight()->getValue() << endl; cout << "Value of root's left child is: " << hnRoot->getLeft()->getValue() << endl; return 0; }

Mar 31st, 2006, 2:48 PM	#29
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	You haven't changed anything to what The Dark said, it calls recursively. Why are you? What is supposed to happen to the insert? When is it supposed to swap the values or which value goes left and which goes right? Why are you checking to see if the nodes are NULL when they always are? Think about how it should go, work it out on paper if you have to. I'll try to work it out tomorrow, got to go to sleep now. Good luck! EDIT: Maybe this will help you understand. __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Mar 31st, 2006, 4:03 AM	#22
The Dark Expert Programmer Join Date: Jun 2005 Posts: 816 Rep Power: 4	@nnixion: In that loop, i gets set to -1 and then the loop exits, (the loop still continues when i is 0, as shown by the fact that it prints it out). @cwl157: I can't see how that change would fix up your segfault. The infinite recursion is still there as you only changed the code after the recursion occurs. I still don't get the whole bit-checking thing. I can't see how this could ever make a min-heap, as one of the properties of a min-heap is that each parent node is less than all of its child nodes.

Mar 31st, 2006, 5:39 AM	#24
The Dark Expert Programmer Join Date: Jun 2005 Posts: 816 Rep Power: 4	en-nixion (oops) :o Thats how it sounds in my head, sometimes my fingers listen to my brain instead of typing by themselves.

Mar 31st, 2006, 10:32 AM	#26
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 327 Rep Power: 4	insertSpot is supposed to take a counter and find the next spot to add a value based on the counter. The realInsert is supposed to actually insert the new node in the right spot.

Mar 31st, 2006, 2:58 PM	#30
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 327 Rep Power: 4	i thought calling it recursively is the easiest way to do it. The number is supposed to be inserted in the next available spot going left to right. So the number the user entered is supposed to be added to the next available spot and then you compare that node with all the nodes before it and if its smaller than the parent node you swap the values because the lowest value has to be the root. I am checking when they are null because when one is null thats where the new value goes or something like that? Like i get the idea of inserting and swapping and stuff on paper with a picture of a tree and stuff but i have no clue how it should be programmed or anything.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

pointer help