Блочный способ

Элементы линейного списка упорядочены по первичному ключу. Для удобства дальнейшего изложения предположим (здесь и далее по линейным спискам), что упорядочение выполнено по возрастанию значения ключа.

Список разделяется на виртуальные блоки размером √N элементов, где N – число элементов в списке. С ключом доступа К_доступ сравниваются ключевые поля последних элементов в блоках - К_j^блока, начиная с первого блока (j – номер блока). С помощью такого сравнения вначале определяется блок, в котором возможно нахождение элемента доступа, а затем уже, как правило, методом последовательного сканирования - сам элемент в блоке.

Рассмотрим вначале, как выполняется задача просмотра.

Пример 3. Пусть линейный список имеет вид таблицы 3. Надо просмотреть адрес студента по фамилии Скворцов, т.е. q^{просмотр} = (Фамилия= Скворцов, Домашний адрес), где К_доступ = Скворцов.

Таблица 3

Очевидно, N = 4. Тогда список разбивается на 2 блока размером по 2 элемента (последние элементы блоков имеют номера 2 и 4).

Для решения задачи выполняются следующие шаги:

1. выбирается последний элемент первого блока;

2. ключевое поле сравнивается с ключом доступа: Соколов = Скворцов;

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

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

5. выбирается предыдущий элемент;

6. ключевое поле сравнивается с ключом доступа: Скворцов = Скворцов;

7. ключи равны, поэтому выводится адрес: пр. Мира, 45 – 3; алгоритм заканчивает работу.

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

1. выбирается последний элемент первого блока;

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

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

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

5. выбирается предыдущий элемент;

6. ключевое поле сравнивается с ключом доступа: Скворцов = Сидоров;

7. поскольку ключи не равны, а список упорядочен, определяется возможность наличия искомого элемента в данном блоке: Скворцов > Сидоров;

8. условие выполняется, поэтому делается попытка выбрать предыдущий элемент блока. Однако блок просмотрен полностью. Выводится диагностическое сообщение об отсутствии искомого элемента в данном списке; алгоритм заканчивает работу.

Задача добавления нового элемента решается аналогично способу, рассмотренному ранее для упорядоченного списка.