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

---

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}

---

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.

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.

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.

Code:

---

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

---

Woops.

k got rid of thoes errors but it still crashes

"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.

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??

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.

k i fixed that but it didnt fix the problem though

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)

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

---

No. It would allocate memory for it; however, you implicitly call the default constructor:

Code:

---

Key::Key()
{
        data = NULL;
}

---

> 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.