Фамилия (ключ) Числовое значение ключа

Скворцов 81257352

Соколов 8515252

Строков 8975152

Супруненко 8067045415

2. приведение ключа к требуемому порядку:

· метод квадратов. Преобразование ключа показано в таблице 15:

Таблица 15

· сдвиг разрядов. Преобразование ключа показано таблице 16:

Таблица 16

Поскольку для последнего ключа (выделен полужирным курсивом) результат имеет 5 разрядов (требуется 4), с этим значением ключа продолжается работа по тому же методу (таблица 17):

Таблица 17

· метод складывания. Преобразование ключа показано таблицей 18:

Таблица 18

3) формирование реальных номеров бакетов. Для определения константы С выполним следующие вычисления:

С = N_max/9999 = 0009/9999 = 0,0009.

Тогда номера бакетов рассчитаны по приведенной ранее формуле и представлены в таблице 19:

Таблица 19

Для анализа эффективности методов построим схему распределения элементов исходного линейного списка (таблица 11) по бакетам:

1. метод квадратов. Распределение элементов по бакетам показано в таблице 20:

Таблица 20

2. сдвиг разрядов. Распределение элементов по бакетам показано в таблице 21:

Таблица 21

3. метод складывания. Распределение элементов по бакетам показано в таблице 22:

Таблица 22

Как показывает анализ, все три метода с одинаковой равномерностью заполняют бакеты: один бакет содержит два элемента, остальные – по одному, т.е. методы равноэффективны.

Решим задачу просмотраэлемента.

Пример 10. По ключу Супруненко требуется просмотреть домашний адрес студента, т.е. q^{просмотр} = (Фамилия= Супруненко, Домашний адрес), где К_доступ = Супруненко. Пусть линейный список после размещения соответствует таблице 22. Задача решается следующим образом:

1. по приведенным выше алгоритмам рандомизации определяется номер бакета для нужного ключа доступа – это 0004;

2. в данном бакете находится линейный список элементов, в общем случае, не упорядоченный по ключу. Поэтому к нему применим метод последовательного сканирования. Анализируется первый элемент бакета с ключом Соколов: Соколов = Супруненко;

3. поскольку условие не выполняется, выбирается следующий элемент;

4. его ключевое поле сравнивается с ключом доступа: Супруненко = Супруненко; условие выполняется, поэтому выводится результат – Каштановая аллея, 23 – 5. Алгоритм заканчивает работу.