rechercher un arbre de recherche binaire

Question

J'essaie de trouver un nom dans une clé. Je pense qu'il récupère bien. Cependant, son coming up comme non trouvé. peut-être que mon code est faux 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; 

} 

si ce bit de code à l'intérieur main() est où il dit pas trouvé quand je l'encre 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 devriez utiliser le BST pour naviguer dans l'arbre - ne pas boucler 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 comparer quel que soit le type de items[index].instanceData et char*.

Je vous suggère de mettre un peu de journalisation dans l'opérateur et voir si elle est effectivement appelée - je suppose que ce n'est pas le cas.

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 à tout. Il me semble que c'est juste une liste simple - vous faites une recherche linéaire au sein de retrieve au lieu de comparer la clé et d'aller à gauche ou à droite dans l'arbre (ou retourner "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 mal:

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 également que votre fonction renvoie true ou un booléen non défini. Vous devriez probablement avoir un return false; à la fin de BST :: retrieve.