4.1. Тема: Прямий доступ та хешування.
4.2. Мета роботи: Здобути навички організації даних у вигляді таблиць прямого доступу та хешованих таблиць.
4.3. Теми для попередньої роботи
4.3.1. Статичні структури даних
4.3.2 Файли
4.3.3. Пошук
4.3.4. Прямий доступ
4.3.5. Хешування, функції хешування
4.4. Індивідуальні завдання
Для вмісту файла створити таблицю прямого доступу або хеш-таблицю. Перевірити працездатність створених таблиць на прикладі операцій пошуку. Порівняти час пошуку даних по ключу безпосередньо у файлі та із використанням створених таблиць.
Індивідуальне завдання обрати у таблиці 1 так, що N= Nспик. mod 2,
де Nспик. – номер студента по списку у журналі групи.
Таблиця 1. Вихідні дані до лабораторної роботи
|
N |
Вміст вихідних даних |
Таблиця |
Хеш -функція |
Примітка |
|
1 |
Номер залікової книжки Прізвище студента Середній бал |
Хеш-таблиця з повторним хешуванням |
Ділення по модулю Повторне хешування: Адр=Адр+1 |
Ключ - прізвище |
|
2 |
Модель процесора Тип материнської плати Об’єм вінчестера Розмір ОЗП |
Хеш-таблиця з повторним хешуванням |
Ділення по модулю Повторне хешування: Адр=Адр+1 |
Ключ – (об’єм вінчестера/ розмір ОЗП) |
|
3 |
Номер читацького білета Прізвище читача Кількість книжок |
Хеш-таблиця з пакетуванням |
Функція згортки та ділення по модулю |
Ключ - прізвище |
|
4 |
Код Тип двигуна Кількість обертів Потужність |
Таблиця прямого доступу |
Ключ - код |
|
|
5 |
Мережна адреса станції Операційна система Мережний протокол |
Хеш-таблиця з розподіленими ланцюжками переповнення |
Функція перетворення системи обчислення та ділення по модулю |
Ключ – мережна адреса станції |
|
6 |
Код Тип літака Кількість пасажирів Швидкість |
Таблиця прямого доступу |
Ключ - код |
|
|
8 |
Обліковий номер картки Прізвище чоловіка Вік |
Хеш-таблиця з розподіленими ланцюжками переповнення |
Функція середини квадрата |
Ключ- обліковий номер картки |
Продовження таблиці 1.
|
8 |
Код виробу Назва Ціна Кількість |
Хеш-таблиця із спільним просто-ром переповнення |
Функція перетворення системи обчислення та ділення по модулю |
Ключ- код виробу |
|
9 |
Ідентифікаційний код Ім’я користувача мережі Адреса Е-mail |
Хеш-таблиця з розподіленими ланцюжками переповнення |
Функція середини квадрата та ділення по модулю |
Ключ – ідентифікаційний код |
|
10 |
Код міста Назва міста Площа Кількість мешканців |
Хеш-таблиця з повторним хешуванням |
Функція згортки та ділення по модулю |
Ключ - код міста |
|
11 |
Код країни Назва країни Столиця |
Хеш-таблиця із спільним просто-ром переповнення |
Функція середини квадрата |
Ключ - код країни |
|
12 |
Табельний номер Прізвище працівника Цех або відділ |
Хеш-таблиця з розподіленими ланцюжками переповнення |
Функція згортки та ділення по модулю |
Ключ - табельний номер працівника |
|
13 |
Назва файлу Розмір Дата створення |
Хеш-таблиця з пакетуванням та повторним хешуванням |
Функція згортки та ділення по модулю. Повторне хешування: Адр=Адр+1 |
Ключ - назва файлу |
|
14 |
Номер телефону Прізвище власника Адреса Час розмови |
Хеш-таблиця з розподіленими ланцюжками переповнення |
Функція середини квадрата |
Ключ – номер телефону |
|
15 |
Шифр книги Прізвище автора Кількість примірників |
Хеш-таблиця із спільним просто-ром переповнення |
Функція згортки та ділення по модулю |
Ключ – шифр книги |
4.5. Типове завдання
У файлі записані прізвища студентів. Для вмісту файлу створити хеш-таблицю на 10 елементів із розподіленими ланцюжками переповнення (у списки записувати прізвища – синоніми). Функція хешування визначається як:
Адреса = ∑(Код)i mod 10
де: ∑(Код)i - сума кодів усіх літер прізвища,
mod - залишок від цілочисельного ділення.
Перевірити працездатність хеш-таблиць. Результати видати на екран.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
