la recherche d'un arbre de recherche binaire

Question

Je suis en train de trouver un nom au sein d'une clé. Je pense qu'il est bien la récupérer. Cependant, son entrée comme non trouvé. peut-être que mon code est mal quelque part?

if (database.retrieve(name, aData))  // both contain the match

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

récupérer la fonction ...

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
        }


    }

}


 }

et défini dans data.cpp

bool operator== (const data& d1, const data& d2)
{

return strcmp(d1.getName(), d2.getName()) == 0;

}

ce bit de code à l'intérieur principal () est l'endroit où il dit ne se trouve pas quand je pense qu'il devrait fonctionner correctement. le nom et aData contiennent le bon nom qui a été trouvé ..

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

Vous devez utiliser la BST pour naviguer dans l'arbre - pas en boucle sur chaque élément de votre tableau, comme d'autres l'ont dit. Essayez quelque chose comme:

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)

Cela devrait bien fonctionner! :)

Answer 2

Je ne suis pas expert C ++, mais est votre opérateur == en fait en cours d'évaluation? Il est destiné à prendre deux références de données const, mais vous semblez être comparer quel que soit le type de items[index].instanceData est et char*.

Je vous suggère de mettre un peu d'exploitation forestière dans l'opérateur et voir si elle est en fait appelé -. Je soupçonne que ce n'est pas

Une option de prendre l'opérateur == de l'équation serait temporairement est de faire la comparaison explicite:

 if (strcmp(items[index].instanceData.getName(), key) == 0)
 {
     ...
 }

Sur un autre point, je ne vois pas comment cela est en train de faire une recherche binaire du tout. Il me semble que c'est juste une simple liste -. Que vous faites une recherche linéaire dans retrieve au lieu de comparer la clé et aller à gauche ou à droite vers le bas l'arbre (ou retour « trouvé ») en fonction du résultat

Answer 3

Je ne peux pas dire à coup sûr sans voir le code pour BST, mais cela semble erroné:

for(int index=0; index < maxsize+1; index++)

Avec les conventions traditionnelles, il devrait être:

for(int index=0; index < maxsize; index++)

A côté de cela, il semble aussi votre fonction soit renvoie true ou une valeur booléenne non définie. Vous devriez probablement avoir un return false; à la fin de BST :: récupérer.