Лабы / 3
.docxЗадание:
|
2. |
Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования хеш-адреса использовать хеш-функцию универсального хеширования и процедуру линейного исследования для разрешения коллизии.
|
Код:
var
Form4: TForm4;
a:array[0..50] of integer;
b:array[0..50] of integer;
m,c1,c2,r,k,p,g:integer;
implementation
{$R *.dfm}
procedure TForm4.Button1Click(Sender: TObject);
function h(k,i:integer):integer; //коллизия
var
vs:integer;
begin
vs:=k mod m;
h:=(vs+c1*i+c2*i*i)mod m;
end;
function delenie(k,m:integer):integer;
begin
delenie:=k mod m;
end;
procedure hesh_insert(var t:array of integer;k:integer); //вставка ключа в ячейку массива
var
j,i:integer;
begin
i:=0;
repeat
j:=h(k,i); //функция квадратичн
if t[j]<>-1 then //если не пустая
i:=i+1 //то идет дальше
else begin //иначе
t[j]:=k; //вставляем в эту ячейку массива ключ,ячейку полученную квадратичным исследованием
exit //вставляет и выходит, больше не нужно по квадратичной
end;
until t[j]=k;
end;
begin
g:=memo1.lines.count;
m:=strtoint(edit1.text); //k - ключ m - размер таблицы,
c1:=strtoint(edit2.text); //k mod m получаем номер ячейки (j)
c2:=strtoint(edit3.text);
for r:=0 to m-1 do
b[r]:=-1;
for r:=0 to g-1 do begin
k:=strtoint(memo1.lines[r]);
p:=delenie(k,m); //индекс массива хеш функцией деления получаем
if b[p]=-1 then //если пусто, то вносим ключ
b[p]:=k
else
if b[p]<>-1 then //если занято, то коллизия
hesh_insert(b,k);
end;
for r:=0 to m-1 do
memo2.lines.add(inttostr(b[r]));
end;
end.
Результат:
Блок схема:
Ввод
m,c1,c2,k Начало
b[r]:=-1; ii:=0
to m-1 ii:=0
to g-1 k:=strtoint(memo1.lines[r]); p:=delenie(k,m); b[p]=-1 b[p]:=k b[p]<>-1
ir:=0
to m-1 end
Вывод
b[r]
-
+
hesh_insert(b,k);
+
function
h(k,i:integer):integer;
vs:=k
mod m; h:=(vs+c1*i+c2*i*i)mod
m;
end
function delenie(k,m:integer):integer;
delenie:=k
mod m;
end
i:=0; p:=delenie(k,m); t[j]<>-1 i:=i+1
t[j]:=k; t[j]=k; end
procedure
hesh_insert(var t:array of integer;k:integer);