procurar uma árvore de busca binária
-
13-09-2019 - |
Pergunta
Eu estou tentando encontrar um nome dentro de uma chave. Eu acho que é recuperá-lo bem. no entanto, a sua vinda como não foi encontrado. talvez o meu código está em algum lugar errado?
if (database.retrieve(name, aData)) // both contain the match
em 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);
recuperar função ...
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 definida em data.cpp
bool operator== (const data& d1, const data& d2)
{
return strcmp(d1.getName(), d2.getName()) == 0;
}
então este pedaço de código dentro de main () é onde ele diz que não encontrou quando eu acho que deveria estar funcionando corretamente. o nome e ADATA conter o nome certo de que foi encontrado ..
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;
}
Solução
Você deve estar usando a BST para navegar através da árvore - não looping sobre cada item em sua matriz, como outros já disseram. Tente algo como:
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)
Isso deve funcionar bem! :)
Outras dicas
Não sou especialista C ++, mas é o seu operador == realmente está sendo avaliado? Era para levar duas referências de dados const, mas você parece estar comparando qualquer que seja o tipo de items[index].instanceData
é e uma char*
.
Eu sugiro que você coloque um pouco de logging para o operador e ver se ele está realmente sendo chamado -. Eu suspeito que não é
Uma opção para tirar o operador == fora da equação temporariamente seria fazer a comparação explícita:
if (strcmp(items[index].instanceData.getName(), key) == 0)
{
...
}
Em outro ponto, não posso ver como isso está realmente fazendo uma pesquisa binária em tudo. Parece-me como se fosse apenas uma lista simples -. Você está fazendo uma pesquisa linear dentro retrieve
em vez de comparar a chave e indo para a esquerda ou para a direita para baixo da árvore (ou retornando "encontrado"), dependendo do resultado
Eu não posso dizer com certeza sem ver o código para BST, mas isso parece errado:
for(int index=0; index < maxsize+1; index++)
Com as convenções tradicionais, que deve ser:
for(int index=0; index < maxsize; index++)
Além disso, ele também parece que sua função seja retorna verdadeiro ou algum boolean indefinido. Você provavelmente deve ter um return false;
no final do BST :: recuperar.