Книга: Фундаментальные алгоритмы и структуры данных в Delphi
Связные списки
Связные списки
В связных списках последовательный поиск выполняется точно так же, как и в массивах. Тем не менее, элементы проходятся не по индексу, а по указателю Next. Для класса TtdSingleLinkList, описанного в главе 3, можно разработать две следующих функции: первая - для выполнения поиска по несортированному связному списку, и вторая - по отсортированному. Функции просто указывают, найден ли искомый элемент. В случае, если элемент найден, список будет установлен в позицию искомого элемента. В функции для отсортированного списка курсор будет установлен в позицию, где должен находиться искомый элемент, чтобы список оставался отсортированным.
Листинг 4.8. Последовательный поиск в однонаправленном связном списке
function TDSLLSearch(aList : TtdSingleLinkList;
aItem : pointer;
aCompare : TtdCompareFunc) : boolean;
begin
with aList do begin
MoveBeforeFirst;
MoveNext;
while not IsAfterLast do begin
if (aCompare(Examine, aItem) = 0) then begin
Result := true;
Exit;
end;
MoveNext;
end;
end;
Result := false;
end;
function TDSLLSortedSearch(aList : TtdSingleLinkList;
aItem : pointer;
aCompare : TtdCompareFunc) : boolean;
var
CompareResult : integer;
begin
with aList do begin
MoveBeforeFirst;
MoveNext;
while not IsAfterLast do begin
CompareResult := aCompare(Examine, aItem);
if (CompareResult >= 0) then begin
Result := (CompareResult = 0);
Exit;
end;
MoveNext;
end;
end;
Result := false;
end;
Соответствующие функции для класса TtdDoubleLinkList будут точно такими же.
Оглавление книги
