Алгоритми і структури даних

У різних ситуаціях використовуються різні види списків. В односторон-ньому незв’язаному (singly linked) списку відсутні поля prev. У впорядковано-му (sorted) списку елементи розташовані в порядку зростання ключів таким чином, що у голови списку ключ найменший, а у хвоста списку – найбільший, на відміну від неврегульованого (unsorted) списку. У кільцевому списку (circular list) поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.

 

 

Розробити програму, яка читає з клавіатури послідовність цілих чисел ( ), жодне з яких не повторюється, зберігає їх до структури да-них (згідно з завданням) та видає на екран такі характеристики:

 кількість елементів;

 середнє арифметичне збережених елементів;

 мінімальний та максимальний елемент;

 четвертий елемент послідовності;

 елемент, що йде перед мінімальним елементом.

Наголосимо, що всі характеристики потрібно визначити із заповненої структури даних. Дозволено використовувати лише ті операції, що притаманні заданій структурі, наприклад, заборонено отримувати доступ до елемента із довільною позицією у черзі, яку реалізовано на базі масиву.

Використовувати готові реалізації структур даних (наприклад, STL) за-боронено.

 

 

Для виконання завдання до лабораторної роботи потрібно використати такі структури даних:

Варіант 1: черга.

Варіант 2: стек.

Варіант 3: однобічно зв’язаний список.

Варіант 4: двобічно зв’язаний список.

Варіант 5: кільцевий список.

Варіант 6: масив із довільним доступом.

 

 

Мета роботи: познайомитися з хеш-функціями і хеш-таблицями та отримати навички програмування алгоритмів, що їх обробляють.

 

 

Часто виникає потреба використання динамічної множини, що підтри-мує тільки «словникові операції» додавання, пошуку і видалення елемента. У цьому випадку часто застосовують так зване хешування; відповідна структура даних називається хеш-таблицею. У гіршому випадку пошук у хеш-таблиці може займати стільки ж часу, скільки пошук у списку , але на практиці хешування вельми ефективне.

Тоді як при прямій адресації елементу з ключем відводиться позиція номер , при хешуванні цей елемент записується в позицію номер в хеш-таблиці (hashtable) , де – деяка функція, звана хеш-функцією (hash function).

Хороша хеш-функція повинна (наближено) задовольняти припущенням рівномірного хешування: для чергового ключа всі хеш-значень повинні бути рівноймовірні.

Тривіальне хешування полягає у використанні хеш-функції, що повертає власний аргумент.

Побудова хеш-функції методом ділення із залишком (division method) полягає в тому, що ключу ставиться у відповідність залишок від ділення на , де – число можливих хеш-значень: .

Наприклад, якщо розмір хеш-таблиці і ключ дорівнює , то хеш-значення дорівнює .

Хороші результати зазвичай виходять, якщо вибрати за просте число, яке є далеким від ступенів двійки.

Побудова хеш-функції методом множення (multiplication method) полягає в такому.

Нехай кількість хеш-значень дорівнює . Зафіксуємо константу в ін-тервалі і покладемо , де – дрібна час-тина .

Перевага методу множення полягає в тому, що якість хеш-функції мало залежить від вибору . Зазвичай за вибирають ступінь двійки, оскільки в більшості комп’ютерів множення на таке реалізується як зсув слова.

Хешування Пірсона (Pearson hashing) – алгоритм, запропонований Піте-ром Пірсоном для процесорів з 8-бітними регістрами, завданням якого є швид-ке обчислення хеш-коду для рядка довільної довжини. На вході функція отри-мує слово , що складається з символів, кожен розміром 1 байт, і повертає значення в діапазоні від до . Значення хеш-коду залежить від кожного символу вхідного слова.

Алгоритм, який отримує на вхід рядок і використовує таблицю перес-тановок можна описати таким кодом мовою Python:

def hash_pearson(w):

h = 0

for c in w:

index = h ^ ord(c)

h = T[index]

return h

 

 

Розробити програму, яка читає з клавіатури цілі числа , пар (при цьому ключ – ціле, дійсне число або рядок залежно від варіанта завдання; значення – рядок; усі рядки розміром до символів, жодний з яких не повторюється) та ще ключів. Всі рядки розділяються пропуском або новим рядком. Програма зберігає пар рядків до хеш-таблиці та видає на екран значення, що відповідають переліченим клю-чам.

Приклад входу для ключів-рядків:

Використовувати готові реалізації структур даних (наприклад, STL) за-боронено, але можна використати реалізацію рядків (наприклад, std::string в C++).

 

 

Варіант 1: ключ – ціле число; тривіальне хешування.

Варіант 2: ключ – ціле число; хешування за допомогою ділення.

Варіант 3: ключ – ціле число; мультиплікативне хешування.

Варіант 4: ключ – дійсне число; мультиплікативне хешування.

Варіант 5: ключ – рядок; хешування за остачею суми символів.

Варіант 6: ключ – рядок; хешування Пірсона.

 

 

Мета роботи: ознайомитися