Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Варіанти індивідуальних завдань. 1. Розробити функцію, яка:



1. Розробити функцію, яка:

 

1.1. Визначає чи входить елемент Е до дерева Т;

1.2. Визначає кількість входжень елемента Е до дерева Т;

1.3. Обчислює суму елементів дерева Т;

1.4. Визначає найбільше значення елемента дерева Т;

1.5. Виводить до масиву елементи усіх листів дерева Т;

1.6. Визначає максимальну глибину дерева Т;

1.7. Підраховує кількість вершин на n-му рівні дерева Т;

1.8. Записує до файлу f елементи дерева Т у порядку їх збільшення;

1.9. Додає до дерева Т новий елемент Е, якщо його не було у Т;

1.10. По файлу f, елементи якого всі різні, будує відповідне дерево пошуку Т.

 

2. Для дерева пошуку Т визначити чи є воно збалансованим.

 

3. Розробити функцію додавання нового елемента Е до дерева пошуку, використовуючи AVL – дерева.

 

4. Для дерева пошуку Т виконати реалізацію на його базі RB – дерева.

 

5. Написати функцію, яка присвоює параметру «max» значення самого правого елемента дерева Т.

 

9.4 Контрольні питання та завдання

 

1. Надайте визначення поняттям дерево та граф.

2. Які методи реалізації дерев та графів використовуються у програмуванні?

3. Яким чином виконується реалізація множини на базі дерев?

4. Що таке збалансовані дерева?

5. Чим визначається час пошуку даних у збалансованому дереві?

6. Що таке двійникові дерева?

7. З якою метою використовуються дерева та графи у програмуванні?

8. Надайте визначення наступним поняттям: термінальна вершина дерева, власна вершина дерева, висота дерева, шлях, довжина шляху.

9. Що таке AVL-дерева? З якою метою вони використовуються у програмуванні?

10. Опишіть схеми збереження збалансованості дерев при добавленні та вилученні елементів дерева на базі AVL-дерев.

11. Що таке червоно-чорні дерева? З якою метою вони використовуються у програмуванні?

12. Опишіть схеми збереження збалансованості дерев при добавленні та вилученні елементів дерева на базі RB-дерев.

 

 

ВИКОРИСТАННЯ ХЕШ-ФУНКЦІЙ

 

Мета роботи

 

Вивчення методів використання хеш-функцій у середовищі мови С++. Отримання практичних навичок по використанню хеш-функцій при вирішенні практичних завдань.

10.2 Організація самостійної роботи студентів

 

Під час підготовки до виконання лабораторної роботи необхідно вивчити індивідуальне завдання (п. 10.3), виконати розробку алгоритму вирішення задачі та підготовити текст програми щодо реалізації розробленого алгоритму, підготовити відповідні розділи звіту та вивчити відповідний теоретичний матеріал, який викладено у лекції: „Хеш-реалізація множин у С++” та відповідного матеріалу у наступних підручниках і навчальних посібниках [1, 4, 5, 7, 8].

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

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

1) її можна було легко обчислювати;

2) вона повинна приймати різні значення приблизно з рівною ймовірністю;

3) бажано, щоб на близьких значеннях аргументу вона приймала далекі одне від одного значення (властивість, протилежна математичному поняттю безперервності).

У наведеному прикладі значення хеш-функції для відповідного прізвища дорівнює номеру першої букви прізвища в алфавіті.

Параметром реалізації хеш-функції є число підмножин, що також називають розміром хеш-таблиці. Нехай він дорівнює N. Тоді хеш-функція повинна приймати значення 0, 1, 2, ... , N - 1. Якщо є деяка функція H(x), що приймає довільні цілі позитивні значення, то в якості хеш-функції можна використовувати функцію h(x), яка дорівнює остачі від ділення H(x) на N.

Множина M розбивається на N непересічних підмножин, занумерованих індексами від 0 до N - 1. Підмножина з індексом i містить всі елементи x з M, тобто значення хеш-функції h(x), для яких дорівнюються i: Mi = {x € M : h(x) = i}

При пошуку елемента x спочатку обчислюється значення його хеш-функції: t = h(x). Після цього розшукується x у підмножині . Оскільки ця підмножина невелике, то пошук здійснюється швидко. Для ефективної реалізації кожна підмножина повинна, в більшості випадків, містити не більше одного елемента. Отже, розмір хеш-таблиці N повинен бути більше, ніж середнє число елементів множини. Звичайно N вибирають перевищуюче число елементів множини приблизно в три рази. У прикладі із записною книжкою це означає, що в ній повинне бути записане близько 10 прізвищ. У такому випадку більшість сторінок або порожні, або містять одне прізвище, хоча не виключені й колізії, коли на одній сторінці записані кілька прізвищ.

Це тільки ідея хеш-реалізації множини. Конкретні схеми по-різному реалізують масив підмножин та борються з колізіями. Приведемо найбільш універсальну схему, яка використовує реалізацію з посиланнями (рисунок 10.1). Кожна підмножина представляється у вигляді лінійного списку з одним напрямком, який містить елементи підмножини. Таким чином, є N списків. Голови всіх списків зберігаються в одному масиві розміру N, який називається хеш-таблицею. Елемент хеш-таблиці з індексом i відповідає голові i-го списку. Голова містить посилання на перший елемент списку, перший елемент – на другий і так далі. Останній елемент у ланцюжку містить нульове посилання, тобто посилання в нікуди. Якщо список порожній, то елемент хеш-таблиці з індексом i містить нульове посилання.

 

 
 
Голова і-го списку


Хеш-таблиця
Елементи множини

Рисунок 10.1

Розглянемо конструкції цикл для кожного та ітератори. На неформальній мові використовується конструкція цикл для кожного; наприклад, у випадку множини M можна записати наступний фрагмент програми:

цикл для кожного елемента x із множини M| дія(x);кінець циклу

 

У більшості структур даних такий цикл можна реалізувати, користуючись іншими діями, можливими для структури цього типу. Наприклад, для списку можна використовувати наступний фрагмент програми:

 

Встановити покажчик на початок списку; цикл поки покажчик не в кінці списку| дія(елемент за покажчиком);| переміщення покажчика уперед;кінець циклу

 

Множина відрізняється від всіх інших структур даних тим, що цикл для кожного неможливо змоделювати, користуючись іншими приписами множини. Тому виконання такого циклу повинне бути забезпечене реалізацією множини. Метод побудови циклу для кожного в залежить від використовуваної мови програмування та від конкретної бібліотеки класів або підпрограм. Як правило, створюється деякий об'єкт, що дозволяє послідовно перебирати елементи структури. Внутрішня побудова такого об'єкта залежить від структури даних і прихована від програміста. Об'єкт такого типу називають ітератором або енумератором. З ітератором можливі дві дії:

1. Перевірити, є чи ще елементи структури даних, які не були перебрані на попередніх кроках;

2. Одержати наступний елемент структури даних.

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

У випадку множини М цикл для кожного записується за допомогою ітератора таким чином:

ітератор := почати перебирання елементів множини M;цикл поки ітератор. Чи є ще елементи?| x := ітератор.Одержати наступний елемент множини;| дія(x);кінець циклу

Як видно з наведених прикладів, при реалізації на практиці множин з використанням хеш-функцій може використовуватися не тільки елементарні структури, а й комбінація декількох елементарних структур – наприклад, реалізація масиву множин може використовувати списки або дерева. Мистецтво програміста полягає в тому, щоб вибрати структуру даних, найбільш ефективну для розв'язуваної задачі, щоб у ній були відсутні масові операції, пам'ять витрачалася ощадливо, а пошук виконувався швидко. І, мабуть, один з головних критеріїв – це простота та добротність програми, яка буде отримана за наслідками проектування.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.