2015-04-08
900
Иногда возникает необходимость организовать эффективное перемещение по списку, как в прямом, так и в обратном направлениях; или по заданному элементу нужно быстро найти предшествующий ему и последующий элементы. В этих ситуациях можно дать каждой ячейке указатели и на следующие, и на предыдущие ячейки списка, т.е. организовать дважды связный список. На рис. 1.4 приведен такой список.
Рис. 1.4 Дважды связный список
Важным преимуществом является то, что можно использовать указатель ячейки, содержащей i -й элемент, для определения i -й позиции вместо использования указателя предшествующей ячейки. Однако при этом появляются дополнительные указатели и, следовательно, удлиняются некоторые процедуры. Ниже приведен код объявления дважды связного списка.
Type pt=^elem; {Указатель на элемент списка}
Elem=Record
Data: Integer; {Поле данных}
Next:pt; {Указатель на следующий элемент списка}
Previous: pt; {Указатель на предыдущий элемент списка}
End;
Var first:pt; {Указатель на первый элемент списка}
Ниже показаны процедуры построения двусвязного списка, а также удаления элемента из него. На рис. 1.5 приведена схема удаления элемента из дважды связного списка. Здесь предполагается, что удаляемая ячейка не является ни первой, ни последней в списке. Сплошными линиями показаны указатели до удаления, а пунктирными – после удаления элемента. Сначала с помощью указателя поля previous определяется положение предыдущей ячейки. Затем в поле next этой ячейки устанавливается указатель на ячейку, предшествующую позиции р. Таким образом, ячейка в позиции р исключается из цепочек указателей и при необходимости может быть использована повторно.
|
|
|
Procedure Make(var x: pt); {Построение списка из пяти элементов}
var t,y:pt;
i: integer;
begin
new(x);
x^.prev:=nil;
for i:=1 to 5 do
begin
y:=x;
readln(y^.data);
if i<>5 then
begin
new(x);
y^.next:=x;
x^.prev:=y;
end
else
y^.next:=nil;
end;
Procedure Delete (p:pt);
Begin
If p^.previous <> nil then {Удаление ячейки, не являющейся первой}
p^.previous^.next:=p^.next;
If p^.next <> nil then {Удаление ячейки, не являющейся последней}
p^. next^. previous:=p^. previous;
End;
Рис. 1.5 Удаление элемента из дважды связного списка
