Размещение элементов в упорядоченном списке

Для размещения элемента с ключом К_доступ в упорядоченном списке возможны два подхода:

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

2. использование областей переполнения.

Первый подход показан ниже:

1. пусть исходный список соответствует таблице 8:

Таблица 8

2. добавляется элемент со структурой таблицы 9, т.е. q^{добавление} = (Фамилия= Стручков, Имя = Петр, Отчество= Кузьмич, Номер зачетной книжки = 18345, Домашний адрес= ул. Леонова, 14-16):

Таблица 9

3) результирующий список соответствует таблице 10 (добавленный элемент выделен заливкой):

Таблица 10

Как видно, включение нового элемента со значением ключа Стручков вызвало перемещение элементов, следующих за ним в списке (в нашем примере – это элемент с ключом Супруненко). Если в памяти компьютера элементы исходного списка занимали физически последовательные адреса, такое перемещение выражается в перезаписи всех элементов, расположенных после добавляемого элемента. Очевидно, такой подход не рационален, так как влечет дополнительные временные затраты и лишние операторы ввода-вывода на машинный носитель.

Использование областей переполнения позволяет по-другому решить задачу. Для этого вводится дополнительный список – область переполнения, и именно туда помещается вновь поступающий элемент. Чтобы показать, как он должен быть размещен в исходном списке, в состав полей основного списка вводится дополнительное поле, куда помещается ссылка на новый элемент.

Иллюстрация этого подхода показана ниже:

1. исходный список представлен таблицей 11:

Таблица 11

2. добавляется элемент со структурой таблицы 12, т.е. q^{добавление} = (Фамилия= Стручков, Имя = Петр, Отчество= Кузьмич, Номер зачетной книжки = 18345, Домашний адрес= ул. Леонова, 14-16):

Таблица 12

3. он размещается в области переполнения – таблица 13 (первоначально она пуста):

Таблица 13

4) модифицируется исходный список – таблица 14 (новое данное выделено заливкой):

Таблица 14

Как видно, модификация основного списка состоит в изменении одного из полей того элемента, за которым должен следовать вновь поступивший элемент: в поле Ссылка на область переполненияпомещается порядковый номер добавляемого элемента из области переполнения. Таким образом, новый список состоит из двух частей: основного модифицированного списка (таблица 14) и списка - области переполнения (таблица 13). Когда второй список становится слишком большим, он «включается» в основной и его элементы занимают положенные им позиции в основном списке. Такая процедура называется ведением списка.