Thread: need help program crashing

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    44

    need help program crashing

    i am trying to make a Binary Search tree and my program is crashing when i try to insert names from a file into the tree and i cant figure out y. my load file function works if i just read in the names of the file then print them but if i try to put them into the tree it crashes. i dont see anything wrong with my insert function in my BST class

    Key Class

    Code:
    #include <iostream>
    #include <queue>
    #include <fstream>
    #include <string>
    #include <conio.h>
    using namespace std;
    
    // structs/Classes
    /*********************************************************************/
    struct Key {
    	char* data;  // string
    
    	Key();
    	Key(char* data) { this->data = new char[strlen(data)];
    								strcpy(this->data,data);}
    	~Key() {delete data;};
    	Key(Key& key);
    	void print();
    
    	Key& operator= (Key& key);
    	bool operator== (Key& key) { return 0 == strcmp(this->data,key.data);} // is this == to that key
    	bool operator< (Key& key)  { return -1 == strcmp(this->data,key.data);}// is this < that key
    	bool operator> (Key& key)  { return 1 == strcmp(this->data,key.data);} // is this > that key
    };
    
    
    Key::Key()
    {
    	data = NULL;
    }
    
    Key::Key(Key& key)
    {
    	data = key.data;
    }
    
    Key& Key::operator= (Key& key)
    {
    	data = key.data;
    	return *this;
    }
    
    void Key::print()
    {
    	cout << data << endl;
    }

    /************************************************** *******************/

    BST tree class

    Code:
    class BST_Node {
    private:
    	Key key;         // key holds the data
    	BST_Node* left;  // ptr to left subtree
    	BST_Node* right; // ptr to right subtree
    
    public:
    	// Managers
    	BST_Node();
    	BST_Node(Key key);        // Construct given key-data
    	BST_Node(BST_Node& node); // Copy Constructor
    	~BST_Node();              // Destruct node
    
    	// Operators
    	BST_Node& operator= (BST_Node& node); // Assignment
    
    	// Accessors
    	Key getKey() {return key;};         // get Key Data
    	BST_Node* getLeft() {return left;};  // get root of left subtree
    	BST_Node* getRight() {return right;}; // get root of right subtree
    	void setLeft(BST_Node* node);
    	void setRight(BST_Node* node);
    };
    
    BST_Node::BST_Node()
    {
    	key.data = NULL;
    	left = NULL;
    	right = NULL;
    }
    
    BST_Node::BST_Node(Key key)
    {	
    	
    	cout << "enter key" << endl;
    	cin >> key.data;
    
    }
    
    BST_Node::BST_Node(BST_Node& node)
    {
    	right = node.right;
    	left = node.left;
    	//key = node.key;
    }
    
    BST_Node::~BST_Node()
    {
    	delete left;
    	delete right;
    }
    
    BST_Node& BST_Node::operator= (BST_Node& node)
    {
    	right = node.right;
    	left = node.left;
    	//key = node.key;
    	return *this;
    }
    
    void BST_Node::setLeft(BST_Node* node)
    {
    	this->left = node;
    }
    
    void BST_Node::setRight(BST_Node* node)
    {
    	this->right = node;
    }
    /************************************************** *******************/
    BST Class

    Code:
    class BST {
    private:
    	BST_Node* root; // root of tree
    	int size;       // number of elements in tree
    	string inFileName,
    		  outFileName,
    		  name;
    
    	// Mutators - called by public methods
    	bool insert(BST_Node* subRoot, Key key); // insert to subtree (recursive)
    	void preOrder(BST_Node* subRoot);  // preOrder-Traversal of tree (recursive)
    	void inOrder(BST_Node* subRoot);   // inOrder-Traversal of tree (recursive)
    	void postOrder(BST_Node* subRoot); // postOrder-Traversal of tree (recursive)
    
    
    
    public:
    	// Managers
    	BST();         // Construct Empty Tree
    	BST(BST& bst); // Copy Constructor
    	~BST();        // Destruct tree
    	
    	// Operators
    	BST& operator= (BST& bst); // Assignment 
    
    	// Accessors
    	int getSize() {return size;}; // returns number of elements in tree
    	bool empty();  // is tree empty?
    	bool full();   // is memory available?
    	void preOrder();  // preOrder-Traversal of tree (recursive)
    	void inOrder();   // inOrder-Traversal of tree (recursive)
    	void postOrder(); // postOrder-Traversal of tree (recursive)
    	bool findKey();   // take input from user-keyboard
    	bool findKey(Key key);
    	void breadthFirst(); // breadth-First-Traversal of tree
    	bool findKey(Key key, /*BST_Node* parent,*/ BST_Node* foundNode); // given key-data, find node
    	void loadFile();
    	void saveFile();
    
    	// Mutators
    	bool insert();         // take input from user-keyboard
    	bool insert(Key key);  // insert key-data into tree
    	bool delNode();        // take input from user-keyboard
    	bool delNode(Key key); // delete node containing key-data from tree
    	ifstream inFile;
    	ofstream outFile;
    };
    
    BST::BST()
    {
    	size = 0;
    	root = NULL;
    }
    
    BST::BST(BST& bst)
    {
    	root = bst.root;
    	size = bst.size;
    }
    
    BST& BST::operator= (BST& bst)
    {
    	root = bst.root;
    	size = bst.size;
    	return *this;
    }
    
    BST::~BST()
    {
    	delete root->getLeft();
    	delete root->getRight();
    }
    
    bool BST::insert()
    {
    	Key key;
    	cout << "Enter a key" << endl;
    	cin >> key.data;
    	return insert(key);
    }
    
    bool BST::insert(BST_Node* subRoot, Key key)
    {
    	BST_Node* node = new BST_Node(key);
    	if(subRoot == NULL)
    	{
    		subRoot = node;
    		return true;
    	}
    	if(key == subRoot->getKey())
    	{
    		return false;
    		delete node;
    	}
    	if(key < subRoot->getKey())
    	{
    		if(subRoot->getLeft() == NULL)
    		{
    			root->setLeft(new BST_Node(key));
    			return true;
    		}
    		else
    		{
    			return insert(subRoot->getRight(), key.data);
    			
    		}
    		return true;
    	}
    	return false;
    }
    
    bool BST::empty()
    {
    	return root == NULL;
    }
    
    bool BST::full()
    {
    	BST_Node* bstnode = new BST_Node;
    	if(!bstnode)
    	{
    		return true;
    	}
    	else
    	{
    		delete bstnode;
    		return false;
    	}
    }
    
    bool BST::insert(Key key)
    {
    	return insert(root, key);
    }
    
    bool BST::findKey()
    {
    	Key key;
    	cout << "What would you like to find" << endl;
    	cin >> key.data;
    	return findKey(key);	
    }
    
    bool BST::findKey(Key key) 
    {
    	if(root == NULL)
    		return false;
    	
    	return findKey(key, /*root,*/ root);
    }
    
    bool BST::findKey(Key key, /*BST_Node* parent,*/ BST_Node* foundNode)
    {
    
    	if(foundNode == NULL)
    		return false;
    	else if(key.data == foundNode->getKey().data)
    			return true;
    	else if(key.data < foundNode->getKey().data)
    	{
    		return findKey(key, foundNode->getLeft());
    			
    	}
    	else if(key.data > foundNode->getKey().data)
    	{
    		return findKey(key, foundNode->getRight());
    	}
    	else
    		return false;
    }
    
    void BST::inOrder()
    {
    	inOrder(root);
    }
    
    void BST::inOrder(BST_Node* subRoot)
    {
    	if(subRoot == NULL)
    		return;
    	inOrder(subRoot->getLeft());
    	subRoot->getKey().print();
    	inOrder(subRoot->getRight());
    	
    }
    
    void BST::preOrder()
    {
    	preOrder(root);
    }
    
    void BST::preOrder(BST_Node* subRoot)
    {
    	//base case
    	if(subRoot == NULL)
    		return;
    	//process
    	subRoot->getKey().print();
    	//go left
    	preOrder(subRoot->getLeft());
    	//go right
    	preOrder(subRoot->getRight());		
    }
    
    void BST::postOrder()
    {
    	postOrder(root);
    }
    
    void BST::postOrder(BST_Node* subRoot)
    {
    	if (root == NULL)
    		return;
    	postOrder(subRoot->getLeft());
    	postOrder(subRoot->getRight());
    	subRoot->getKey().print();
    }
    
    void BST::breadthFirst()
    {
    	queue <BST_Node*>q;
    	if (root == NULL)
    		return;
    
    	q.push(root);
    	while (!q.empty())
    	{
    		if(root->getLeft() != NULL)
    			q.push(root->getLeft());
    		if(root->getRight() != NULL)
    			q.push(root->getRight());
    		q.front()->getKey().print();
    		q.pop();
    	}	
    }
    
    bool BST::delNode()
    {
    	Key key;
    	cout << "What do you want to delete?" << endl;
    	cin >> key.data;
    	return delNode(key);
    }
    
    bool BST::delNode(Key key)
    {
    	BST_Node* node = root;
    
    	if(findKey(key,root))
    	{
    		if(root == NULL)
    			return false;
    		if(root->getLeft() == NULL)
    		{
    			root = root->getRight();
    			delete node;
    			return false;
    		}
    		else if(root->getRight() == NULL)
    		{
    			root = root->getLeft();
    			delete node;
    			return false;
    		}
    		else
    		{
    			node = root->getLeft();
    			while(node->getRight() != NULL)
    				node = node->getRight();
    			return true;
    		}
    		root->getKey() = node->getKey();
    		delNode(key);
    	/*	else if(key < root->getKey().data)
    			root = root->getLeft();
    		if(key == root->getKey())
    		{
    			delete key.data;
    			return true;
    		}
    
    		else if(root->getLeft() == NULL)
    		{
    			p = root->getRight();
    			free(root);
    			return false;
    		}
    		else if(root->getRight() == NULL)
    		{
    			p = root->getLeft();
    			free(root);
    			return false;
    		}
    		else
    		{
    			node = root->getRight();
    			p = root->getRight();
    			while (p->getLeft())
    			{
    				p = p->getLeft();
    			}
    			p->setLeft(root->getLeft());
    			free(root);
    			return true;
    		}
    		if(root->getKey() < key)
    		{
    			root->getLeft() = delete key.data;
    			return true;
    		}
    		else
    		{
    			root->setRight();
    			return true;
    		}*/
    	}
    	else 
    		return false;
    }
    
    void BST::loadFile()
    {
    	Key key;
    	cout << "Enter the the file location" << endl;
    	cin >> inFileName;
    	inFile.open(inFileName.c_str());
    	if (!inFile.is_open())  //test for file
    	{
    		cerr << "Cannot open file: " << inFileName << endl;
    		getche();
    	}
    	while(!inFile.eof()) //loop through untill end of file
    	{ 
    		inFile >> name; 
    		/*if(key.data == NULL)
    			return;
    		else
    			insert(key);*/
    
    		cout << name << endl; 
     
    	}// end obtain info 
    
    	inFile.close();//close infile
    }
    
    void BST::saveFile()
    {
    	Key key;
    	cout << "Enter where you want to save the file" << endl;
    	cin >> outFileName;
    	outFile.open(outFileName.c_str());
    	if(!outFile.is_open())
    	{
    		cerr << "Cannot open file: " << outFileName << endl;
    		getche();
    	}
    	else
    	{
    		outFile << key.data << endl;
    	}
    	outFile.close();//close outfile
    }
    /************************************************** *******************/
    Code:
    int menu();
    
    void main () {
    
    	BST bst;
    
    	switch(menu())
    	{
    		case 1:
    			bst.inOrder();
    			break;
    		case 2:
    			bst.preOrder();
    			break;
    		case 3:
    			bst.postOrder();
    			break;
    		case 4:
    			bst.breadthFirst();
    			break;
    		case 5:
    			bst.loadFile();
    			break;
    		case 6:
    			bst.saveFile();
    			break;
    		case 7:
    			bst.insert();
    			break;
    		case 8: 
    			//bst.delNode();
    			break;
    		case 9:
    			bst.findKey();
    			break;
    		case 10:
    			break;
    		default:
    			break;
    	}
    }
    
    int menu()
    {
    	int choice;
    	cout << "________________BST________________\n" << endl;
    	cout << "1) Print In-Order Traversal\n"
    		 <<	"2) Print Pre-Order Traversal\n"
    		 << "3) Print Post-Order Traversal\n"
    		 << "4) Print Breadth-First Traversal\n"
    		 <<	"5) Load BST from file\n"
    		 <<	"6) Save BST to file\n"
    		 <<	"7) Add to tree\n"
    		 << "8) Delete from tree\n"
    		 <<	"9) Find a value in tree\n"
    		 <<	"10) Quit Program" << endl;
    	cout << "Enter your choice" << endl;
    	cin >> choice;
    
    	return choice;
    }

  2. #2
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    Code:
    	Key(char* data) { this->data = new char[strlen(data)];
    								strcpy(this->data,data);}
    strlen + 1 for null.

    Code:
    ~Key() {delete data;};
    ~Key() {delete [] data;}
    Code:
    bool operator< (Key& key)  { return -1 == strcmp(this->data,key.data);}
    It may not work like that. strcmp will just return less than 1.

    Code:
    bool operator< (Key& key)  { return strcmp(this->data,key.data) < 0;}
    bool operator> (Key& key)  { return strcmp(this->data,key.data); > 0}

  3. #3
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    I don't know if this will fix your crashing, but I think you want to take a reference to a key rather than a key in your BST(key) constructor. Also, your Key class copy constructor should be implemented properly. Currently, a Key shares the string memory of the Key it's copied from. When the first one dies, your key deallocates the memory, and then the second Key has a pointer to deallocated data. That's bad.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    By implement properly, I mean that you should probably just copy the string data.

    Alternatively, just use an stl string (from <string>) rather than your Key class (if allowed), as it looks like the Key functionality is a subset of the string functionality.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    44
    Quote Originally Posted by SilentStrike
    I don't know if this will fix your crashing, but I think you want to take a reference to a key rather than a key in your BST(key) constructor. Also, your Key class copy constructor should be implemented properly. Currently, a Key shares the string memory of the Key it's copied from. When the first one dies, your key deallocates the memory, and then the second Key has a pointer to deallocated data. That's bad.
    ur right i missed that thx. but no that didnt fix it im positive its mostly my insert function cause when i take it out and just read the file then print it it prints out all the names but then crashes for some reason. i dunno if its having a problem closing the file or what.

    Quote Originally Posted by Tonto
    It may not work like that. strcmp will just return less than 1.


    Code:
    bool operator< (Key& key)  { return strcmp(this->data,key.data) < 0;}
    bool operator> (Key& key)  { return strcmp(this->data,key.data); > 0}
    if i do that i get warnings

    warning C4800: 'int' : forcing value to bool 'true' or 'false' (performance warning)

    never had that one b4.

  6. #6
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    Code:
    bool operator> (Key& key)  { return strcmp(this->data,key.data) > 0;}
    Woops.

  7. #7
    Registered User
    Join Date
    Mar 2006
    Posts
    44
    k got rid of thoes errors but it still crashes

  8. #8
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    "it crashes" That's nice.

    Where does it crash? Answering that will usually lead you to cause of the crash quite quickly. So, where does it crash? Not everyone on the boards will want to compile your code themselves.

    If you're using gcc, you can do this:
    Compile your program with the -g switch passed to gcc. (ie: "gcc -g -c -o myfile.o myfile.c") This gives a debug build. Then run your program with gdb. (ie: "gdb myprogram") Type "run", crash your program, and gdb will tell you how & where it crashed.
    If you're not using gcc, read the documentation on your compiler & debugger.

    If none of that works for you, one can always insert lots of printf() or cout statements in the code. But that takes a while, and isn't pretty to do.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  9. #9
    Registered User
    Join Date
    Mar 2006
    Posts
    44
    ok so i narrowed it down to my loadFile function wher i read the file in

    Code:
    void BST::loadFile()
    {
    	Key key;
    	cout << "Enter the the file location" << endl;
    	cin >> inFileName;
    	inFile.open(inFileName.c_str());
    	if (!inFile.is_open())  //test for file
    	{
    		cerr << "Cannot open file: " << inFileName << endl;
    		getche();
    	}
    	while(!inFile.eof()) //loop through untill end of file
    	{ cout << "hi" << endl;
    		inFile >> key.data;
    		
    		if(key.data == NULL)
    			return;
    		else
    			insert(key);
    
    		cout << name << endl; 
     
    	}// end obtain info 
    	cout << "hi" << endl;
    
    	inFile.close();//close infile
    }
    it displays the first "hi" b4 the inFile >> key.data and thast where it stops.

    what is wrong there??

  10. #10
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Don't use eof() to control a while loop, it doesn't work as you expect. You commonly get junk after you read the last line of the file. Instead you can just use the insertion operator.
    Code:
    while (inFile >> key.data)
    It will fail correctly when there is no more data. That might or might not fix your problem, but that needs to be done anyway.
    Last edited by whiteflags; 05-21-2006 at 03:55 PM.

  11. #11
    Registered User
    Join Date
    Mar 2006
    Posts
    44
    k i fixed that but it didnt fix the problem though

  12. #12
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    key.data is a pointer to a char, and you don't allocate any space for it (as far as I can see) Since this is C++ you might as well stick with std::strings (especially since you're using them elsewhere)
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  13. #13
    Registered User
    Join Date
    Mar 2006
    Posts
    44
    isn this allocating mem for it??? that part was given by teacher so i just assumed it was

    Code:
    Key(char* data) { this->data = new char[strlen(data)];
    								strcpy(this->data,data);}

  14. #14
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    No. It would allocate memory for it; however, you implicitly call the default constructor:
    Code:
    Key::Key()
    {
    	data = NULL;
    }
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  15. #15
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Key(char* data) { this->data = new char[strlen(data)];
    I told you over a week ago on another board that you need to add 1 to this to account for the \0
    Tonto said the same thing a couple of days ago.
    If you STILL haven't changed it, start paying attention.

    Better yet, use std::string for everything, because dynamic memory isn't for you.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 11:17 PM
  2. Can someome help me with a program please?
    By WinterInChicago in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2006, 10:58 PM
  3. Need help with my program...
    By Noah in forum C Programming
    Replies: 2
    Last Post: 03-11-2006, 07:49 PM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM