procedure BinarySearch(var T:tTable; k:tKey; var index:integer);
var l,c,r: integer;
begin
index:=0;
l:=1; r:=T.n;
while (index=0)and(l<=r) do begin
c:=(l+r) div 2;
if T.a[c].key=k then index:=c
else if T.a[c].key>k then r:=c-1
else l:=c+1;
end;
end;
Переменные l, r и c обозначают соответственно номер левого края, центра и правого края части массива, в которой мы ищем элемент с заданным ключом. Поиск прекращается либо если элемент найден (index <> 0), либо если часть массива, в которой нужно искать, была исчерпана (то есть номер левого края превысил номер правого). Внутри цикла находим номер середины части массива (c), затем сравниваем ключ этого среднего элемента с искомым ключом. Если выполнилось равенство, то элемент найден, если средний больше искомого, то устанавливаем правую границу части массива равной c-1, если больше — меняем левую границу на c+1.
3. Линейный поиск в списке
Пусть теперь данные таблицы содержатся в списке. В этом случае можно использовать для поиска алгоритм, очень похожий на алгоритм линейного поиска в массиве. Отличие лишь в том, что изменение номера текущего элемента заменяется переходом к указателю на следующий элемент списка:
procedure SearchInList(T: tTable; k: tKey; var p: tItemPtr);
var notfound: boolean;
begin
notfound:=true;
p:=T;
while (p<>nil) and (notfound) do begin
if p^.key=k then notfound:=false;
p:=p^.next;
end;
end;
Параметр T в этом случае не нужно делать параметром-переменной, поскольку он является только указателем на начало таблицы, а сама таблица лежит в динамической памяти. Вместо номера найденного элемента будем возвращать пользователю нашей процедуры указатель на него (если поиск был удачным) или nil, если поиск неудачен.
Сокращать число проверок в цикле с помощью барьера было бы неразумно: каждый раз барьер придётся ставить в «хвост» списка, а для этого нужно сначала обойти весь список, начиная с головы, затрачивая при этом много времени.
Лекция 19. Перемешанные таблицы
Наиболее очевидным способом хранения таблицы является массив, в котором несколько первых элементов представляют собой полезные данные, а остальные элементы считаются пустыми. Ниже будет рассмотрен другой вариант применения массива для реализации таблицы.
Позволим данным располагаться в любых элементах массива, а не только в первых n. Чтобы отличать пустые элементы от занятых нам понадобится специальное значение ключа, которое мы будем заносить в ключевое поле всех пустых ячеек. Если ключ — число, а все полезные ключи положительны, то можно в качестве ключа пустой ячейки использовать 0, если ключи — строки, содержащие фамилии, то ключом пустой ячейки можно сделать пустую строку и т. п. Пусть в ключами являются строки, тогда для таблицы потребуются такие объявления:
const empty = '';
nmax = 1000;
type tKey = string;
tData = .....;
tItem = record
key: tKey;
data: tData;
end;
tTable = array[0..nmax-1] of tItem;
Перед тем как помещать данные в массив заполним ключевые поля всех его элементов «пустыми» значениями. Заносить в таблицу будем не все данные сразу, а один за другим, по очереди. Для того, чтобы определить номер ячейки массива, в которую нужно поместить добавляемый элемент данных, напишем функцию, значение которой зависит только от ключа добавляемого элемента. В такой ситуации поиск можно будет осуществлять довольно просто: находим значение функции на искомом ключе, и смотрим на элемент массива с полученным номером. Если ключ элемента равен искомому ключу, мы нашли то, что искали, иначе — поиск оказался неудачным.
Реализованная описанным способом таблица называется перемешанной (или hash-таблицей), а функция — функцией расстановки ключей (hash-функцией). Такие названия связаны с тем, что данные беспорядочно разбросаны по массиву.
Теперь покажем, как всё сказанное воплотить в программу на Паскале. В качестве ключей в наших примерах используются строки, поэтому можно предложить такой вариант хэш-функции: сложить коды всех символов строки, и, чтобы полученное число не выходило за максимально возможный индекс массива, возьмём остаток от деления на размер массива:
function hash(key: tKey): integer;
var i: integer;
begin
sum:=0;
for i:=1 to length(key) do sum:=sum+ord(key[i]);
hash := sum mod nmax;
end;
Процедура добавления элемента в таблицу в предварительном варианте будет выглядеть так:
procedure AddItem(var t: tTable; item: tItem);
var h: integer;
begin
h:=hash(item.key);
t[h]:=item.key;
end;
У написанной процедуры есть один существенный недостаток: если элемент, номер которого указала нам хэш-функция был занят, то новые данные будут записаны на место старых, а старые бесследно исчезнут. Чтобы решить эту проблему будем пытаться найти какой-либо другой свободный элемент для добавляемых данных. Здесь понадобится ещё одна функция (вторичная хэш-функция), которая по номеру занятого элемента и по значению ключа добавляемых данных укажет номер другой ячейки, если и там будет занято, вызовем вторичную функцию ещё раз, и т. д. до тех пор пока свободная ячейка не найдется.
Наиболее простая хэш-функция будет добавлять к номеру занятой ячейки какое-нибудь постоянное число:
const HC = 7;
function hash2(n: integer, key: tKey): integer;
begin
hash2 := (n + HC) mod nmax;
end;
Остаток от деления на nmax понадобилось вычислять по той же причине, что и в первичной хэш-функции.
Сейчас можно написать окончательный вариант процедуры добавления элемента данных в таблицу:
procedure AddItem(var t: tTable; item: tItem);
var h: integer;
begin
h:=hash(item.key);
while t[h].key<>empty do h:=hash2(h,item.key);
t[h].key:=item.key;
t[h].data:=item.data;
end;
Пусть в хэш-таблицу занесены все необходимые данные и требуется отыскать данные с некоторым ключом. Для этого будем действовать по такой схеме: вычисляем значение хэш-функции на данном ключе, если ячейка с полученным номером свободна, то элемент не найден, если занята, то сравниваем её ключ с искомым. В случае совпадения мы нашли нужный элемент, иначе — находим значение вторичной функции и смотрим на ключ в ячейке с полученным номером. Если он равен «пустому» значению, то поиск неудачен, если равен искомому ключу — то удачен, иначе — вновь находим значение вторичной хэш функции и т. д. На Паскале всё это выглядит так:
const notfound = -1;
continue = -2;
procedure Search(var t: tTable; key: tKey; var index: integer);
var h: integer;
begin
h:=hash(key);
index:=continue;
repeat
if t[h].key = key then index:=h
else if t[h].key = empty then index:= notfound
else h:=hash2(h,key);
until index<>сontinue;
end;
Процедура выдаёт ответ о результатах поиска через параметр-переменную index. При удачном поиске там будет лежать номер найденного элемента, при неудачном — константа notfound. Константа continue означает «пока не найден» и используется только внутри процедуры. При поиске сначала вычисляется значение первичной хэш-функции, а в index заносится значение continue Затем выполняется проверка на равенство ключей, если оно выполняется, то ячейка массива найдена, и мы записываем её номер в index, иначе, если ячейка пуста, то элемент не найден (в index записываем notfound), в третьем случае находим значение вторичной функции. Эти действия продолжаются до тех пор, пока index не перестанет быть равным continue.