バイナリ検索ツリーを検索

StackOverflow https://stackoverflow.com/questions/1853082

  •  13-09-2019
  •  | 
  •  

質問

私は、キー内の名前を見つけようとしています。私はそれがうまくそれを取得していると思います。ただし、そのが見つからないとして上がってきます。多分私のコードはどこか間違っているのですか？

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;
     }
役に立ちましたか？

解決

あなたはツリーをナビゲートするために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)

これはうまく動作するはずです！ ：）

他のヒント

私はC ++専門家だが、あなたの==演算子は、実際に評価されていますか？ 2つのconstのデータ参照を取るためのもの、しかし、あなたはitems[index].instanceDataのタイプがあると何でも比較されるように見えるだchar*ます。

私はあなたがオペレータにいくつかのログを入れて、それが実際に呼び出されていますかどうかを確認示唆 - 。私はそれがありません疑う

方程式のうち、==演算子を取るための一つのオプションを一時的に比較を明示的にするために、次のようになります。

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

他の点では、私はこれは実際にすべてのバイナリ検索をやっているかを確認することはできません。それは単なるリストだように私には見えます - あなたの代わりにキーを比較し、左または右のツリーの下に行くのretrieve内線形検索をやっている（または「見つかった」戻る）結果に応じて、

。

私はBSTのコードを見ることなく確実に伝えることができないが、これは間違っているになります。

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

伝統的な慣習で、それはする必要があります：

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

そのほかに、それはまた、あなたの関数を思わtrueまたはいくつかの未定義のブール値を返します。あなたはおそらく、BSTの終わり::検索でreturn false;を持っている必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top