Методи передачі даних в мережах | Організація обміну інформацією в мережі | Обробка інформації | Операції над даними | лінійні списки | Способи доступу по первинному ключу | блоковий спосіб | двійковий спосіб | Індексного-послідовний спосіб | Індексного-довільний спосіб |

загрузка...
загрузка...
На головну

рандомизация

Цей метод доступу має кілька назв: перемішування, рандомизация, хешування. Загальна схема представлена ??на малюнку 4:

Область розміщення елементів

лінійного списку

малюнок 4

Область розміщення елементів лінійного списку ділиться на ділянки - Бакета. при додаванні елементів лінійного списку відповідно до значень первинних ключів Доi алгоритм рандомізації визначає не адреса окремого елемента (як це було в попередніх випадках), а номер (адреса) Бакета. Сам елемент розміщується в Бакета в першому вільному місці - після вже наявних в ньому елементів. Таким чином, список елементів всередині Бакета не впорядкований.

При пошуку елемента алгоритм рандомізації по первинному ключу визначає спочатку номер Бакета, в якому повинен знаходитися елемент. Потім вже в знайденому Бакета методом послідовного сканування робиться спроба знайти потрібний елемент (див. Метод послідовного сканування для невпорядкованого списку).

алгоритм рандомізації складається з наступних кроків:

1. цей крок виконується тільки для нечислових значень ключа і полягає в їх перетворенні в числові значення. Для цього кожному символу алфавіту, який використовується для запису значення ключа, приписується десяткова цифра від 0 до 9, і ключ переписується. Наприклад, нехай значення ключа формуються з літер російського алфавіту. Припишемо їм десяткові цифри:



Розміщення елементів в упорядкованому списку | А б в г д е є ж з и й к л м н о п р с т у ф х ц ч ш щ ь ь и е ю я
загрузка...
© um.co.ua - учбові матеріали та реферати