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

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

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

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

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

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

Таблица 8

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
	Скворцов	Олег	Иванович		пр. Мира, 45 - 3
	Соколов	Юрий	Кузьмич		ул. Леонова, 23 - 98
	Строков	Иван	Иванович		ул. Красная, 9 - 2
	Супруненко	Виктор	Егорович		Каштановая аллея, 23 - 5

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

Таблица 9

Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
Стручков	Петр	Кузьмич		ул. Леонова, 14 - 16

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

Таблица 10

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
	Скворцов	Олег	Иванович		пр. Мира, 45 - 3
	Соколов	Юрий	Кузьмич		ул. Леонова, 23 - 98
	Строков	Иван	Иванович		ул. Красная, 9 - 2
	Стручков	Петр	Кузьмич		ул. Леонова, 14 - 16
	Супруненко	Виктор	Егорович		Каштановая аллея, 23 - 5

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

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

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

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

Таблица 11

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес	Ссылка на область переполнения
	Скворцов	Олег	Иванович		пр. Мира, 45 - 3
	Соколов	Юрий	Кузьмич		ул. Леонова, 23 - 98
	Строков	Иван	Иванович		ул. Красная, 9 - 2
	Супруненко	Виктор	Егорович		Каштановая аллея, 23 - 5

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

Таблица 12

Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
Стручков	Петр	Кузьмич		ул. Леонова, 14 - 16

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

Таблица 13

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
	Стручков	Петр	Кузьмич		ул. Леонова, 14 - 16

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

Таблица 14

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес	Ссылка на область переполнения
	Скворцов	Олег	Иванович		пр. Мира, 45 - 3
	Соколов	Юрий	Кузьмич		ул. Леонова, 23 - 98
	Строков	Иван	Иванович		ул. Красная, 9 - 2
	Супруненко	Виктор	Егорович		Каштановая аллея, 23 - 5

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