Последовательное и связанное распределение данных

Последовательное распределение

С вычислительной точки зрения простейшим представлением [3] конечной последовательности является список ее членов, расположенных по порядку в последовательных ячейках памяти.

 

d ®

Ячейка памяти	S1	S2	S3	…	Sn-1	Sn
Адреса ячеек памяти	l 1	l2	l3		ln-1	ln

 

l₂ = l₁ + d

l₃ = l₁ + 2d

…

l_n = l₁ + (n-1) d

 

Таким образом, представляется последовательное распределение данных S ₁, S ₂,…, S_n, для каждого элемента которой требуется объем памяти d, l_i — адрес ячейки.

Такое представление имеет ряд преимуществ. Во-первых, оно легко осуществимо и требует небольших расходов памяти. Во-вторых, существует простое соотношение между номером элемента i  и адресом ячейки, в которой хранится S_i: l_i = l ₁ + (i -1) d. Это соотношение позволяет организовать прямой доступ к любому элементу последовательности. В-третьих, оно имеет широкий диапазон и включает в себя представление многомерных массивов.

Последовательное распределение имеет значительный недостаток. Оно становится неудобным, если требуется изменить последовательность путем включения новых и исключения имеющихся там элементов. Включение между S_i и S_{i +1} нового элемента требует сдвига S_{i +1}, … S_n вправо на одну позицию, а исключение соответственно — сдвиг влево.

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

 

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

Неудобство включения и исключения элементов при последовательном распределении происходит из-за того, что порядок следования элементов задается неявно требованием, чтобы смежные элементы последовательности находились в смежных ячейках памяти. Если это требование опустить, то можно выполнять операции включения и исключения без передвижения элементов последовательности. Конечно, необходимо сохранять информацию о способе упорядочения элементов, но можно это делать явным образом. В частности, при связанном распределении данных каждому S_i поставлен в соответствие указатель Р _i, отмечающий ячейку, в которой записаны S_{i +1} и P_{i +1} (т.е. переход на следующую ячейку последовательности). Существует также указатель P ₀, который указывает на начальную ячейку последовательности, т.е. на ячейку с содержимым S ₁ и P ₁.

 

(INFO) (LINK)

P0=l1	S1	P1=l2		S2	P2=l3	…	Sn-1	Pn-1=ln		Sn	Pn= L
	l1			l2			l n-1			l n

 

Рис. 2.1. Представление последовательности в виде связанного списка.

Каждый элемент списка состоит из поля INFO (содержащего элемент последовательности) и поля LINK (содержащего адрес следующего элемента)

 

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

 

P0	S1			S2		…	Sn-1			Sn

 

Рис. 2.2. Способ задания списка

 

Связанное представление данных облегчает операции включения и исключения элемента, если ячейка S_i известна. Для этого лишь необходимо, изменить значение некоторых указателей. Например, чтобы исключить элемент S ₂ из последовательности, изображенной на рис. 2.2, необходимо положить LINK(l ₁)=LINK(l ₂). После этой операции элемента S ₂  в последовательности больше не будет.

 

P0	S1			S2			S 3		…

 

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

 

Чтобы в последовательность (рис. 2.2) включить новый элемент S ₅ после S ₁, необходимо воспроизвести новый элемент в некоторой ячейке l ₅ с INFO(l ₅) = S ₅ и LINK(l ₅) =LINK(l ₁) и присвоить LINK(l ₁) l ₅.

 

P0	S1			S2			S3		…

 

 

S5
l5

 

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

 

Также легко осуществляется сцепление последовательностей и разбиение последовательности на части.

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

 С помощью связанного распределения достигается большая гибкость, но идет потеря скорости обращения к данным. При последовательном представлении фиксированное соотношение между i и ячейкой S_i позволяет, в частности, иметь быстрый и прямой доступ к любому элементу последовательности. В связанном распределении такого соотношения не существует, и доступ ко всем элементам последовательности, кроме первого, не является прямым и эффективным. Кроме того, при связанном представлении приходится тратить память на P_i.

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

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

 

Разновидности связанных списков

Если P_n указывает на S ₁, то такая форма списка дает возможность достигнуть любой элемент списка (хотя и не прямо) из любого другого элемента последовательности.

 

P₀

 

S1

S2

…

Sn-1

Sn

 

Рис. 2.5. Циклический список

 

Включение и исключение элементов здесь осуществляется так же, как и в нециклических списках, в то время как сцепление и разбиение реализуется более сложно.

Большая гибкость при работе со списками достигается, если использовать дважды связанный список, когда каждый элемент S_i последовательности вместо одного имеет 2 связанных с ним указателя, они указывают на элементы S_{i -1}  и S_{i +1}.

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

 

P₀

 

L

S1

S2

…

Sn-1

Sn

L

 

Рис. 2.6. Дважды связанный список

 

Стеки и очереди

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

В обоих случаях операции включения и исключения производятся только на концах последовательности [3].

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

Правило работы со стеком: «Первым пришел — последним ушел».

 

Очередь — это последовательность, в которой все включения производятся на одном конце списка (в конце очереди), в то время как все исключения производятся на другом (в начале очереди).

Правило работы с очередью: «Первым пришел — первым ушел».

Стеки и очереди имеют важное значение в бухгалтерском деле.

Введем следующие обозначения:

D Ü X Добавить X к D. Если D — стек, то X помещается в вершину, если D — очередь, то Х добавляется в ее конец.

X Ü D Присвоить переменной Х значение верхнего элемента D, если D — стек, или начального элемента, если D — очередь. Этот элемент затем из D исключается.

Последовательная реализация списков

Для стеков это распределение весьма удобно. Все, что нам нужно, это переменная, например t, чтобы следить за вершиной стека S. Предположим, что для S отведены ячейки S (1), S (2), …, S (m), тогда пустой стек соответствует случаю t = 0. Операции включения и исключения в стек при этом следующие:

 

S Ü X tt+1
if t>m then overflow {переполнение}
  else s(t) X

X Ü S if t=0 then underflow {нехватка}
  else X S(t)

              t t-1

 

Здесь overflow означает переполнение или отсутствие в стеке места для добавления X, что означает ошибку.

Underflow означает, что делается попытка удалить элемент из пустого стека, как правило, этот оператор означает окончание алгоритма.

Последовательное распределение очереди сложнее потому, что она растет на одном конце и убывает на другом.

Если ничего не предпринимать, то очередь начнет медленно двигаться и перейдет границу отведенных для нее ячеек. Чтобы это не произошло для очереди Q будем использовать m ячеек Q (0), Q (1), …, Q (m -1), связанных круговым способом, и считаем, что Q (0) следует за Q (m -1). Если использовать переменную f в качестве указателя ячейки, расположенной непосредственно перед началом очереди, а переменную r в качестве указателя ее конца, то очередь будет состоять из элементов Q (f +1), Q (f +2), …, Q (r). Согласно этому определению, пустая очередь соответствует случаю r = f. Мы имеем:

 

Q Ü X r r+1 {ограничено величиной m }
if r > m then overflow
    else Q(r) X

X Ü Q if r = f then underflow
    else X Q(f)

               f f+1