6 - 20=16
i=21 - 20=1
i=27 - 20=7
i=33 - 20=13
i=37 - 20=17
i=30 - 20=10
i=38 - 20=18=39 - 20=19=28 - 20=8=36 - 20=16=29 - 20=9=37 - 20=17=29 - 20= 9=32 - 20=12
Організація даних записів зображена на малюнку 3.1.
Малюнок 3.1 - Організація записів відповідно до адресної функцією виду i=A - з
Вказаного вище недоліку (великий обсяг невикористаної пам'яті) позбавлена ??адресна функція виду i=ОСТ (А / m), де m - ціле число; ОСТ - залишок від ділення А на m.
Значення m приймається рівним простому числу, яке безпосередньо більше або менше числа записів М: m=М ± 1. Виділяються дві зони пам'яті - основна та резервна. Основна зона містить m записів. Резервна зона призначена для розміщення записів-синонімів. При формуванні даних згідно з адресною функції спочатку проводиться заповнення основної зони. Якщо при цьому позиція основної зони, отримана при обчисл?? Нии, вже зайнята, то поточна запис поміщається в резервну зону і адресується з позиції основної зони. Надалі при такій ситуації нарощується ланцюжок записів у резервної зоні.
Завдання 5. Побудувати адресну функцію виду i=ОСТ (A / m), відповідно до обраного варіанту.
77, 89, 20, 41, 82, 36, 56, 45, 89, 22, 26, 82, 37, 82, 57, 83, 42
Розглянемо вихідний масив, значення m приймається рівним простому числу, яке безпосередньо більше або менше числа записів M:.
Визначимо число записів M і значення m: M=17, m=17 - 1=16.
Таким чином, адресна функція набуде вигляду: i=ОСТ (A/16).
Визначимо розміщення записів згідно з адресною функції, i=ОСТ (A / m):
i=ОСТ (77/16)=13=ОСТ (89/16)=9=ОСТ (20/16)=4=ОСТ (41/16)=9=ОСТ (82/16)=2= ОСТ (36/16)=4=ОСТ (56/16)=8=ОСТ (45/16)=13=ОСТ (89/16)=9=ОСТ (22/16)=6=ОСТ (26/16 )=10=ОСТ (82/16)=2=ОСТ (37/16)=5=ОСТ (82/16)=2=ОСТ (57/16)=9=ОСТ (83/16)=3
i=ОСТ (42/16)=10
Організація записів відповідно до адресної функцією виду i=ОСТ (A / m) показана на малюнку 3.2.
нелінійний бінарний доступ індексований
Рисунок 3.2 - Організація записів відповідно до адресної функцією виду i=ОСТ (A / m)
Таким чином, доступ до необхідних записів може здійснюватися не тільки шляхом порівняння шуканого значення ключа з ключами записів, видобутих з масиву за певним алгоритмом, але й у результаті обчислення місцезнаходження необхідної запису. Як було вище показано, можна використовувати спеціальну розстановку записів у пам'яті комп'ютера, яка порушує типову при послідовній організації даних впорядкованість записів за значеннями ключового атрибута.
2.2 Способи організації индексируемого масиву
Індексом називається набір адрес і ключів записів, які вибираються з основного масиву за певним законом. Окремий елемент набору індексів також називається індексом, хоча це не відповідає значенню слова index-список.
Існує кілька різних способів організації индексируемого масиву. Розглянемо два з них - це індексного-послідовний масив і рандомізований індекс.
індексного-послідовний масив...
