Suche ein binärer Suchbaum

Question

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

Answer 1

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! :)

Answer 2

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

Answer 3

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.