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

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

Изучая код листинга 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.

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

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

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

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

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

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

function TtdSingleLinkList.SortedFind(aItem : pointer;

aCompare : TtdCompareFunc) : boolean;

var

BLCursor : PslNode;

BLCursorIx : longint;

WorkCursor : PslNode;

WorkParent : PslNode;

WorkCursorIx : longint;

ListCount : longint;

MidPoint : longint;

i : integer;

CompareResult :integer;

begin

{подготовительные операции}

BLCursor := FHead;

BLCursorIx := -1;

ListCount := Count;

{пока в списке имеются узлы...}

while (ListCount <> 0) do begin

{вычислить положение средней точки; оно будет не менее 1}

MidPoint := (ListCount + 1) div 2;

{переместиться вперед до средней точки}

WorkCursor := BLCursor;

WorkCursorIx := BLCursorIx;

for i := 1 to MidPoint do begin

WorkParent := WorkCursor;

WorkCursor := WorkCursor^.slnNext;

inc(WorkCursorIx);

end;

{сравнить значение узла с искомым значением}

CompareResult := aCompare(WorkCursor^.slnData, aItem);

{если значение узла меньше искомого, уменьшить размер списка и повторить цикл}

if (CompareResult < 0) then begin

dec(ListCount, MidPoint);

BLCursor := WorkCursor;

BLCursorIx := WorkCursorIx;

end

{если значение узла больше искомого, уменьшить размер списка и повторить цикл}

else if (CompareResult > 0) then begin

ListCount := MidPoint - 1;

end

{в противном случае искомое значение найдено; установить реальный курсор на найденный узел}

else begin

FCursor := WorkCursor;

FParent := WorkParent;

FCursorIx := WorkCursorIx;

Result := true;

Exit;

end;

end;

Result := false;

end;

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Списки

Из книги автора

Списки Списки дают возможность расположить большое количество пунктов компактно. При создании списков вы сами можете определить количество видимых элементов. Можно настроить возможность выбора одного или нескольких пунктов. По функциям списки напоминают


Списки

Из книги автора

Списки Рассмотрим все возможности задания спискам различного визуального форматирования.Кстати, если вы с помощью display: marker укажете маркер вместе с элементом списка, созданным с помощью свойств списка, то маркер просто-напросто заменит стандартный элемент списка.


Списки

Из книги автора

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


Списки

Из книги автора

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


15.5.6. Списки ACL

Из книги автора

15.5.6. Списки ACL ACL (Access Control Lists) — списки контроля доступа. Довольно часто возникает потребность группировки однотипных параметров в единое целое для их последующей обработки. Для эффективного решения этой задачи используются списки контроля доступом (ACL). Например: acl SSL_ports


18.6. Списки ACL

Из книги автора

18.6. Списки ACL ACL (Access Control Lists) — списки контроля доступа. Довольно часто возникает необходимость группировки однотипных параметров в единое целое для их последующей обработки. Для эффективного решения этой задачи используются списки ACL. Например:acl SSL_ports port 443 563Эта запись


23.2.4. Списки

Из книги автора

23.2.4. Списки Библиотека Glib содержит средства для работы с одно- и двусвязными списками. Особенность двусвязного списка заключается в том, что по нему можно перемещаться в обоих направлениях — назад и вперед. В файле gslist.h (Glib Single List) описаны средства для работы с


Списки

Из книги автора

Списки Когда в тексте нужно что-то перечислить, это принято делать с помощью списков. Пока читаете книгу, обратили внимание, сколько в ней есть списков? Я их создавала в Word с помощью специальных инструментов. Сейчас расскажу вам о них.Остаемся в группе Абзац на вкладке


Нумерованные списки

Из книги автора

Нумерованные списки При создании нумерованных списков можно использовать самые разные типы нумерации. Список кнопки Нумерация (рис. 4.36) и одноименная команда контекстного меню (см. рис. 4.31) позволяют выбрать один из семи наиболее часто используемых типов нумерации. Кроме


Многоуровневые списки

Из книги автора

Многоуровневые списки Microsoft Word позволяет создавать также многоуровневые списки, содержащие до девяти уровней различных списков. При этом каждый уровень может иметь собственный маркер или номер.Кнопка Многоуровневый список, которая находится в группе Абзац вкладки


Глава 3. Связные списки, стеки и очереди

Из книги автора

Глава 3. Связные списки, стеки и очереди Как и массивы, связные списки представляют собой универсальную структуру данных, широко используемую многими программистами. Однако, в отличие от массивов, связные списки не входят в состав стандартного языка Object Pascal. Тем не менее,


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

Из книги автора

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


5.1.8. Списки

Из книги автора

5.1.8. Списки Текстовый процессор Pages, как и MS Word, предлагает создавать списки следующих видов:? Маркированные. В качестве маркера могут быть использованы символы, готовые картинки, входящие в библиотеку, картинки пользователя;? Нумерованные. Перечень вариантов для


Списки

Из книги автора

Списки Чтобы акцентировать внимание на отдельных абзацах, их можно пронумеровать, создав так называемый нумерованный список. Другой способ выделения абзацев состоит в отметке их маркерами (маркированный список). Например, последовательность выполнения практических


Дельта-списки и косвенные дельта-списки САС

Из книги автора

Дельта-списки и косвенные дельта-списки САС Назначение дельта-списка - информировать об изменениях в САС, произошедших с момента его выпуска или с некоторого заданного момента времени, другими словами, о приращении САС (как известно, приращение обозначается символом ,