1

私には2つの機能があります。関数 Find は 2 セクション検索を実行します。つまり、キーが見つかるまでセクションごとに配列を検索し、その場所を返します。関数 removef または (remove fast) はその場所を取得し、文字列配列から削除します。ユーザーにコマンドと文字列 (文字列は削除されます) を入力するように求めるコマンド ライン インターフェイスを使用しているため、ユーザーに文字列の入力を求める必要はありません。

ここに私の検索機能があります

int StringList::Find(string key, int start, int end)
{
    int middle = (end + start)/2;
    if (key > str[middle])
    {
        return Find(key,middle,end);
    }
    else if ( key < str[middle])
    {
        return Find(key,start,middle);
    }
    else if (key == str[middle])
    {
        return middle;
    }
}

Find 関数は、キーが配列の上部セクションまたは下部セクション (中央の上または中央の下) にあるかどうかを判断し、削除する必要があるキーまたは文字列が見つかるまで分割を続けることになっています。

removef は次のとおりです。

void StringList::removef(string s)
{
    int loc = Find(s,0,10000); //ignore these parameters, i know they are wrong they are just an example


        for(int j=loc; j<(numberOfStrings)-1; j++)
        {
            str[j] = str[j+1];
        }
        numberOfStrings--;

}

私の問題は、二分検索を使用した検索機能にあります。私が修正できる何か提案はありますか？私は本当に立ち往生しています。ありがとう！

4

2 に答える 2

2

私が見ることができる1つの問題は、キーが中間要素よりも大きい場合、新しい範囲を に設定していることですが、[midde,end]そうであるべきです[middle+1,end]-中間要素を再度検討しても意味がありません.

したがって、最初の条件は次のようになります。

if (key > str[middle])
{
    return Find(key,middle+1,end);
}

また、他の人が述べたように、文字列が配列にないかどうかを確認する必要があります。メソッドの最初にこのようなものを追加することをお勧めしますFind。

if (start == end) return -1;

開始点が終了点に等しくなるまで配列を細分化すると、検索するスペースがなくなり、文字列が見つからなくなります。

それ以外に、間違っていると思われる唯一のことはFind、間違った範囲でメソッドを呼び出していることです。次のように呼び出す必要があります。

int loc = Find(s,0,numberOfStrings);
于 2013-07-01T20:51:16.587 に答える
1

まず、文字列 'str' 配列を既にソートしていると仮定しています...そうしないと、バイナリ検索は機能しません。

「Find」関数では、文字列配列であると想定している「str」配列にアクセスしますが、この配列をパラメーターとして渡しません。そのため、アクセスしようとしているグローバル配列でない限り、機能しません。

最後に、この関数を再帰的に呼び出しているため、配列にまったく含まれていない文字列を処理するケースが必要です。

于 2013-07-01T20:03:28.953 に答える