повинен призводити до швидкого виконання табличних операцій. Залежно від способів розміщення записів в таблиці можливе використання різних методів виконання операцій обробки таблиць. Ефективність застосовуваних способів організації може бути оцінена, наприклад, у кількості переглядаються записів таблиці при виконанні операцій пошуку, вставки та видалення. p align="justify"> Далі слід характеристика основних способів побудови таблиць. Розглянуті способи мають різні показники по ефективності; для всіх перерахованих способів можуть бути виділені області додатків, в яких рекомендовані способи є найбільш доцільними. br/>
. Популярні таблиці
Найпростішим способом відшукання потрібного елемента є метод повного перегляду (сканування), коли шуканий ключ порівнюється по черзі з усіма ключами таблиці, починаючи з першого, аж до відшукання збігається елемента або до вичерпання записів. Якщо ключі в таблиці розташовані в довільному порядку (неупорядкована таблиця), цей спосіб є єдино можливим. p align="justify"> Операція вставки в невпорядковану таблицю може бути виконана шляхом додавання нового запису в кінець таблиці з коригуванням номери останньої зайнятої рядка. Операція видалення рядка може бути реалізована за допомогою переписування останнього запису таблиці на місце видаляється і відповідного коректування номери останнього рядка. p align="justify"> Середня кількість переглядаються записів таблиці при пошуку запису по ключу при припущенні рівної ймовірності використання ключів визначається наступним співвідношенням
= pN/2 + (1-p) N, (1)
де ймовірність того, що шукана запис мається на таблиці; кількість записів у таблиці. br/>
. Впорядковані таблиці
При великій кількості записів у таблиці (N>> 1) витрати на виконання повного перегляду стають значними. Ефективність процедури пошуку можна підвищити при розміщенні записів у таблиці в порядку зростання (чи зменшення) ключів (впорядкована, або сортована таблиця). Для пошуку потрібного запису в таких таблицях може бути використаний швидкий метод бінарного (двійкового) пошуку. Разом з тим, в упорядкованих таблицях ускладнюється реалізація операцій вставки і видалення записів, при виконанні яких для збереження впорядкованості стає необхідною перепакування записів таблиці. p align="justify"> Середня кількість переглядаються записів таблиці при використанні бінарного пошуку визначається як
= log2N. (2)
. Таблиці з обчислюваними адресами
Інший можливий спосіб побудови таблиць при великій кількості записів полягає в попередньому (перед безпосереднім пошуком по таблиці) обчисленні можливого місця розташування шуканої запису. Даний метод передбачає наявність деякої простої функції h (key), яка відображає безліч імен на безліч номерів рядків таблиці. Ця...
