Фундаментальные алгоритмы и структуры данных в 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 целых чисел:

var

MyArray : array[0..99] of integer;

Inx : integer;

begin

for Inx := 0 to 99 do

if MyArray[Inx] = 42 then

Break;

if (Inx = 100) then

.. значение 42 не было найдено ..

else

.. значение 42 было найдено в элементе с индексом Inx ..

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

Интересно, сколько читателей в приведенном выше коде нашли ошибку? Проблема заключается в том, что в языке Object Pascal при успешном завершении цикла значение переменной цикла будет не определено. С другой стороны, в случае преждевременного завершения цикла, скажем, с помощью оператора Break, значение переменной цикла будет определено.