Хешування (метод обчислення адреси)

Хай у кожному з М елементів масиву Т міститься елемент списку (наприклад ціле позитивне число). Якщо є деяка функція H(V), що обчислює однозначно по елементу V його адресу - ціле позитивне число з інтервалу [0, M-1], то V можна зберігати в масиві T з номером H(V) тобто V = T(H (V)). При такому зберіганні пошук будь-якого елементу відбувається за постійний час не залежне від M.

Масив T називається масивом хешування, а функція H - функцією хешування.

При конкретному застосуванні хешування зазвичай є певна область можливих значень елементів списку V і деяка інформація про них. На основі цього вибирається розмір масиву хешування M і будується функція хешування. Критерієм для вибору M і H є можливість їх ефективного використання.

Приклад.

Завдання для виконання лабораторної роботи №7.

1. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений односпрямованим списком. Пошук провести методом бінарного пошуку.

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

3. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений односпрямованим списком. Пошук провести методом М-блочного пошуку.

4. Написати програму, що реалізує пошук імені абонента телефонної станції за його телефонним номером. Телефонний довідник організований односпрямованим списком. Пошук провести методом М-блочного пошуку.

5. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений односпрямованим списком. Пошук провести методом обчислення адреси.

6. Написати програму, що реалізує пошук імені абонента телефонної станції за його телефонним номером. Телефонний довідник організований односпрямованим списком. Пошук провести методом обчислення адреси.

7. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений циклічним списком. Пошук провести методом бінарного пошуку.

8. Написати програму, що реалізує пошук імені абонента телефонної станції за його телефонним номером. Телефонний довідник організований циклічним списком. Пошук провести методом бінарного пошуку.

9. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений циклічним списком. Пошук провести методом М-блочного пошуку.

10. Написати програму, що реалізує пошук імені абонента телефонної станції за його телефонним номером. Телефонний довідник організований циклічним списком. Пошук провести методом М-блочного пошуку.

11. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений циклічним списком. Пошук провести методом обчислення адреси.

12. Написати програму, що реалізує пошук імені абонента телефонної станції за його телефонним номером. Телефонний довідник організований циклічним списком. Пошук провести методом обчислення адреси.

13. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений двонаправленим списком. Пошук провести методом бінарного пошуку.

14. Написати програму, що реалізує пошук імені абонента телефонної станції за його телефонним номером. Телефонний довідник організований двонаправленим списком. Пошук провести методом бінарного пошуку.

15. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений двонаправленим списком. Пошук провести методом М-блочного пошуку.

16. Написати програму, що реалізує пошук імені абонента телефонної станції за його телефонним номером. Телефонний довідник організований двонаправленим списком. Пошук провести методом М-блочного пошуку.

17. Написати програму, що реалізує пошук перекладу слова в англо-російській словнику. Словник представлений двонаправленим списком. Пошук провести методом обчислення адреси.

18. Написати програму, що реалізує пошук імені абонента телефонної станції за його телефонним номером. Телефонний довідник організований двонаправленим списком. Пошук провести методом обчислення адреси.

Вимоги до звіту:

Звіт з лабораторної роботи повинен відповідати наступній структурі:

1. Словесна постановка задачі. У цьому підрозділі проводиться повний опис завдання. Описується суть завдання, аналіз вхідних в неї фізичних величин, район їх допустимих значень, одиниці їх вимірювання, можливі обмеження, аналіз умов при яких завдання має рішення (не має рішення), аналіз очікуваних результатів.

2. Математична модель. У цьому підрозділі вводяться математичні описи фізичних величин і математичний опис їх взаємодій. Мета підрозділу - представити вирішувану задачу в математичній формулюванні.

3. Алгоритм рішення задачі. У підрозділі описується розробка структури алгоритму, обгрунтовується абстракція даних, завдання розбивається на підзадачі. Приводится схема алгоритму або псевдокод. Вказується оцінка алгоритму.

4. Лістинг програми.

5. Контрольний тест. Підрозділ містить набори вихідних даних і отримані в ході виконання програми результати.

6. Висновки з лабораторної роботи.

Лабораторна робота №8

Тема: Алгоритми на графах. Алгоритми обходу графа.

Мета лабораторної роботи – закріплення теоретичного матеріалу, отримання практичних навичків застосування алгоритмів обходу графа, вирішення завдання обходу графа на основі пошуку в ширину і пошуку в глибину.