I have insert working, and i have preorder,inorder,and post order working. I am working on retrieveItem where i try to find using a key. Thats when i realize that in my driver file(main()) that my class instance holds no information.( data aData) So, that makes it impossible to do the retrieve.
Down in main() i have data aData;
Thats where aData contains nothing. But it needs to have the name so i can do retrieveItem. I can get name, and name contains items.
I will give pretty much all the code so you can see where i am going wrong?
using namespace std;
static BST database;
static void displayDatabase(bool all)
{
database.displayArrayOrder(cout);
cout << endl;
if (! all)
return;
database.displayPreOrder(cout);
cout << endl;
database.displayInOrder(cout);
cout << endl;
database.displayPostOrder(cout);
cout << endl;
}
static void retrieveItem(char *name, data& aData)
{
cout << ">>> retrieve " << name << endl << endl;
if (database.retrieve(name, aData))
cout << aData << endl;
else
cout << "not found\n";
cout << endl;
}
static void removeItem(char *name)
{
cout << ">>> remove " << name << endl << endl;
if (database.remove(name))
cout << name << " removed\n";
else
cout << name << " not found\n";
cout << endl;
}
int main()
{
#ifdef _WIN32
// request memory leak report in Output Window after main returns
_CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );
#endif
data aData;
<< "Database Of Great Computer Scientists\n\n";
database.insert(data("Ralston, Anthony"));
database.insert(data("Liang, Li"));
database.insert(data("Jones, Doug"));
database.insert(data("Goble, Colin"));
database.insert(data("Knuth, Donald"));
database.insert(data("Kay, Alan"));
database.insert(data("Von Neumann, John"));
database.insert(data("Trigoboff, Michael"));
database.insert(data("Turing, Alan"));
displayDatabase(true);
retrieveItem("Trigoboff, Michael", aData);
retrieveItem("Kaye, Danny", aData);
removeItem("Ralston, Anthony");
displayDatabase(true);
removeItem("Jones, Doug");
displayDatabase(true);
Headers...
#ifndef BST_H
#define BST_H
#include "data.h"
class BST
{
public:
BST(int capacity = 5); // constructor (default if no arg supplied)
BST(const BST& aTable); // copy constructor
~BST(); // destructor
void insert(const data& aData);
bool remove(const char *key);
bool retrieve(const char *key, data& aData) const;
void displayArrayOrder(ostream& out) const;
void displayPreOrder(ostream& out) const;
void displayInOrder(ostream& out) const;
void displayPostOrder(ostream& out) const;
int getSize(void) const;
private:
int size;
int maxsize;
int parent;
void expand();
struct item
{
bool empty;
data instanceData;
};
item *items;
void insert(int index, const data & aData );
void displayHeaders(ostream& out)const;
void BST::displayPreOrder(std::ostream &out, int parent)const;
void BST::displayInOrder(std::ostream &out, int parent)const;
void BST::displayPostOrder(std::ostream &out, int parent)const;
};
#endif // BST_H
last header...
#ifndef DATA_H
#define DATA_H
#include <ostream>
using namespace std;
class data
{
public:
data() : name(NULL) {} // default constructor
data(char const * const name); // constructor
~data(); // destructor
data& operator=(const data& data2);
char const * const getName() const;
void setName(char const * const name);
private:
char * name;
friend ostream& operator<< (ostream& out, const data& outData);
friend bool operator< (const data& d1, const data& d2);
friend bool operator== (const data& d1, const data& d2);
};
BST.cpp - i wont include the code for inorder,preorder, etc...
#include "BST.h"
#include <iostream>
#include <iomanip>
using namespace std;
BST::BST(int capacity) : size(0), parent(0),
items(new item[capacity])
{
maxsize = capacity;
items->empty = true;
}
BST::~BST()
{
//delete items;
delete [] items;
}
void BST::insert(int parent, const data &aData)
{
if(parent >= maxsize)
{
this->expand();
}
if (items[parent].empty)
{
items[parent].instanceData = aData;
items[parent].empty = false;
size++;
}
else if (aData < items[parent].instanceData) // indicates we want this to be the left child
{
parent = (2 * parent)+ 1;
this->insert(parent,aData);
}
else // indicates we want this to be the right child.
{
parent = (2 * parent)+ 2;
this->insert(parent,aData);
}
}
// insert a new item into the BST
void BST::insert (const data& aData)
{
this->insert(parent, aData);
}
void BST::expand()
{
item *swap = new item[maxsize*2];
for ( int index = 0; index < maxsize; index++ )
{
if ( !items[index].empty )
{
swap[index].instanceData = items[index].instanceData;
swap[index].empty = false;
}
}
maxsize += size;
delete [] items;
items = NULL;
items = swap;
}
bool BST::retrieve(const char *key, data& aData) const
{
if (parent <= maxsize)
{
if(aData.getName() == key)
{
}
if (!items[parent].empty)
{
//out << items[parent].instanceData <<setw(22) << parent;
//out << endl;
}
//this->displayPreOrder(out, 2 * parent + 1);
//this->displayPreOrder(out, 2 * parent + 2);
}
return false;
}
Here is data.cpp
#include "data.h"
#include <iostream>
#include <iomanip>
using namespace std;
data::data(char const * const name) : name(new char[strlen(name)+1])
{
if (name)
{
strcpy(this->name , name);
}
else this->name = NULL;
}
// destructor
data::~data()
{
delete [] name ;
}
// assignment operator overload
data& data::operator=(const data& data2)
{
if ( this == &data2)
{
return *this;
}
delete [] name;
name = NULL;
name = new char[strlen(data2.name)+1]; // allocate new space
strcpy(name , data2.name); //copy
return *this;
}
char const * const data::getName() const
{
return this->name;
}
void data::setName (char const * const name)
{
strcpy(this->name, name);
}
// return true if d1 is "less than" d2, false otherwise
bool operator< (const data& d1, const data& d2)
{
return strcmp(d1.getName(), d2.getName()) < 0;
}
// return true if d1 is "equal to" d2, false otherwise
bool operator== (const data& d1, const data& d2)
{
return false;
}
// print the data instance referred to by outData
ostream& operator<< (ostream& out, const data& outData)
{
out << outData.name;
//out << endl;
return out;
}