2

要件は、指定された文字列 (以下の例では "yz") のバイナリ検索メソッドを使用して、アルファベット順/並べ替えられた (文字列型の) リストを検索し、結果 (指定された文字列で始まるすべての文字列とリスト内のその文字列のインデックスも) ListBox のような適切なコントロールに。

問題は、BinarySearch メソッドが 1 つだけではなく、リスト内の一致するすべての文字列を返すようにループを何度も実行する必要があることです。これが私の主な問題です。このループを正しく記述する方法がわかりません。while ループの中を見ると、見つかった結果をリストから削除しようとしていることがわかります。これにより、リスト内の項目のインデックスが変更されるという問題が発生します。そのため、結果に対して間違ったインデックスが返されます。たとえば、次のコードを実行すると、9、10、11、および 12 のインデックスが返されます。ただし、アイテムが削除されるとリストが短くなるため、9、10、9、10 が返されます。結果の文字列を完全に削除するのではなく、別のランダムな文字列に置き換えることができます。しかし、それはリストがアルファベット順にソートされなくなったことを意味します。BinarySearch メソッドを機能させるには、リストをアルファベット順に並べ替える必要があります。

BinarySearch メソッドはおそらく問題なく、変更する必要はありません。問題はループにあります。これは大学での課題であるため、ショートカット コードや組み込み関数は使用できません。私は何時間も試しましたが、これを理解できません。

public partial class MainWindow : Window
{
    public MainWindow()
    {
        InitializeComponent();
    }

    string searchString = "yz";

    List<string> list1 = new List<string>();

    private void btnSearch_Click(object sender, RoutedEventArgs e)
    {
        if (list1.Count != 0)
        {
            list1.Clear();
        }

        list1.Add("ant");   //0
        list1.Add("bb");    //1
        list1.Add("bc");    //2 
        list1.Add("bD");    //3
        list1.Add("Be");    //4
        list1.Add("j");     //5
        list1.Add("RRR");   //6
        list1.Add("sT");    //7
        list1.Add("Uv");    //8      
        list1.Add("yz");    //9
        list1.Add("yza");   //10
        list1.Add("yzb");   //11
        list1.Add("yzc");   //12

        int index = BinarySearch(list1, 0, list1.Count, searchString);

        while (index != list1.Count)
        {
            listBox1.Items.Add("Index: " + index + " File: " + list1[index]);

            list1.RemoveAt(index); //Remove from list so we don't find it again
                                   // but this changes the index of the list

            index = BinarySearch(list1, 0, list1.Count, searchString);
        }
    }

    //BinarySearch method to search an alphabetically sorted list for a specified string
    public int BinarySearch(List<string> strList, int first, int last, string target)
    {
        int mid;    // index of the midpoint
        string midStr;  // object that is assigned listStr[mid]
        int origLast = last;
        // save original value of last
        while (first < last)
        // test for nonempty sublist
        {
            mid = (first + last) / 2;
            midStr = strList[mid];

            int indy = midStr.IndexOf(target, StringComparison.OrdinalIgnoreCase);

            if (indy == 0)
                return mid;// have a match, we're only matching the beginning of the string
            else
            {
                int order = string.Compare(target, midStr, StringComparison.OrdinalIgnoreCase);

                if (order < 0)
                    last = mid; // search lower sublist. Reset last                    
                else
                    first = mid + 1; // search upper sublist. Reset first
            }
        }
        return origLast; // target not found
    }
}
4

1 に答える 1

1

要素の1つのインデックスを取得したら、最後のオブジェクトまたは文字列から開始しないオブジェクトに到達するまでインデックスからループアップし、インデックス-1から0に到達するまでループします。または、無効なオブジェクトに到達します。

編集: コードを変更するには、次のことを行います。

int index = BinarySearch(list1,0,list1.Count,searchString);

オブジェクトを削除する while ループを実行する代わりに、次のようにします。

for (int n=index;n<list1.Count;n++) {
    if (list1[n].IndexOf(searchString,StringComparison.OrdinalIgnoreCase)!=0) break;
    listBox1.Items.Add("Index: " + n + " File: " + list1[n]);
}
for (int n=index-1;n>=0;n--) {
    //Do same thing as other loop
}

これは、リスト内の両方の方法を検索し、無効な文字列に到達するまでアクションを実行するだけで、ループが中断されます。

于 2013-03-18T08:00:57.260 に答える