Programming Forums > Application Development > C++

DaWei · Mar 30th, 2006, 6:25 PM

Quote:

you know this is going to loop until i == -1, right?

Actually, it'll loop until i 'rolls around' to the largest negative number.

The Dark · Mar 30th, 2006, 7:32 PM

Nope, jayme is right -1

DaWei · Mar 30th, 2006, 7:44 PM

Excuse me? There must be some dreadful misunderstanding on my part.

(Toggle Plain Text)

#include <iostream>

using std:: cout;
using std:: endl;
using std:: cin;

int main (int argc, char *argv [])
{
    char i, j;
    for (i = 120; i >= 0; i++) cout << (int) i << endl;
    cout << endl << "Next few : \n" <<  endl;
    j = 5;
    while (j--) cout << (int) i++ << endl;
    cin.get ();
    return 0;
}

Quote:

Originally Posted by Output

120
121
122
123
124
125
126
127

Next few :

-128
-127
-126
-125
-124

The Dark · Mar 30th, 2006, 8:41 PM

Yes, I am afraid so

Quote:

Originally Posted by jayme

(Toggle Plain Text)

for(int i = 31; i >= 0; i--)

four posts up, first [code] tags, you know this is going to loop until i == -1, right?

Jayme is commenting on the code that is in his post, not on some other code that doesn't seem to be in this thread.

cwl157 · Mar 30th, 2006, 9:55 PM

Quote:

if you trace through your realInsert code, you can see where it will crash (comments in red)

Ok so the problem makes sense but I have no clue how to fix it. I have never done anything recursively in a program before nor programmed any kind of tree before nor extensivley used pointers before so i am really new to all of this. I'll repost the code because i think there are a couple changes.

(Toggle Plain Text)

#include <iostream>
using namespace std;

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

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

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

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

  // set left
  void setLeft(heapNode *newLeft)
  {
    right = newLeft;
  }
  
}; // end of heapNode class

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

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  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());
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    int arrayValue;
    bool isOne = false;
    int ar[32];
    int i = 31;
    for(int i = 0; i < 32; i++)
    {
        arrayValue = option % 2;
        option = option / 2;
        ar[i] = arrayValue;
    }
 
    for(int i = 0; i < 32; i++)
      cout << ar[i] << " ";
    cout << endl;

    while(i > 0)
    {

      if(ar[i] == 1)
        isOne = true;
      if(isOne = true)
        break;
      i--;
    }
    realInsert(*ar, i, option);
  }

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

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=0;
  //while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    //}
  return 0;
}

#include <iostream>
using namespace std;

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

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

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

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

  // set left
  void setLeft(heapNode *newLeft)
  {
    right = newLeft;
  }
  
}; // end of heapNode class

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

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  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());
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    int arrayValue;
    bool isOne = false;
    int ar[32];
    int i = 31;
    for(int i = 0; i < 32; i++)
    {
        arrayValue = option % 2;
        option = option / 2;
        ar[i] = arrayValue;
    }
 
    for(int i = 0; i < 32; i++)
      cout << ar[i] << " ";
    cout << endl;

    while(i > 0)
    {

      if(ar[i] == 1)
        isOne = true;
      if(isOne = true)
        break;
      i--;
    }
    realInsert(*ar, i, option);
  }

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

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=0;
  //while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    //}
  return 0;
}

The Dark · Mar 31st, 2006, 1:37 AM

I'm not entirely sure what you are trying to achieve. You are finding out a lot of yes/no values for each bit in the original value, are you intending to use these to position the new node in the heap? If so, all of your leaf nodes will be 32 levels deep, which doesn't look like a heap to me (I could be wrong).

If this is what you want (and I don't think it is), your recursive insert function would need a pointer to appropriate spot in the array ar passed in (not just the first element as you do now). Then at each level, if the ar[level] value is true then you check the right node, if it is NULL, create it, if not just recurse down to it. Same for the left node if the ar[level] value is false.

cwl157 · Mar 31st, 2006, 2:13 AM

i need to enter and print a min heap and then delete the top level. The array of 1 and 0 is supposed to be where i put the number when i enter it. If the number is a 1 it moves right and if its 0 it moves left. Then it checks and if the left or right is NULL it puts it there if not it keeps going until it finds a NULL and puts it there. In the recersive method realInsert i changed it to say

(Toggle Plain Text)

 newNode->left != NULL and newNode->right != NULL

and that got rid of the segmentation fault. However, now it just prints the array of 0 and 1. How do i know if it added the number? How do i set up the print method because i know that is recursive too right?

cwl157 · Mar 31st, 2006, 2:41 AM

ok i have updated code with a recursive print method. I can enter numbers fine but i get a segmentation fault when printing. Here is the updated code:

(Toggle Plain Text)

#include <iostream>
using namespace std;

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

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

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

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

  // set left
  void setLeft(heapNode *newLeft)
  {
    right = newLeft;
  }
  
}; // end of heapNode class

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

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  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());
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    int arrayValue;
    bool isOne = false;
    int ar[32];
    int i = 31;
    for(int i = 0; i < 32; i++)
    {
        arrayValue = option % 2;
        option = option / 2;
        ar[i] = arrayValue;
    }
 
    for(int i = 0; i < 32; i++)
      cout << ar[i] << " ";
    cout << endl;

    while(i > 0)
    {

      if(ar[i] == 1)
        isOne = true;
      if(isOne = true)
        break;
      i--;
    }
    realInsert(*ar, i, option);
  }

  void print()
  {
    cout << root->left
         << root->right;
    if(root->left != NULL && root->right != NULL)
    {
      print();
    }
  }
  // get root
  heapNode* getRoot()
  {
    return root;
  }
  

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    }

  myHeap->print();
  return 0;
}

#include <iostream>
using namespace std;

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

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

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

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

  // set left
  void setLeft(heapNode *newLeft)
  {
    right = newLeft;
  }
  
}; // end of heapNode class

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

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  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());
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    int arrayValue;
    bool isOne = false;
    int ar[32];
    int i = 31;
    for(int i = 0; i < 32; i++)
    {
        arrayValue = option % 2;
        option = option / 2;
        ar[i] = arrayValue;
    }
 
    for(int i = 0; i < 32; i++)
      cout << ar[i] << " ";
    cout << endl;

    while(i > 0)
    {

      if(ar[i] == 1)
        isOne = true;
      if(isOne = true)
        break;
      i--;
    }
    realInsert(*ar, i, option);
  }

  void print()
  {
    cout << root->left
         << root->right;
    if(root->left != NULL && root->right != NULL)
    {
      print();
    }
  }
  // get root
  heapNode* getRoot()
  {
    return root;
  }
  

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    }

  myHeap->print();
  return 0;
}

nnxion · Mar 31st, 2006, 2:52 AM

Quote:

Originally Posted by jayme

(Toggle Plain Text)

for(int i = 31; i >= 0; i--)

you know this is going to loop until i == -1, right?

I must be missing something but this loops until i == 0.

(Toggle Plain Text)

#include <iostream>

using namespace std;

int main()
{
	for(int i = 31; i >= 0; i--)
		cout << i << endl;

	return 0;
}

Quote:

Originally Posted by output

31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

EDIT: @cwl157:
something.cpp(110) : warning C4288: nonstandard extension used : 'i' : loop control variable declared in the for-loop is used outside the for-loop scope; it conflicts with the declaration in the outer scope.

Please fix those issues first. And change your constructor or whatever to do change that what The Dark told you.

@DaWei: You declare them as char though?

cwl157 · Mar 31st, 2006, 3:11 AM

i think i want the left and right to initialize to NULL because then it creates a node with a space to hold an int and 2 NULL pointers to the 2 children. I thought that is what i want?

Mar 31st, 2006, 2:13 AM	#17
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 343 Rep Power: 4	i need to enter and print a min heap and then delete the top level. The array of 1 and 0 is supposed to be where i put the number when i enter it. If the number is a 1 it moves right and if its 0 it moves left. Then it checks and if the left or right is NULL it puts it there if not it keeps going until it finds a NULL and puts it there. In the recersive method realInsert i changed it to say (Toggle Plain Text) newNode->left != NULL and newNode->right != NULL newNode->left != NULL and newNode->right != NULL and that got rid of the segmentation fault. However, now it just prints the array of 0 and 1. How do i know if it added the number? How do i set up the print method because i know that is recursive too right?

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

Mar 30th, 2006, 7:32 PM	#12
The Dark Expert Programmer Join Date: Jun 2005 Posts: 852 Rep Power: 4	Nope, jayme is right -1

Mar 31st, 2006, 1:37 AM	#16
The Dark Expert Programmer Join Date: Jun 2005 Posts: 852 Rep Power: 4	I'm not entirely sure what you are trying to achieve. You are finding out a lot of yes/no values for each bit in the original value, are you intending to use these to position the new node in the heap? If so, all of your leaf nodes will be 32 levels deep, which doesn't look like a heap to me (I could be wrong). If this is what you want (and I don't think it is), your recursive insert function would need a pointer to appropriate spot in the array ar passed in (not just the first element as you do now). Then at each level, if the ar[level] value is true then you check the right node, if it is NULL, create it, if not just recurse down to it. Same for the left node if the ar[level] value is false.

Mar 31st, 2006, 2:41 AM	#18
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 343 Rep Power: 4	ok i have updated code with a recursive print method. I can enter numbers fine but i get a segmentation fault when printing. Here is the updated code: (Toggle Plain Text) #include <iostream> using namespace std; class heapNode { private: int value; //heapNode left; //heapNode right; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode* getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { right = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } 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()); } } // find the spot to put new value void insertSpot(int option) { int arrayValue; bool isOne = false; int ar[32]; int i = 31; for(int i = 0; i < 32; i++) { arrayValue = option % 2; option = option / 2; ar[i] = arrayValue; } for(int i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; while(i > 0) { if(ar[i] == 1) isOne = true; if(isOne = true) break; i--; } realInsert(ar, i, option); } void print() { cout << root->left << root->right; if(root->left != NULL && root->right != NULL) { print(); } } // get root heapNode getRoot() { return root; } /* int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class int main() { heap myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); } myHeap->print(); return 0; } #include <iostream> using namespace std; class heapNode { private: int value; //heapNode left; //heapNode right; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { right = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } 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()); } } // find the spot to put new value void insertSpot(int option) { int arrayValue; bool isOne = false; int ar[32]; int i = 31; for(int i = 0; i < 32; i++) { arrayValue = option % 2; option = option / 2; ar[i] = arrayValue; } for(int i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; while(i > 0) { if(ar[i] == 1) isOne = true; if(isOne = true) break; i--; } realInsert(ar, i, option); } void print() { cout << root->left << root->right; if(root->left != NULL && root->right != NULL) { print(); } } // get root heapNode getRoot() { return root; } /* int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class int main() { heap *myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); } myHeap->print(); return 0; }

Mar 31st, 2006, 3:11 AM	#20
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 343 Rep Power: 4	i think i want the left and right to initialize to NULL because then it creates a node with a space to hold an int and 2 NULL pointers to the 2 children. I thought that is what i want?

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

Programming Forums > Application Development > C++

pointer help