Связанное распределение

В лекции 11 даны примеры и программные реализации списков, стеков и очередей. Неудобство включения и исключения элементов при последовательном распределении происходит из-за того, что порядок следования элементов задается неявно требованием, чтобы смежные элементы последовательности находились в смежных ячейках памяти. В результате многие элементы последовательности во время включения или исключения должны передвигаться. Если это требование опущено, то можно выполнить операции включения и исключения без того, чтобы передвигать элементы последовательности. При связанном распределении последовательности (связанном списке) каждому

$s_i$

поставлен в соответствии указатель (ссылка)

$P_i$

, отмечающий ячейку, в которой записаны

$s_{i + 1}$

$P_{i + 1}$

. Существует также указатель

$P_0$

, который указывает начальную ячейку последовательности, то есть ячейку с символами

$s_1$

$P_1$

. Все сказанное выше проиллюстрировано на рис. 3.1.

Рис. 3.1.

Здесь каждый узел состоит из двух полей. Под узлом понимается одно или несколько последовательных слов в памяти машины, которые выступают как единое целое и разделены на части, именуемые полями. В поле

$INFO$

размещен сам элемент последовательности, а в поле

$LINK$

- указатель на следующий за ним элемент.

Linked list - список с использованием указателей: список, в котором каждый элемент содержит указатель на следующий элемент или два указателя - на следующий и предыдущий. Поскольку для

$s_n = INF0(l_n)$

следующего элемента не существует, будем использовать обозначение

$P_n = LINK(l_n ) = \Lambda$

, где

$\Lambda$

- пустой , или нулевой указатель . Так как точные значения

$l_1,l_2,\ldots,l_n$

для программиста не существенны, то в более общем виде связанное представление, показанное на рис. 3.1, можно изобразить так, как показано на рис.3.2.

Рис. 3.2. Другой, более употребительный, способ представления списка

Связанное представление последовательностей облегчает операции включения элемента после некоторого

$s_i$

и исключения элемента

$s_{i + 1}$

, если ячейка для

$s_i$

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

$s_2$

из последовательности, изображенной на рис. 3.2, необходимо только положить

$LINK(l_1 ) = LINK(l_3 );$

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