Хеш-функция по сумме кодов символов по модулю m

Алгоритм:

а) хеш-функцию приравниваем остатку от деления на m суммы кодов трех символов, которые являются ее параметрами

function h1(c1,c2,c3:char):integer;

begin

h1:=(ord(c1)+ord(c2)+ord(c3)) mod m;

end;

Заключение

Цель лабораторной работы была выполнена. Приобрёл навыки в использовании хеш-таблиц для поиска данных, а также применение метода линейного хеширования для разрешения коллизий. Была разработана программа в среде Turbo Pascal, в соответствии с заданием. В программе были выполнены основные операции с хешированием данных:

1) функция поиска данных из таблицы

2) Была описана хеш-функция по сумме кодов символов по модулю m

3) Процедура считывания таблицы из файла

4) Был описан линейный метод хеш-функции

Список использованной литературы

Литературные источники:

1) А. Л. Марченко - Структуры и алгоритмы обработки данных

2) Лойко В.И. - Структуры и алгоритмы обработки данных

3) Валиуллова Н.А. - Структуры и алгоритмы обработки данных

4) Матьяш В.А. - Структуры и алгоритмы обработки данных

Web источники:

1) http://cendomzn.ucoz.ru/index/0-7623

2) http://webpnz.narod.ru/student/saod/lections/

3) http://0361.org/news/posts/С%20и%20АОД/

4) http://www.lections.hut2.ru/AiSD.html

5) http://www.lections.hut2.ru/AiSD.html

6) http://bsuir-helper.ru/predmet/siaod

Приложение А

(обязательное)

Листинг программы

type person = record

Name:string;

Number:longint;

end;

const c=1;

const m=10;

const max=1000;

var collisions,h,numb,n,i,j:longint;

s:string;

t:array[0..max] of integer;

persons:array[1..1000] of person;

f:textfile;

//хеш-функция по сумме кодов

function h1(c1,c2,c3:char):integer;

begin

h1:=(ord(c1)+ord(c2)+ord(c3)) mod m;

end;

// линейный метод для первой хешфункции

procedure linear1();

var i,j,a:integer;

str:string;

begin

collisions:=0;

for i:=1 to n do

begin

str:=persons[i].name;

j:=0;

while (true) do

begin

a:=h1(str[1],str[2],str[3])+j*c;

if t[a]=0 then

begin

t[a]:=i;

break;

end

else

begin

j:=j+1;

inc(collisions);

end;

end;

end;

end;

procedure poisk();

var i:integer;

begin

writeln('Введите фамилию (exit - выход): ');

readln(s);

if s='exit' then exit;

j:=0;

h:=h1(s[1],s[2],s[3])+j*c;

if t[h]=0 then writeln('такого нет')

else

while (j<max) do

begin

h:=h1(s[1],s[2],s[3])+j*c;

if ((persons[t[h]].name[1]=s[1]) and (persons[t[h]].name[2]=s[2]) and (persons[t[h]].name[3]=s[3])) then

begin

writeln(persons[t[h]].name, ' ', persons[t[h]].number);

end;

j:=j+1;

end;

end;

procedure showTable();

var i:integer;

begin

for i:=1 to max do

begin

if t[i]<>0 then writeln(i, ' ', persons[t[i]].name, ' ', persons[t[i]].number);

end;

end;

procedure loadTable();

begin

assign(f, 'для хэша.txt');

reset(f);

n:=1;

while (not eof(f)) do

begin

readln(f, s);

readln(f, numb);

readln(f);

persons[n].Name:=s;

persons[n].Number:=numb;

inc(n);

end;

dec(n);

end;

var ch:char;

begin

while (true) do

begin

writeln(‘ЧТО СДЕЛАТЬ?’)

writeln(' ');Writeln;

writeln('Загрузить информацию из файла - 0');

writeln(' ');Writeln;

writeln('Посмотреть хеш-таблицу - 1');

writeln(' ');Writeln;

writeln('Поиск - 2');

writeln(' ');Writeln;

writeln('Удаление таблицы - 3');

writeln(' ');Writeln;

writeln('Выход - 4');

writeln(' ');Writeln;

readln(ch);

if ch='0' then

begin

loadTable();

linear1();

end;

if ch='1' then showtable();

if ch='2' then poisk();

if ch='3' then for i:=0 to max do t[i]:=0;

if ch='4' then exit;

end;

end.

Приложение B

(обязательное)

Блок – схемы основных операций по хешированию данных

Не нашли, что искали? Воспользуйтесь поиском: