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

Давайте рассмотрим пример функции 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, значение переменной цикла будет определено.

В коде предполагается, что перемененная цикла Inx после завершения цикла будет на 1 больше конечного значения для цикла For, даже если цикл будет выполнен успешно. Оказывается, что в 32-разрядных компиляторах (в версиях Delphi от 2 до 7) ошибки не возникает: значение переменной цикла после завершения цикла будет на 1 больше, чем при последнем выполнении цикла. В Delphi 1 код будет работать неправильно: после завершения выполнения цикла переменная цикла будет содержать значение, равное своему значению при последнем выполнении цикла (в нашем примере Inx после полного выполнения цикла будет содержать 99). Кто знает, что будет в следующих версиях Delphi? Вполне возможно, что в будущих версиях Delphi будет изменен оптимизатор компилятора, и переменная цикла после завершения цикла будет получать другое значение. В конце концов, разработчики, описав поведение переменной цикла, оставили за собой право изменения ее значения после выхода из цикла.

Тогда каким образом можно реализовать алгоритм последовательного поиска? Цикл For можно использовать (это самый быстрый метод организации последовательного поиска), однако потребуется ввести флаг, который будет указывать, найден ли искомый элемент. Код несколько усложнится, но зато становится корректным с точки зрения языка программирования: