Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритмы

Список значений хеш-функции

Пусть хеш-функция принимает значения 1..k. Для каждого значения хеш-функции рассмотрим список всех элементов множества с данным значением хеш-функции. Будем хранить эти k списков с помощью переменных
Содержание: array [1..n] of T;
 Следующий: array [1..n] of 1..n;
 ПервСвоб: 1..n;
 Вершина: array [1..k] of 1..n;
Задача. Напишите соответствующие программы. Решение. Перед началом работы надо положить Вершина[i]=0 для всех i=1..k, и связать все места в список свободного пространства, положив ПервСвоб=1 и Следующий[i]=i+1 для i=1..n-1, а также Следующий[n]=0.
function принадлежит (t: T): boolean;
 | var i: integer;
 begin
 | | i := Вершина[h(t)];
 | i := Вершина[h(t)];
 | {осталось искать в списке, начиная с i}
 | while (i <> 0) and (Содержание[i] <> t) do begin
 | | i := Следующий[i];
 | end; {(i=0) or (Содержание [i] = t)}
 | belong := Содержание[i]=t;
 end;

 procedure добавить (t: T);
 | var i: integer;
 begin
 | if not принадлежит(t) then begin
 | | i := ПервСвоб;
 | | {ПервСвоб <> 0 - считаем, что не переполняется}
 | | ПервСвоб := Следующий[ПервСвоб]
 | | Содержание[i]:=t;
 | | Следующий[i]:=Вершина[h(t)];
 | | Вершина[h(t)]:=i;
 | end;
 end;

 procedure исключить (t: T);
 | var i, pred: integer;
 begin
 | i := Вершина[h(t)]; pred := 0;
 | {осталось искать в списке, начиная с i; pred -
 | предыдущий. если он есть, и 0, если нет}
 | while (i <> 0) and (Содержание[i] <> t) do begin
 | | pred := i; i := Следующий[i]; 
 | end; {(i=0) or (Содержание [i] = t)}
 | if Содержание[i]=t then begin
 | | {элемент есть, надо удалить}
 | | if pred = 0 then begin
 | | | {элемент оказался первым в списке}
 | | | Вершина[h(t)] := Следующий[i];
 | | end else begin
 | | | Следующий[pred] := Следующий[i]
 | | end;
 | | {осталось вернуть i в список свободных}
 | | Следующий[i] := ПервСвоб;
 | | ПервСвоб:=i;
 | end;
 end;
 Похожие публикации: Алгоритмы

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]