need help deallocating

This is a discussion on need help deallocating within the C++ Programming forums, part of the General Programming Boards category; All in all my program works how I want it to except that when it's done running, I have some ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    4

    Question need help deallocating

    All in all my program works how I want it to except that when it's done running, I have some active allocations that I want to get rid of. I was introduced to pointers a couple of months ago and my Chop function is my feeble attempt to deallocate (i don't know if that's even the right term). What needs to be deallocated and what's a good way to go about doing it? Thanks for the help.

    with the test data:

    1
    a
    1
    a
    print

    I end up with two active allocations


    Code:
    #include <iostream>
    #include<string>
    #include<sstream>
    using namespace std;
    
    template <class T>
    struct NodeType{
    	T info;
    	NodeType  * left;
    	NodeType  * right;
    };	
    template<class T>
    struct Tree{
    	NodeType<T> * root;
    };
    template<class T>
    T GetSuccessor(NodeType<T> *& successor){
    	successor = successor->right;
    	while(successor->left!=NULL)
    		successor = successor->left;
    	return successor->info;
    }
    template<class T>
    NodeType<T> * Retrieve(Tree<T> myTree, T item){
    	NodeType<T> * node = myTree.root;
    	while(item != node->info){
    		if(item < node->info)
    			node = node->left;
    		else
    			node = node->right;
    	}
    	return node;
    }
    template<class T>
    void Insert(NodeType<T> *& node, T item){	
    	if(node == NULL){
    		node = new NodeType<T>;
    		node->left = NULL;
    		node->right = NULL;
    		node->info = item;		
    	}
    	else if(item < node->info)
    		Insert(node->left, item);
    	else
    		Insert(node->right, item);
    }
    template<class T>
    void Delete(Tree<T> & myTree, T item){
    	NodeType<T> * node = myTree.root;
    	NodeType<T> * parent = myTree.root;
    	while(item!=node->info){
    		parent = node;
    		if(item < node->info){
    			node = node->left; 
    			}
    		else{
    			node = node->right;
    			}
    	}//node = the node to be deleted
    	
    	bool isleft = (parent->left==node);		//true if the node to be deleted is a left child
    	
    	//if the node is a leaf
    	if(node->right==NULL && node->left==NULL){		
    		if(myTree.root->info == item)
    			myTree.root = NULL;
    		else if(isleft)
    			parent->left = NULL;
    		else
    			parent->right = NULL;
    	}
    	//else the node has two children
    	else if(node->right!=NULL && node->left!=NULL){			
    		//cout << "Deleting node->info: " << node->info << endl;
    		T data = GetSuccessor(node);		//get the successor
    		node = Retrieve(myTree, item);
    		Delete(myTree, data);
    		node->info = data;
    	}	
    	//if the node's only child is left
    	else if(node->left!=NULL){									
    		if(node == myTree.root)										//if the node to be deleted is the root
    			myTree.root = node->left;								//the root is now it's left (and only) child
    		else if(isleft)															//check if the node to be deleted is a left child
    			parent->left = node->left;									//if so replace the parent's left child with the node's left child
    		else																		//else the node is a right child
    			parent->right = node->left;								//so replace the parent's right child with the node's left child
    	}
    	//if the node's only child is right	
    	else if(node->right!=NULL){										
    		if(node == myTree.root)										//if the node to be deleted is the root
    			myTree.root = node->right;								//the root is now it's right (and only) child
    		else if(isleft)															//check if the node to be deleted is a left child
    			parent->left = node->right;								//if so replace the node's parent's left child with the node's right child
    		else																		//else the node is a right child
    			parent->right = node->right;								//so replace the node's parent's right child with the node's right child
    	}
    }
    template <class T>
    void Chop(NodeType<T> * n){
    	if(n!=NULL){
    		if(n->left!=NULL)
    			Chop(n->left);
    		if(n->right!=NULL)
    			Chop(n->right);
    	}
    	delete n;
    }
    template<class T>
    void PrintChildren(NodeType<T> *& n){
    	cout << " [";
    	if(n->left!=NULL && n->right!=NULL)	cout << "left, right";
    	else if(n->left!=NULL) cout << "left";
    	else if(n->right!=NULL)	cout << "right";
    	cout << "]" << endl;
    }
    template <class T>
    void InOrder(NodeType<T> *& n){
    	if(n == NULL)
    		cout << " empty tree.";
    	else{
    		if(n->left != NULL)
    			InOrder<T>(n->left);
    		cout << " " << n->info;
    		//PrintChildren<T>(n);
    		if(n->right != NULL)
    			InOrder<T>(n->right);	
    	}
    }
    template <class T>
    void PreOrder(NodeType<T> *& n){
    	if(n == NULL)
    		cout << " empty tree.";
    	else{
    		cout << " " << n->info;
    		//PrintChildren<T>(n);
    		if(n->left != NULL)
    			PreOrder<T>(n->left);
    		if(n->right != NULL)
    			PreOrder<T>(n->right);
    	}
    }
    template <class T>
    void PostOrder(NodeType<T> *& n){
    	if(n == NULL)
    		cout << "empty tree.";
    	else{
    		if(n->left != NULL)
    			PostOrder<T>(n->left);
    		if(n->right != NULL)
    			PostOrder<T>(n->right);
    		cout << " " <<  n->info;
    		//PrintChildren<T>(n);
    	}
    }
    template <class T>
    void PrintDot(NodeType<T> *& n){
    	if(n == NULL)
    		cout << "empty tree.";
    	else{
    		if(n->left!=NULL){
    			cout << n->info << "->" << n->left->info << " [label=L];\n";
    			PrintDot(n->left);		
    		}
    		if(n->right!=NULL){
    			cout << n->info << "->" << n->right->info << " [label=R];\n";
    			PrintDot(n->right);
    		}
    	}
    }
    
    int main(){
    	Tree<string> myTree;
    	int n;
    	string key;
    	string str;	
    	string item;
    	myTree.root = NULL;
    	//inserts
    	cin >> n;
    	for(int i=0;i<n;i++){
    		cin >> item;
    		Insert<string>(myTree.root, item);		
    	}
    	//deletes
    	cin >> n;
    	for(int i=0;i<n;i++){
    			cin >> key;
    			Delete<string>(myTree, key);
    	}
    	//print
    	cin >> str;
    	if(str == "print"){
    		cout << "InOrder:";
    		InOrder<string>(myTree.root);
    	}
    	else if(str == "printpre"){
    		cout << "PreOrder:";
    		PreOrder<string>(myTree.root);
    	}
    	else if(str == "printpost"){
    		cout << "PostOrder:";
    		PostOrder<string>(myTree.root);
    	}
    	else if(str == "dot"){
    		cout << "digraph \"Binary Search Tree\" {\n";
    		PrintDot<string>(myTree.root);
    		cout << "}" << endl;
    		}
    	//empty tree
    	Chop(myTree.root);	
    }


    Also, is it possible to configure my mingw compiler to tell me how many active allocations there are after running a program such as this?

  2. #2
    Registered User
    Join Date
    Feb 2010
    Posts
    38
    Also, is it possible to configure my mingw compiler to tell me how many active allocations there are after running a program such as this?
    If you're on Linux, you should give Valgrind a try.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    4
    thanks, but i'm using windows. not that i prefer it...

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Chop will delete all the nodes that are still in the tree when you call it. Nodes that had been in the tree, but were Deleted, are still in limbo somewhere.

  5. #5
    Registered User
    Join Date
    Apr 2010
    Posts
    4
    wow, thank you! i've been trying to figure that out for days.

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,703
    Quote Originally Posted by kocaloka View Post
    Also, is it possible to configure my mingw compiler to tell me how many active allocations there are after running a program such as this?
    You don't need to. Use a smart pointer and be done with it.
    Code:
    bool flip(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() < 0;
    }

  7. #7
    Registered User
    Join Date
    Apr 2010
    Posts
    4
    Quote Originally Posted by Sebastiani View Post
    You don't need to. Use a smart pointer and be done with it.
    i'd love to, only i don't know what to do with that code you posted or what it is...

  8. #8
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,703
    Quote Originally Posted by kocaloka View Post
    i'd love to, only i don't know what to do with that code you posted or what it is...
    Unrelated. It's called a "signature" (attaches to every post). That particular bit of code just dumps a bunch of rubbish to the console, basically.

    Anyway, just google "smart pointer". The Boost library has a pretty decent set of them, too.
    Last edited by Sebastiani; 04-08-2010 at 11:58 PM.
    Code:
    bool flip(bool value)
    {
        return std::pow(std::exp(1), std::complex<float>(0, 1) 
        * std::complex<float>(std::atan(1)*(1 << (value + 2))))
        .real() < 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 10
    Last Post: 08-12-2008, 03:42 AM
  2. Deallocating memory for a linked list
    By Mandy_C in forum C Programming
    Replies: 14
    Last Post: 04-11-2006, 12:55 AM
  3. Deallocating Memory allocated to a pointer to a pointer
    By darklord1984 in forum C++ Programming
    Replies: 8
    Last Post: 12-31-2005, 10:09 AM
  4. Deallocating a character pointer array
    By cunnus88 in forum C++ Programming
    Replies: 8
    Last Post: 11-12-2005, 10:22 PM
  5. allocating and deallocating
    By kuwait in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2003, 01:28 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21