Двоичный поиск для TListView

Delphi , Компоненты и Классы , TListView

Оформил: DeeCo
Автор: http://www.swissdelphicenter.ch

{+------------------------------------------------------------ 
| Function ListviewBinarySearch 
| 
| Parameters : 
| listview: listview to search, assumed to be sorted, must 
| be <> nil. 
| Item : item caption to search for, cannot be empty 
| index : returns the index of the found item, or the 
| index where the item should be inserted if it is not 
| already in the list. 
| Returns : True if there is an item with the passed caption 
| in the list, false otherwise. 
| Description: 
| Uses a binary search and assumes that the listview is sorted 
| ascending on the caption of the listitems. The search is 
| case-sensitive, like the default alpha-sort routine used by 
| the TListview class. 
| Note: 
| We use the lstrcmp function for string comparison since it 
| is the function used by the default alpha sort routine. If 
| the listview is sorted by another means (e.g. OnCompare event) 
| this needs to be changed, the comparison method used must 
| always be the same one used to sort the listview, or the 
| search will not work! 
| Error Conditions: none 
| Created: 31.10.99 by P. Below 
+------------------------------------------------------------}

 function ListviewBinarySearch(listview: TListview; const Item: string;
   var Index: Integer): Boolean;
 var
   First, last, pivot, res: Integer;
 begin
   Assert(Assigned(listview));
   Assert(Length(item) > 0);

   Result := False;
   Index  := 0;
   if listview.Items.Count = 0 then Exit;

   First := 0;
   last  := listview.Items.Count - 1;
   repeat
     pivot := (First + last) div 2;
     res   := lstrcmp(PChar(item), PChar(listview.Items[pivot].Caption));
     if res = 0 then
     begin
       { Found the item, return its index and exit. }
       Index  := pivot;
       Result := True;
       Break;
     end { If }
     else if res > 0 then
     begin
       { Item is larger than item at pivot }
       First := pivot + 1;
     end { If }
     else
     begin
       { Item is smaller than item at pivot }
       last := pivot - 1;
     end;
   until last < First;
   Index := First;
 end; { ListviewBinarySearch }

Перевод контента на русский язык:

Функция поиска для компонента TListView в Delphi. Функция принимает три параметра:

• listview: компонент TListView, который должен быть отсортирован и не равен nil.
• Item: заголовок элемента, который нужно найти, и он не может быть пустым.
• Index: целочисленный индекс, возвращаемый индексом найденного элемента или индексом, на котором элемент должен быть вставлен, если он уже есть в списке.

Функция использует алгоритм двоичного поиска для поиска элемента в списке. Она предполагает, что список отсортирован в порядке возрастания заголовков элементов и поиск чувствителен к регистру.

Распределение кода:

1. Первые несколько строк проверяют ошибки:
   • Assert(Assigned(listview)): проверяет, не равно ли nil компонент listview.
   • Assert(Length(item) > 0): проверяет, не пустой ли заголовок элемента.
2. Инициализируются переменные результата и индекса:
   • Result := False; устанавливает начальный результат в false (не найден).
   • Index := 0; устанавливает начальный индекс в 0.
3. Если компонент listview не имеет элементов, функция выходит из цикла:
   • if listview.Items.Count = 0 then Exit;
4. Инициализируются переменные поиска:
   • First := 0; устанавливает начальный индекс в 0.
   • Last := listview.Items.Count - 1; устанавливает конечный индекс в последний элемент списка.
5. Выполняется двоичный поиск:
   • Функция повторно вычисляет середину диапазона поиска (pivot := (First + Last) div 2) и сравнивает ее с целевым элементом с помощью lstrcmp.
   • Если результат сравнения равен 0, элемент найден, поэтому устанавливается Index в pivot, Result в true и функция выходит из цикла.
   • Если результат сравнения больше 0, элемент на pivot больше целевого элемента, поэтому диапазон поиска перемещается вниз (First := pivot + 1).
   • Если результат сравнения меньше 0, элемент на pivot меньше целевого элемента, поэтому диапазон поиска перемещается вверх (Last := pivot - 1).
6. Когда цикл выходит (т.е. список был просмотрен и не найдено совпадения), устанавливается Index в начальный индекс диапазона поиска (First).

Обратите внимание, что этот код использует функцию lstrcmp для сравнения строк, которая чувствительна к регистру и предполагает тот же метод сортировки, который используется по умолчанию в TListView. Если список отсортирован с помощью другого метода, необходимо изменить метод сравнения соответственно.

В целом, это хорошо структурированная реализация двоичного поиска, которая должна работать эффективно для поиска элементов в отсортированном списке TListView.

Статья описывает функцию ListviewBinarySearch, которая выполняет двоичный поиск в отсортированном TListView и возвращает индекс найденного элемента или место, где он должен быть вставлен.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: TListView ::