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

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

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

var

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

Inx : integer;

FoundIt : boolean;

begin

FoundIt := false;

for Inx := 0 to 99 do

if MyArray[Inx] = 42 then begin

FoundIt := true;

Break;

end;

if not FoundIt then

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

else

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

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

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

function TDTListIndexOf(aList : TList; aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

Inx : integer;

begin

for Inx := 0 to pred(aList.Count) do

if (aCompare(aList.List^[Inx], aItem) = 0) then begin

Result := Inx;

Exit;

end;

{если мы попали сюда, значит искомый элемент не найден}

Result := -1;

end;

Эта функция работает не так как метод TList.IndexOf, который предназначен для поиска элемента в массиве путем сравнения значений указателей. Фактически он в своем внутреннем списке указателей осуществляет поиск элемента как указателя. С другой стороны, функция TDTListIndexOf осуществляет поиск самого элемента, вызывая для сравнения искомого и текущего элемента функцию сравнения. Функция сравнения может сравнивать просто значения указателей или преобразовывать указатели во что-нибудь более значимое, например, в класс или запись, а затем сравнивать поля.

Обратите внимание, что в реализации функции с целью повышения эффективности применяется небольшая хитрость. Вместо сравнения aItem с aList[Inx] выполняется сравнение с aList.List^[Inx]. Зачем? Компилятор преобразовывает первое сравнение в вызов функции, а затем вызываемая функция, TList.Get, перед возвратом указателя из внутреннего массива указателей проверяет переданный ей индекс на предмет попадания в диапазон от 0 до количества элементов (вызывая исключение, если условие не соблюдается). Но мы знаем, что индекс находится в требуемом диапазоне, поскольку используется цикл от 0 до количества элементов минус 1. Поэтому нам не нужно считывать значение свойства Items и вызывать метод TList.Get. Можно получить доступ непосредственно к массиву указателей (свойство List экземпляра TList).

-----

Эта хитрость (использование свойства List экземпляра TList) вполне корректна. Если вы уверены, что значения индекса не выходят за пределы допустимого диапазона, можно исключить проверку на предмет попадания в диапазон за счет непосредственного доступа к массиву ListItems. Тем не менее, ее применение при итерации по массиву TList или в коде, который может привести к выходу индекса за пределы допустимого диапазона, не желательно. Лучше обезопасить себя, нежели потом сожалеть.

-----

В классе TtdRecordList (который описан в главе 2) для организации последовательного поиска можно пользоваться методом IndexOf (см. листинг 4.6).

Листинг 4.6. Последовательный поиск с помощью метода TtdRecordList.IndexOf

function TtdRecordList.IndexOf(aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

ElementPtr : PAnsiChar;

i : integer;

begin

ElementPtr := FArray;

for i := 0 to pred(Count) do begin

if (aCompare(aItem, ElementPtr) = 0) then begin

Result := i;

Exit;

end;

inc(ElementPtr, FElementSize);

end;

Result := -1;

end;