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

После изучения стеков и очередей, основанных на связных списках и массивах, вы, наверное, задали себе вопрос: "Какой тип лучше использовать?" Тесты на контроль времени в различных версиях Delphi (16- и 32-разрядных) показали, что в большинстве случаев быстрее оказывается версия, основанная на массиве. Ее и лучше использовать. Исключением является случай, когда в Delphi1 количество элементов в стеке или очереди превышает 16000 - это максимальное значение для Delphi1. Поэтому, если в вашем стеке или очереди будет больше 16000 элементов, в Delphi1 потребуется работать со связными списками.

Глава 4. Поиск.

Поиск - это действие, заключающееся в просмотре набора элементов и выделении из этого набора интересующего элемента. Наверное, все вы знакомы с одной из функций поиска - Pos из модуля SysUtils, которая предназначена для поиска подстроки в строке.

Эта и следующая главы, посвященные поиску, довольно-таки тесно связаны между собой. Часто поиск элемента приходится осуществлять в уже отсортированном контейнере. И если контейнер отсортирован, можно воспользоваться эффективным алгоритмом для поиска позиции вставки нового элемента, чтобы и после вставки контейнер оказался отсортированным. Тем не менее, поиск не ограничивается просмотром отсортированных списков. Мы, помимо прочих, рассмотрим простейший тип поиска - алгоритмы, которые кажутся почти очевидными и не заслуживают специального названия.

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

Процедуры сравнения

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

Очевидно, что если элементы принадлежат к целочисленному типу, операция сравнения не представляет никаких трудностей: все мы можем взять два целых числа и определить, отличаются они или нет. В случае строк сравнение усложняется. Можно выполнять сравнение, чувствительное к регистру (т.е. строчные символы будут отличаться от прописных), и сравнение, нечувствительное к регистру (т.е. строчные символы не будут отличаться от прописных), сравнение по локальным таблицам символов (сравнение на основе алгоритмов, специфических для определенной страны или языка) и т.д. Тип set в Delphi, несмотря на то, что он позволяет сравнивать два набора, все же не имеет четко определенного способа определения того, что один набор больше другого (фактически выражение "один набор больше другого" не имеет смысла, если речь не идет о количестве элементов). А что касается объектов, то здесь даже нет метода, который бы позволил сказать, что объект A равен или не равен объекту B (за исключением сравнения указателей на объекты).

Лучше всего на данном этапе рассматривать процедуру сравнения в виде "черного ящика" - функции с четко определенным интерфейсом или синтаксисом, которая в качестве входного параметра принимает два элемента и возвращает результат сравнения - первый элемент меньше второго, первый элемент равен второму или первый элемент больше второго. Для тех типов элементов, которые не имеют определенного порядка (т.е. даже если известно, что два элемента не равны, мы не можем определить, меньше элемент A элемента B или больше), нужно предусмотреть, чтобы функция сравнения возвращала значение, которое трактуется как "не равно".

В книге все функции сравнения принадлежат к типу TtdCompareFunc (этот тип объявлен в файле TDBasics.pas, который можно найти на Web-сайте издательства, в разделе материалов; там же находятся и примеры функций сравнения):

Листинг 4.1. Прототип функции TtdCompareFunc

type

TtdCompareFunc = function(aData1, aData2 : pointer) : integer;

Другими словами, функция сравнения в качестве входных параметров принимает два указателя и возвращает целочисленное значение. Возвращаемое значение будет равно 0, если два сравниваемых элемента равны, меньше нуля, если первый элемент меньше второго, и больше нуля, если первый элемент больше второго. Тип параметров aData1 и aData2 определяет сама функция, и она же решает, что делать с переданными данными: привести к определенному классу или просто к типу, который не является указателем.

Приведем пример функции сравнения, которая предполагает, что входные параметры принадлежат к типу longint, а не представляют собой указатели. (Будем считать, что значение sizeof(longint) равно sizeof(pointer). На сегодняшний день это справедливо для всех версий Delphi.)

Листинг 4.2. Функция TDCompareLongint

function TDCompareLongint(aData1, aData2 : pointer) : integer;

var

L1 : longint absolute aData1;

L2 : longint absolute aData2;

begin

if (L1 < L2) then

Result := -1

else if (L1 = L2) then

Result := 0

else

Result := 1

end;

Перед тем как в ужасе сказать, что вы бы никогда не вызвали такую функцию сравнения двух значений типа longint, обратите внимание, что этого и не требуется. Приведенная функция предназначена для использования структурами данных, которые принимают элементы в виде указателей (например, список TtdSingleLinkList или стандартный массив TList), и подпрограммами, которые используют такие структуры данных. Если вы разрабатываете функцию поиска, исходя из главных принципов, имеет смысл написать и процедуру сравнения. Остается надеяться, что все мы сможем написать функцию для сравнения двух целых чисел.

Давайте рассмотрим пример функции TDCompareNullStr, предназначенной для сравнения двух строк, завершающихся нулем, не привязываясь к алфавиту определенной страны:

Листинг 4.3. Функция TDCompareNullStr

function TDCompareNullStr(aData1, aData2 : pointer) : integer;

begin

Result := StrComp(PAnsiChar(aData1), PAnsiChar(aData2));

end;

(В Delphi1 в модуле TDBasics объявлено, что тип PAnsiChar соответствует типу PChar.) К счастью, для данного примера стандартная функция StrComp возвращает значение того же типа, что и требуется для нашей функции сравнения.

В качестве последнего примера приведем функцию TDCompareNullStrAnsi, предназначенную для сравнения двух строк, завершающихся нулем, с учетом локальных таблиц символов:

Листинг 4.4. Функция TDCompareNullStrAnsi

function TDCompareNullStrAnsi(aData1, aData2 : pointer) : integer;

begin

{$IFDEF Delphi1}

Result := lstrcmp(PAnsiChar(aData1), PAnsiChar(aData2));

{$ENDIF}

{$IFDEF Delphi2Plus}

Result := CompareString(LOCALE_USER_DEFAULT, 0,

PAnsiChar(aData1), -1,

PAnsiChar(aData2), -1) - 2;

{$ENDIF}

{$IFDEF Kylix1Plus}

Result := strcoll(PAnsiChar(aData1), PAnsiChar(aData2));

{$ENDIF}

end;

В приведенной функции для Delphi1 и 32-разрядных версий Delphi используются разные коды. Кроме того, обратите внимание, что функция lstrcmp возвращает значения в том виде, который нужен нам. К сожалению, функция CompareString этого не делает. Она возвращает 1, если первая строка меньше второй, 2, если строки равны, и 3, если первая строка больше второй. Поэтому для получения требуемого значения необходимо просто вычесть 2 из результата, возвращаемого функцией CompareString. В Kylix для сравнения строк нужно воспользоваться функцией strcoll из модуля Libc.

Последовательный поиск

Теперь, когда мы определились с функцией сравнения, можно перейти к рассмотрению алгоритмов поиска элемента в массивах и связных списках.

Массивы

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

Если массив не отсортирован, для поиска определенного элемента может использоваться только один единственный алгоритм: выбирать каждый элемент массива и сравнивать его с искомым. Как правило, такой алгоритм реализуется с помощью цикла For. В качестве примера давайте выполним поиск значения 42 в массиве из 100 целых чисел: