Работа состоит из двух частей:
сортировка и поиск.
Создать библиотеку, в которой разместить хеш-функцию и пользовательскую функцию ввода строки.
Прототипы функций поместить в заголовочный файл. Файл библиотеки компилировать
отдельно от основной программы.
1.
Сортировка. Выполнить
сортировку массива записей с использованием хеш-функции. Преобразовать ключ в
адрес с использованием заданной хеш-функции согласно своему варианту задания.
Способ разрешения коллизий – использование области переполнения. Оценить
хеш-функцию (2/3 записей должны располагаться в основной области).
2. Поиск. Ввести искомый ключ, преобразовать его в адрес. В основной области поиск выполнять по хеш-функции, в области переполнения – последовательный поиск. Отметить, где найдена запись (в основной области или области переполнения) или запись не найдена.
Варианты заданий
Алгоритмы перемешивания:
1. Метод квадратов
2. Сдвиг разрядов
3. Деление
4. Выделение разрядов
5. Преобразование системы счисления ключа
Окончательное
вычисление хеш-функции:
1. Деление по модулю
2. Умножение на константу
Методические указания
1. Для выполнения работы рекомендуется повторить следующие пункты Темы 7 Символы и строки:
· Строка как массив символов;
· Строка как указатель на символ;
· Инициализация строки;
· Массив строк;
· Функции для работы со строками;
2. Как
создать пользовательскую библиотеку – см. Тему
13 Доп. главы.
одним программным модулем.
3.
В качестве записей взять фамилии (см. ссылку Фамилии на странице
http://kappa.cs.petrsu.ru/~budniko/math1/kurs_2/index.htm , всего 131 фамилия)
Фамилии являются
ключами. Для преобразования ключа использовать 3 и 4 символы каждой фамилии.
Для размещения
фамилий описать двумерный массив символов размерности 131х20, каждая строка которого
представляет одну фамилию. Массив инициализировать фамилиями.
Пример инициализации массива строк см. на Ресурсе тема 7 Символы и строки п. Массив строк.
4.
Программа должна
содержать хеш-функцию, реализующую алгоритм перемешивания. Входным параметром
должна быть строка, представляющая одну фамилию. Выход функции – целое число,
полученное реализацией алгоритма перемешивания.
5.
Окончательно
вычисление хеш-функции (деление по модулю или умножение на константу) выполнить в основной программе.
6.
Не должно быть
промежуточных массивов для хранения значений ключей. Кроме массива фамилий, в
программе должно быть только два массива – для основной области и области
переполнения.
7.
Для того, что различать свободные и занятые участки основной области, рекомендуется предварительно все элементы массива основной
области заполнить условными символами, например "***". Вспомните, какая функция присваивает строки?
.
8.
Ссылки:
https://moodle.cs.petrsu.ru Программирование для студентов специальности Математика. Тема Поиск|Хеширование
http://citforum.ru/programming/theory/sorting/sorting2.shtml#4_2
https://ru.wikipedia.org/wiki/Хеширование
Вопросы для сдачи работы
1. Какие два вида библиотек можно создать в языке Си?
2. Что такое заголовочный файл?
3. Как осуществляется компиляция программы, содержащей бибилиотеку
4. Как Вы вербально оцениваете полученную хеш-функцию (плохая, хорошая...) и почему
5. Каково преимущество раздельной компиляции модулей в данной работе (имеется ввиду при выборе алгоритма перемешивания)