Suche ein binärer Suchbaum
-
13-09-2019 - |
Frage
Ich versuche, einen Namen innerhalb eines Schlüssels zu finden. Ich denke, es ist es in Ordnung abruft. jedoch seine kommen als nicht gefunden. vielleicht mein Code ist falsch irgendwo?
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);
abrufen Funktion ...
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
}
}
}
}
und definiert in data.cpp
bool operator== (const data& d1, const data& d2)
{
return strcmp(d1.getName(), d2.getName()) == 0;
}
so dieses Stück Code in main (), wo sagt sie nicht gefunden, wenn ich denke, es sollte richtig funktionieren. beide Namen und ADATA enthalten den richtigen Namen, der gefunden wurde ..
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;
}
Lösung
Sie sollten sein, die BST mit durch den Baum zu navigieren - nicht über jedes Element im Array Looping, wie andere gesagt haben. Versuchen Sie so etwas wie:
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)
Das sollte gut funktionieren! :)
Andere Tipps
Ich bin kein C ++ Experte, aber Ihr Operator == ausgewertet eigentlich werden? Es sollte zwei const Datenreferenzen nehmen, aber Sie scheinen zu vergleichen, was die Art der items[index].instanceData
ist und ein char*
.
Ich schlage vor, Sie einige Protokollierung in den Bediener und sehen, ob es tatsächlich ist aufgerufen wird. - Ich vermute, es ist nicht
Eine Möglichkeit den Operator == aus der Gleichung zu nehmen vorübergehend den Vergleich explizit zu machen wäre:
if (strcmp(items[index].instanceData.getName(), key) == 0)
{
...
}
Ein weiterer Punkt, kann ich nicht sehen, wie das eigentlich überhaupt eine binäre Suche zu tun. Es scheint mir, wie es nur eine einfache Liste ist -. Sie innerhalb retrieve
eine lineare Suche tun, anstatt den Schlüssel zu vergleichen und nach links zu gehen oder auf dem ganzen Baum (oder „gefunden“ Rückkehr) in Abhängigkeit vom Ergebnis
Ich kann nicht sicher sagen, ohne den Code für BST zu sehen, aber das sieht falsch:
for(int index=0; index < maxsize+1; index++)
Mit den traditionellen Konventionen, sollte es sein:
for(int index=0; index < maxsize; index++)
Daneben scheint es auch Ihre Funktion liefert entweder wahr oder etwas undefiniert boolean. Sie sollten wahrscheinlich eine return false;
am Ende des BST haben :: abgerufen werden.