Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Основные операции с хешированием данных




Формулировка задания

Используя метод хеширования с открытой адресацией, написать программу поиска записи по первых трем буквам фамилии.

Указания : в качестве хэш-функции использовать :

- сумму кодов символов по модулю m

В качестве метода адресации использовать:

- линейный метод.

Основные операции с хешированием данных

1) Линейный метод хеш–функции

Алгоритм:

- Обнуляем число коллизий;

- Для i от 1 до n;

а) Строке str присваиваем фамилию i-го человека;

б) Присваиваем число шагов для хеш-функции 0 (j:=0);

в) Переменной а присваиваем значение хеш-функции от первых трех букв фамилии + количество шагов хеш-функции умноженную на константу С;

г) Если в ячейке с номером а свободно, пишем туда значение i, выходим из цикла;

д) Иначе, увеличиваем шаг и число коллизий на единицу;

 

collisions:=0;{ обнуляем число коллизий}

for i:=1 to n do{ Для i от 1 до n}

begin

str:=persons[i].name;{ присваиваем фамилию i-го человека}

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;{ пишем значение i}

break;{выходим из цикла}

end

else

begin

j:=j+1;

inc(collisions);{ увеличиваем шаг и число коллизий на единицу}

end;

end;

end;

end;

 

 

 

Функция поиска

Алгоритм:

а) Количество шагов хеш-функции приравниваем 0;

б) присваиваем h значение хеш - функции от первых трех букв фамилии + количество шагов хеш-фукнции умноженную на константу С;

в) если в ячейке таблицы с номером h ничего нет, то такого человека в базе нет;

г) Иначе, пока не найдем;

д) присваиваем h значение хеш-функции от первых трех букв фамилии + количество шагов хеш-фукнции умноженную на константу C;

е) Если первые три буквы фамилии человека, чей номер записан в ячейке таблицы с номером h, совпадают с первыми тремя буквами введенной фамилии, выводим его фамилию и номер телефона;

ж) Увеличиваем количество шагов;

j:=0;{ количество шагов хеш-функции приравниваем 0}

h:=h1(s[1],s[2],s[3])+j*c;{ присваиваем h значение хеш - функции от первых трех букв фамилии + количество шагов хеш-фукнции умноженную на константу С}

if t[h]=0 then writeln('такого нет'){ если в ячейке таблицы с номером h ничего нет, то такого человека в базе нет}

else

while (j<max) do{ пока не найдем}

begin

h:=h1(s[1],s[2],s[3])+j*c;{ присваиваем h значение хеш-функции от первых трех букв фамилии + количество шагов хеш-фукнции умноженную на константу 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{ если первые три буквы фамилии человека, чей номер записан в ячейке таблицы с номером h, совпадают с первыми тремя буквами введенной фамилии, выводим его фамилию и номер телефона}

begin

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

end;

j:=j+1;{ увеличиваем количество шагов}

end;

 

 

vikidalka.ru - 2015-2018 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных