Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
учебник Информатика.doc
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
17 Мб
Скачать
☆

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

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

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

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

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

                                                               Таблица 3

№ п/п

Фамилия

Имя

Отчество

Номер зачетной книжки

Домашний адрес

1

Скворцов

Олег

Иванович

02544

пр. Мира, 45 - 3

2

Соколов

Юрий

Кузьмич

01278

ул. Леонова, 23 - 98

3

Строков

Иван

Иванович

02343

ул. Красная, 9 - 2

4

Супруненко

Виктор

Егорович

02347

Каштановая аллея, 23 - 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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