В связных списках последовательный поиск выполняется точно так же, как и в массивах. Тем не менее, элементы проходятся не по индексу, а по указателю Next. Для класса TtdSingleLinkList, описанного в главе 3, можно разработать две следующих функции: первая - для выполнения поиска по несортированному связному списку, и вторая - по отсортированному. Функции просто указывают, найден ли искомый элемент. В случае, если элемент найден, список будет установлен в позицию искомого элемента. В функции для отсортированного списка курсор будет установлен в позицию, где должен находиться искомый элемент, чтобы список оставался отсортированным.

Листинг 4.8. Последовательный поиск в однонаправленном связном списке

function TDSLLSearch(aList : TtdSingleLinkList;
altem : pointer;
aCompare : TtdCompareFunc) : boolean;
begin with aList do begin MoveBeforeFirst;
MoveNext;
while not IsAf t er Last do begin
if (aCompare (Examine, altem) = 0) then begin
Result := true;
Exit;
end;
MoveNext;
end;
end;
Result := false;
end;
function TDSLLSortedSearch(aList : TtdSingleLinkList;
altem : pointer;
aCompare : TtdCompareFunc) : boolean;
var
CompareResult : integers-begin with aList do begin MoveBeforeFirst;
MoveNext;
while not isAf terLast do begin CompareResult := aCompare(Examine, altem);
if (CompareResult >= 0) then begin
Result := (CompareResult = 0);
Exits-end;
MoveNext;
end;
end;
Result := false;
end;

Соответствующие функции для класса TtdDoubleLinkList будут точно такими же.

Бинарный поиск

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

Алгоритм бинарного поиска применим только для отсортированных контейнеров.

Массивы3

Предположим, что у нас имеется отсортированный массив. Как было показано ранее, алгоритм последовательного поиска даже при использовании выхода из цикла в случае отсутствия в списке искомого элемента принадлежит к классу О(и). Каким образом можно улучшить быстродействие?

Ответом может служить бинарный поиск. Он основан на стратегии "разделяй и властвуй": начинаем с большой проблемы, разбиваем ее на маленькие проблемы, которые легче решить, а, затем, следовательно, решаем всю большую проблему.

Бинарный поиск работает следующим образом. Берем средний элемент массива. Равен ли он искомому элементу? Если да, то поиск успешно завершен. В противном случае, если искомый элемент меньше среднего, то можно сказать, что, если элемент присутствует в массиве, он находится в первой половине. С другой стороны, если искомый элемент больше среднего, он должен находиться во второй половине. Таким образом, одним сравнением мы разбили нашу проблему на две части. Теперь мы применяем тот же алгоритм к выбранной части массива: находим средний элемент и определяем, в какой половине (точнее уже в четвертой части) находится искомый элемент. Мы снова делим проблему на две части. Описанные операции продолжаются до тех пор, пока искомый элемент не будет найден (разумеется, если он присутствует в массиве).

Это и есть алгоритм бинарного поиска. Поскольку размер массива при каждом выполнении цикла уменьшается в два раза, быстродействие алгоритма будет выражаться как 0(log(w)), т.е. скорость работы алгоритма примерно пропорциональна функции двоичного логарифма log2 от количества элементов в массиве (таким образом, возведение количества элементов массива во вторую степень приведет к увеличению времени поиска только в два раза).

Ниже приведен пример выполнения бинарного поиска в массиве TList (функцию можно найти в файле TDTList.pas на Web-сайте издательства, в разделе сопровождающих материалов).

Листинг 4.9. Бинарный поиск в отсортированном массиве TList

function TDTListSortedlndexOf (aList : TList;
altem : pointer;
aCompare : TtdCompareFunc) : integer;
var
L, R, M : integer;
CompareResult : integers-begin
{задать значения для индексов первого и последнего элементов) L := 0;
R : - pred(aList.Count); while (L <= R) do begin
{вычислить индекс среднего элемента) M := (L + R) div2;
{сравнить значение среднего элемента с искомым значением) CompareResult : = aCompare(aList.ListA [M], altem);
{если значение среднего элемента меньше искомого значения, переместить левый индекс на позицию до среднего индекса) if (CompareResult < 0) then L := suce (M)
{если значение среднего элемента больше искомого значения, переместить правый индекс на позицию после среднего индекса) else if (CompareResult > 0) then
R : = pred (M) {в противном случае искомый элемент найден) else begin
Result := M;
Exits-end;
end;
Result := -1;
end;

Для описания подмассива, рассматриваемого в текущий момент, используются две переменных - L и R, которые хранят, соответственно, левый и правый индексы. Первоначально значения этих переменных устанавливаются равными 0 (первый элемент массива) и Count-1 (последний элемент массива). Затем мы входим в цикл While, из которого выйдем после обнаружения в массиве искомого элемента или когда значение переменной L превысит значение переменной R, что означает, что искомый элемент в массиве отсутствует. При каждом выполнении цикла вы-

Бинарный поиск в массиве числяется индекс среднего элемента (фактически это среднее значение между Ь и И)

Рисунок 4.1. Бинарный поиск в массиве числяется индекс среднего элемента (фактически это среднее значение между Ь и И). Затем значение элемента со средним индексом сравнивается с искомым значением. Если значение среднего элемента меньше, чем искомое, мы переносим левый индекс на позицию после среднего. В противном случае мы переносим правый индекс на позицию перед средним. Таким образом, мы определяем новый подмасеив для поиска. Если же значение среднего элемента равно искомому, поиск завершен.

Для примера на рис. 4.1 приведены шаги, выполняемые при бинарном поиске буквы й в отсортированном массиве, содержащем буквы от а до к. На шаге (а) переменная Ь указывает на первый элемент (индекс 0), а И - на последний (индекс 10). Это означает, что значение переменной М будет составлять 5. Далее мы выполняем сравнение: значение элемента с индексом 5 равно /, а это больше искомого значения а1.

Согласно алгоритму, мы устанавливаем значение я равным М-1 (таким образом, правая граница подмассива теперь находится слева от среднего элемента). Это означает, что значение Я теперь равно 4. Новое значение среднего индекса будет равно 2, как показано на шаге (Ь). Выполняем сравнение: буква с (значение элемента с индексом 2) меньше, чем а1.

Теперь, в соответствии с алгоритмом, необходимо установить индекс Ь за индексом м (т.е. М+1 или 3). Новое значение переменной м на шаге (с) равно 3. Выполняем сравнение: элемент с индексом 3 содержит букву а это и есть наше искомое значение. Поиск завершен.

Связные списки

Изучая код листинга 4.9, можно придти к выводу, что маловероятно, чтобы бинарный поиск использовался для связных списков, если, конечно, не воспользоваться индексным доступом к элементам списка, который, как уже упоминалось в главе 3, приводит к снижению быстродействия.

Но, тем не менее, реализация бинарного поиска для связных списков оказывается не такой уж и неразрешимой проблемой. Во-первых, нужно понимать, что в общем случае переход по ссылке выполняется гораздо быстрее, нежели вызов функции сравнения. Следовательно, можно сказать, что переход по ссылке - это "хорошо", а вызов функции сравнения - "плохо". Это означает, что следует стремиться к минимизации вызовов функции сравнения. (Поскольку для нас функция сравнения - "черный ящик", мы не можем сказать, сколько времени требуется на ее выполнение: много или мало, по крайней мере, по сравнению со временем, требуемым на переход по ссылке.) Во-вторых, необходимо иметь доступ к "внутренностям" связного списка.

Давайте рассмотрим принцип организации бинарного поиска на примере обобщенного связного списка, а затем рассмотрим код для классов TtdSingleLinkList и TtdDoubleLinkList. Для нашего обобщенного связного списка должно быть известно количество содержащихся в нем элементов, поскольку оно понадобится при реализации алгоритма бинарного поиска. Кроме того, будем считать, что связный список содержит фиктивный начальный узел.

А теперь сам алгоритм.

1. Сохранить фиктивный начальный узел в переменной BeforeCount.

2. Сохранить количество элементов в списке в переменной ListCount.

3. Если значение ListCount равно нулю, искомого элемента нет в списке, и поиск завершается. В противном случае вычислить половину значения ListCount, при необходимости округлить его и сохранить в переменной MidPoint.

4. Переместить BeforeCount по ссылкам Next на MidPoint узлов.

5. Сравнить значение элемента в узле, где остановилась переменная BeforeCount, с искомым значением. Если значения равны, искомый элемент найден и поиск завершается.

6. Если значение в узле меньше, чем искомое, записать узел в переменную BeforeCount, вычесть значение MidPoint из значения ListCount и перейти к шагу 3.

7. Если значение в узле больше, чем искомое, записать значение MidPoint-1 в переменную ListCount и перейти к шагу 3.

Давайте рассмотрим работу этого алгоритма на примере. Предположим, что имеется следующий связный список из пяти узлов, в котором необходимо найти узел В:

Начальный узел ->A->B->C-h>D->E->nil

На первом шаге переменной BeforeList присваивается значение начального узла, а на втором переменной ListCount присваивается значение 5. Делим ListCount на два, округляем до целого, и присваиваем полученное значение (3) переменной MidPoint (шаг 3). По ссылкам от узла BeforeList отсчитываем три узла: А, В, С (шаг 4). Сравниваем текущий узел с искомым (шаг 5). Его значение больше искомого В, следовательно, устанавливаем значение переменной ListCount равным 2 (шаг 7). Еще раз выполняем цикл. Делим ListCount на два, округляем до целого и получаем 1 (шаг 3). По ссылкам от узла BeforeList отсчитываем один узел: А (шаг 4). Сравниваем значение текущего узла с искомым значением (шаг 5). Оно меньше значения В, следовательно, записываем в BeforeList значение узла В, а переменной ListCount присваиваем значение 1 (шаг 6) и снова выполняем цикл. В этот раз MidPoint получит значение 1 (т.е. значение ListCount, деленное на два и округленное до целого). Переходим по ссылке от узла BeforeList на один шаг и находим искомый узел.

Если вы считаете, что в процессе выполнения алгоритма искомый узел был пройден несколько раз, то вы совершенно правы. Но следует иметь в виду, что вызов функции сравнения может быть намного медленнее, чем переход по ссылкам (например, если элементы списка представляют собой строки длиной 1000 символов, то для определения соотношения между строками функции сравнения придется сравнить в среднем 500 символов). Если бы связный список содержал целые числа, а мы отказались бы от частого использования функции сравнения, то быстрее всех оказался бы алгоритм последовательного поиска.

Ниже приведена функция бинарного поиска для класса TtdSingleLinkList.

Листинг 4.10. Бинарный поиск в отсортированном однонаправленном связном списке

function TtdSingleLinkList .SortedFind(altem : pointer;
aCompare : TtdCompareFunc) : boolean;
var
BLCursor : PslNode;
BLCursorlx : longint;
WorkCursor : PslNode;
WorkParent : PslNode;
WorkCursorIx : longint;
ListCount : longint;
MidPoint : longint;
i : integer;
CompareResult : integers-begin
{подготовительные операции}
BLCursor := FHead;
BLCursorlx :=-l;
ListCount := Count;
{пока в списке имеются узлы..}
while (ListCount о 0) do begin
{вычислить положение средней точки; оно будет не менее 1}
MidPoint := (ListCount + 1) div 2;
{переместиться вперед до средней точки}
WorkCursor := BLCursor;
WorkCursorlx := BLCursorlx;
for i : = 1 to MidPoint do begin WorkParent := WorkCursor;
WorkCursor : = WorkCursorA.slnNext;
inc(WorkCursorlx);
end;

{сравнить значение узла с искомым значением] CompareResult := aCompare(WorkCursor*.slnData, altem); { если значение узла меньше искомого, уменьшить размер списка и повторить цикл]

if (CompareResult < 0) then begin
dec(ListCount, MidPoint);
BLCursor := WorkCursor;
BLCursorlx := WorkCursorlx;
end
{если значение узла больше искомого, уменьшить размер списка и повторить цикл}
else if (CompareResult > 0) then begin
ListCount := MidPoint - 1; end
{в противном случае искомое значение найдено; установить реальный курсор на найденный узел} else begin
FCursor := WorkCursor;
FParent := WorkParent;
FCursorlx := WorkCursorIx;
Result := true;
Exits-end;
end;
Result := false;
end;

Функция бинарного поиска для класса TtdDoubleLinkList аналогична приведенной функции.

Массивы3 || Оглавление || Вставка элемента в отсортированный контейнер


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс