la ricerca di un albero binario di ricerca

Question

Sto cercando di trovare un nome all'interno di una chiave. Penso che sta recuperando esso bene. tuttavia, il suo arrivo come non trovato. forse il mio codice è da qualche parte che non va?

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

funzione di recuperare ...

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
        }


    }

}


 }

e definito data.cpp

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

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

}

in modo da questo pezzo di codice all'interno main () è dove si dice non trovato quando penso che dovrebbe funzionare correttamente. sia il nome e ADATA contengono il nome giusto che è stata trovata ..

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

Si dovrebbe essere utilizzando il BST per navigare attraverso l'albero - non ciclare su ogni elemento dell'array, come altri hanno detto. Provare qualcosa di simile:

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)

Che dovrebbe funzionare bene! :)

Answer 2

Non sono un esperto di C ++, ma è il tuo operatore == in realtà in corso di valutazione? E 'lo scopo di prendere due riferimenti ai dati const, ma sembra essere il confronto qualunque sia il tipo di items[index].instanceData è e un char*.

Vi suggerisco di mettere un po 'la registrazione dei gestori e vedere se è effettivamente chiamato -. Ho il sospetto che non è

Una possibilità di prendere l'operatore == fuori dall'equazione temporanea sarebbe quello di fare il confronto esplicito:

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

In un altro punto, non riesco a vedere come questo è in realtà facendo una ricerca binaria a tutti. Sembra a me come se fosse solo un elenco semplice -. Si sta facendo una ricerca lineare entro retrieve invece di confrontare la chiave e andare a sinistra oa destra verso il basso l'albero (o di ritorno "trovato") a seconda del risultato

Answer 3

Non posso dire per certo senza vedere il codice per BST, ma questo sembra sbagliato:

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

Con le convenzioni tradizionali, dovrebbe essere:

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

Accanto a questo, a quanto pare anche la vostra funzione sia restituisce true o qualche booleano indefinito. Probabilmente si dovrebbe avere un return false; alla fine del BST :: recuperare.