поиск двоичного дерева поиска

Question

Я пытаюсь найти имя внутри ключа. Я думаю, что это хорошо. однако его приближение не найдено. может быть, мой код что-то не так?

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

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

извлечения функции ...

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 
     } 


    } 

} 


} 

и определены в data.cpp

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

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

} 

так что этот бит кода внутри главной() где он говорит, что не найден, когда я чернила должны работать правильно. как имя и ADATA содержат правильное имя, которое было найдено ..

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

Вы должны использовать BST для навигации по дереву, а не для каждого элемента в вашем массиве, как говорили другие. Попробуйте что-то вроде:

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) 

Это должно хорошо работать! :)

Answer 2

Я не эксперт C++, но ваш оператор == фактически оценивается? Он предназначен для использования двух ссылок на константу данных, но вы, кажется, сравниваете любые типы items[index].instanceData и char*.

Я предлагаю вам ввести некоторые данные в оператор и посмотреть, действительно ли это вызвано - я подозреваю, что это не так.

Один из вариантов, чтобы взять оператор == из уравнения временно было бы сделать сравнение недопонимание:

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

На другой точке, я не могу понять, как это на самом деле делает бинарный поиск в все. Мне кажется, что это простой список - вы выполняете линейный поиск в пределах retrieve вместо сравнения ключа и перехода влево или вправо вниз по дереву (или возвращающемуся «найденному») в зависимости от результата.

Answer 3

Я не могу точно сказать, не видя код BST, но это выглядит не так:

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

С традиционных условностей, она должна быть:

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

Кроме того, это также кажется, что ваша функция возвращает true или некоторое неопределенное логическое значение. Вероятно, у вас должно быть return false; в конце BST :: retrieve.