поиск в бинарном дереве поиска - PullRequest
Новая
       17

поиск в бинарном дереве поиска

0 голосов
/ 05 декабря 2009

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

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;

}

так что этот фрагмент кода внутри main () говорит, что он не найден, когда я думаю, что он должен работать правильно. и name, и 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;
     }

Ответы [ 3 ]

1 голос
/ 06 декабря 2009

Вы должны использовать 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)

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

0 голосов
/ 05 декабря 2009

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

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

С традиционными соглашениями должно быть: 

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

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

0 голосов
/ 05 декабря 2009

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

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

Одним из вариантов временного исключения оператора == из уравнения будет явное сравнение: 

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

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

...