ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Листинг 2.6. Реализация некоторых операторов списка при использовании курсоров

Алгоритмы структуры данных

Листинг 2.6. Реализация некоторых операторов списка при использовании курсоров

procedure INSERT ( x: elementtype; p: position; var L: LIST );

begin

if p = 0 then begin { вставка х в первую позицию }

if move(available, L) then

SPACE[L].element:= x

end

else { вставка х в позицию, отличную от первой }

if move(available, S PACE [p] .next) then

SPACE [SPACE [Р]. next].element:- x

end; { ItJSERT }

 

procedure DELETE ( p: position; var L: LIST );

begin

if p = 0 then

move(L, available) 

else

move(SPACE [p].next, available)

end; { DELETE }

 

procedure initialize

{initialize связывает ячейки SPACE в один свободный список }

var

і: integer

begin 

for i:= maxlength - 1 downto 1 do

SPACE[i].next:= і + 1;

available:= 1;

SPACE[maxlength].next:= 0

{ помечен конец свободного списка }

end; { initialize }

 

Дважды связные списки

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

 

 

 

 

Другое важное преимущество дважды связных списков заключается в том, что мы можем использовать указатель ячейки, содержащей і-й элемент, для определения і-й позиции — вместо использования указателя предшествующей ячейки. Но ценой этой возможности являются дополнительные указатели в каждой ячейке и определенное удлинение некоторых процедур, реализующих основные операторы списка. Если мы используем указатели (а не курсоры), то объявление ячеек, содержащих элементы списка и два указателя, можно выполнить следующим образом (previous —поле, содержащее указателе на предшествующую ячейку):

type

celltype = record

element: elementtype;

next, previous: ↑ celltype 

end;

position = ↑ celltype;

Процедура .удаления элемента в позиции р дважды связного списка показана в листинге  2.7. На рис. 2.8 приведена схема удаления элемента в предположении, что удаляемая ячейка не является ни первой, ни последней в списке(в этой связи отметим, что на практике обычно делают так, что ячейка заголовка дважды связного списка "замыкает круг" ячеек, т.е. указатель поля previous ячейки заголовка указывает на последнюю ячейку, а указатель поля next — на первую. Поэтому при такой реализации дважды связного списка нет необходимости в выполнении проверки на "нулевой указатель". Иногда этот оператор реализуется в виде функции, возвращающей удаляемый элемент.)

. На этой схеме сплошными линиями показаны указатели до удаления, а пунктирными — после удаления элемента. В процедуре удаления сначала с помощью указателя поля previous определяется положение предыдущей ячейки. Затем в поле next этой (предыдущей) ячейки устанавливается указатель, указывающий на ячейку, следующую за позицией р. Далее подобным образом определяется следующая за позицией р ячейка и в ее поле previous устанавливается указатель на ячейку, предшествующую позиции р. Таким образом, ячейка в позиции р исключается из цепочек указателей и при необходимости может быть использована повторно.

 

21