Комбинаторные алгоритмы для программистов



             

Связанное распределение - часть 2


после такой операции элемента

s_2
в последовательности больше не будет (рис.3.3). Чтобы в последовательность, изображенную на рис. 3.2, включить новый элемент
s_5
, необходимо только воспроизвести новый элемент в некоторой ячейке
l_5
с
INFO(l_5 ) = s_5
и
LINK(l_5)=LINK(l_1)
и присвоить
LINK(l_1 ) \leftarrow l_5
.Это изображено на рис.3.4.

Исключение элемента из связанного списка

Рис. 3.3.  Исключение элемента из связанного списка

Включение элемента в связанный список

Рис. 3.4.  Включение элемента в связанный список

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

Будем предполагать, с целью использования в различных алгоритмах, существование операции порождения ячейки get_cell; если эта операция присутствует в правой части оператора присваивания, то она дает адрес (место) новой неиспользованной ячейки памяти. Таким образом, чтобы добавить элемент

s_5
, как показано на рис. 3.4 нужно фактически использовать оператор get_cell для того чтобы найти значение
l_5
. Проблему сбора ненужных ячеек памяти будем полностью игнорировать, предполагая лишь, что их каким-то образом собирают для последующего использования; такой процесс носит название сбора мусора.

Недостаток при связанном распределении - приходится тратить память на указатели

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




Содержание  Назад  Вперед