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

 

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

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). Когда второй список становится слишком большим, он «включается» в основной и его элементы занимают положенные им позиции в основном списке. Такая процедура называется ведением списка.








Дата добавления: 2015-03-03; просмотров: 622;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.