4.6.1. Включение нового узла в список за тем узлом, на
который предвартельно установлен указатель
Чтобы включить в список новый узел, необходимо выделить память для размещения элемента хранения этого узла и выполнить четыре операции установления связей (рис. 36). Ниже приведена процедура включения нового узла “справа” от узла, на который предварительно установлен указатель.
Рис. 36. Включение узла “справа” от узла, на который предварительно установлен указатель
|
Procedure Ins_Right( head,p: pDlist ); |
{ head – указатель на “голову” списка } | ||
|
|
{ p – предварительно установленный указатель} | ||
|
var q: pDlist; |
{ q – указатель на новый узел } | ||
|
Begin |
| ||
|
if ( head <> nil ) and ( p <> nil ) then |
{ указатель p действительно установлен? } | ||
|
Begin |
| ||
|
New( q ); |
{ создание нового узла } | ||
|
Readln( q^ . info ); |
{ заполнение информационного поля нового узла } | ||
|
q^. prev:=p; |
{ 1 - установка связи нового узла с предыдущим } | ||
|
q^. next:=p^ . next; |
{ 2 - установка связи нового узла со следуюшим } | ||
|
p^. next^. prev:=q; |
{ 3 - установка связи следующего узла с новым } | ||
|
p^. next:=q; |
{ 4 - установка связи предыдущего узла с новым } | ||
|
end; |
| ||
|
end; |
| ||
Процедура включения нового узла “слева” от узла, на который предварительно установлен указатель, выполняется аналогично (рис. 37). В отличие от односвязного списка, никакого прохода до узла, предшествующего узлу p^не требуется, достаточно обратиться к соответствующему атрибуту связи узлаp^.
Рис. 37. Включение узла “слева” от узла, на который предварительно установлен указатель
Ниже приведена процедура создания двусвязного циклического списка из n узлов.
|
Procedure Create_Double( var head: PDlist; n: byte ); var p: PDlist; i: byte; begin new( head ); head^.next:=head; head^.prev:=head; |
{ head – указатель на голову списка } { n – количество узлов в списке }
{ создание элементарного кольца }
| |
|
for i:=1 to n do begin |
{ cоздание циклического списка из n узлов } | |
|
new( p ); |
{ создание узла списка } | |
|
readln(p^.info); |
{ заполнение информационного поля узла } | |
|
p^.next:=head; |
{ операции } | |
|
p^.prev:=head^.prev; |
{ установки связей } | |
|
head^.prev^.next:=p; |
{ нового узла } | |
|
head^.prev:=p; |
{ и списка } | |
|
end; end; |
| |
Каким образом включаются узлы в список при выполнении процедуры Create_Double: “за” головным узлом или “перед” ним?
4.6.2. Исключение из списка узла, на который
предварительно установлен указатель
Исключение узла, на который предварительно установлен указатель, не требует поиска предыдущего узла (рис. 38). После исключения узла из списка и возвращения его элемента хранения в кучу, доступ к этому узлу по предварительно установленному указателю более невозможен, поэтому данному указателю следует присвоить значениеNIL.
Рис. 38. Исключение узла, на который предварительно установлен указатель
|
Procedure Del_Double( head: PDlist; |
{ head – указатель на “голову” списка } | |||
|
varp: PDlist); |
{ p – указатель на исключаемый узел } | |||
|
begin |
| |||
|
if ( head <> nil ) and (head^ .next <> head ) |
{ список не пуст и указатель p } | |||
|
and ( head^.prev <> head ) and ( p <> nil ) then |
{ установлен? } | |||
|
begin |
| |||
|
p^.prev^.next:=p^.next; |
{ изменить поле связи предыдущего узла } | |||
|
p^.next^.prev:=p^.prev; |
{ изменить поле связи следующего узла } | |||
|
dispose( p ); p:=nil |
{ элемент хранения исключаемого узла вернуть в кучу } | |||
|
end; |
| |||
|
end; |
| |||
Операция поиска узла в двусвязном циклическом списке и операция разрушения выполняются так же, как в односвязном циклическом списке, только проход возможен в любом из двух направлений: с использованием атрибута связи next(т.е. “вперед”) или с использованием атрибута связиprev(т.е. “назад”).
Двусвязные циклические списки, как и односвязные, можно использовать для реализации разнообразных линейных структур.