البحث في شجرة البحث الثنائية

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;

}

لذلك هذا القليل من التعليمات البرمجية داخل الرئيسي () هو المكان الذي تقول فيه غير موجود عندما أعتقد أنه يجب أن يعمل بشكل صحيح. اسم كلا اسم وأديناتا يحتوي على الاسم الصحيح الذي وجد ..

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

بجانب ذلك، يبدو أن وظيفتك إما إما إما أن تعرض صحيحة أو منطقية غير محددة. ربما يجب أن يكون لديك return false; في نهاية BST :: استرداد.