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

Поиск - это действие, заключающееся в просмотре набора элементов и выделении из этого набора интересующего элемента. Наверное, все вы знакомы с одной из функций поиска - 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.)