search a Binary search tree
I am trying to find a name within a key. I think it is retrieving it fine. however, its coming up as not found. maybe my code is wrong somewhere?
if (database.retrieve(name, aData)) // both contain the match
in main()
static void retrieveItem(char *name, data& aData)
{
cout << ">>> retrieve " << name << endl << endl;
if (database.retrieve(name, aData)) // name and aData both contain the match
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);
retrieve function...
bool BST::retrieve(const char *key, data &aData, int parent) const
{
for(int index=0; index < maxsize+1; index++)
{
if (!items[index].empty)
{
if ( items[index].instanceData == key )
{
aData.setName(key);
return true; // doesn't return right away
}
}
}
}
and defined in data.cpp
bool operator== (const data& d1, const data& d2)
{
return strcmp(d1.getName(), d2.getName()) == 0;
}
开发者_JS百科so this bit of code inside main() is where it says not found when i think it should be working correctly. both name and aData contain the right name that was found..
static void retrieveItem(char *name, data& aData)
{
cout << ">>> retrieve " << name << endl << endl;
if (database.retrieve(name, aData)) // name and aData both contain the match
cout << aData << endl;
else
cout << "not found\n";
cout << endl;
}
You should be using the BST to navigate through the tree - not looping over each item in your array, like others have said. Try something like:
bool retrieve(key, aData)
retrieve(key, aData, parent)
if (key == aData)
return true
else
return false
bool retrieve(key, aData, parent)
if (key == items[parent].name)
aData.setName(key)
else if (key < items[parent].name)
retrieve(key, aData, 2*parent+1)
else
retrieve(key, aData, 2*parent+2)
That should work well! :)
I'm no C++ expert, but is your == operator actually being evaluated? It's meant to take two const data references, but you appear to be comparing whatever the type of items[index].instanceData
is and a char*
.
I suggest you put some logging into the operator and see if it's actually being called - I suspect it's not.
One option to take the == operator out of the equation temporarily would be to make the comparison explicit:
if (strcmp(items[index].instanceData.getName(), key) == 0)
{
...
}
On another point, I can't see how this is actually doing a binary search at all. It looks to me like it's just a plain list - you're doing a linear search within retrieve
instead of comparing the key and going left or right down the tree (or returning "found") depending on the result.
I can't tell for sure without seeing the code for BST, but this looks wrong:
for(int index=0; index < maxsize+1; index++)
With the traditional conventions, it should be:
for(int index=0; index < maxsize; index++)
Beside that, it also seems your function either returns true or some undefined boolean. You should probably have a return false;
at the end of BST::retrieve.
精彩评论