Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Кольцевые списки

Если значение указателя последнего звена линейного одно— связного списка заменить с п i 1 (или NULL) на адрес ведущего звена, то линейный список превратится в односвязный кольцевой сПисоК.

Для двусвязного списка, кроме того, нужно заменить с п i 1 на адрес последнего звена значение второго указателя в ведущем звене. Получится двусвязный кольцевой (циклический) список.
В односвязном кольцевом списке можно переходить от по— следнего звена к заглавному, а в двусвязном — еще и от заглавно— го к последнему.
Односвязный кольцевой список выглядит так:

^U nii
next
data next
data

next
data

next

Рис. 9.4 — Кольцевой односвязный список

103

Кольцевой список, как и линейный, идентифицируется как единый программный объект указателем, например L 1, значени- ем которого является адрес заглавного звена.
Возможен другой вариант организации кольцевого списка:

nil
U
data
data data

next
next next
next

Рис. 9.5 — Кольцевой односвязный список. Второй вариант

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

Рассмотрим операции с кольцевыми списками.
Отсутствие «последнего» звена приводит к ещё большему упрощению операций добавления и удаления, по сравнению с одно- и двусвязным линейным списком. Например, для одно- связного кольцевого списка в процедуре удаления отсутствует оператор if проверка на существование звена, следующего за заданным (в кольцевом списке такое звено всегда есть). Такие же операторы aшcyшcmsyюm в процедурах добавления и удаления звеньев для двусвязного кольцевого списка.
При циклической обработке кольцевого списка нужно учесть, что формально последнего звена нет.
Процедуры и программа работы с двусвязным кольцевым
списком на языке Паскаль.

Type
rel2 = ’elem2; elem2 = record next: rell; prev: rel2;

104

data: aHXMbIX QaHHbIX>
end;
list2 = rel2;

procedure insert2(pred: rel2; info: ); var

q: rel2; begin
new(q); (* CosQaHUe HOBOLO 3BeHa *)
q’.data := info; q’.next := pred’.next;
q’.prev := pred’.next’.prev; pred’.next.prev := q; pred’.next := q
end;

]3H BCTiIBKé B H£tUl1JIO CHHCKII (HOCJIé 3iIrJIIIBHOFO 3BéHa) HymHo

yxasilTh B KllUéCTBe apryMeHTa p r od appec sarJIiIBHOFO 3BéHiI, TO
écTs yKasIITéJIh HU Cn COK L 2.

procedure delete2(del: rel2); begin

del’.next’.prev := del’.prev; del’.prev’.next := del’.next; dispose(del);
end;

function search2(list: rel2; info: ; var point: rel2) : boolean;

var
p, q: rel2; b: boolean; begin
b false; point := nil; p list:
q := p’.next;
while (p <> q) and (not b) do begin
if q’.data = info then
105
begin
b true; point q
end;
q := q’.next end;
search2 b
end;
var
12: list2; r: rel2;
begin (* Ć oзQaHxe зaгxaBHO*O 3BeHa *)
пew(r);
r’.next := r;
r’.pred := r;
12 r;
end.

TИП Д£tHHЬIX ДПЯ KOJIьIłëBOFo дBycBяЗHOFo CHHCKil TiIKOÎÎ Wë ,

кIIK H QЛя дBycBяЗHOГO ПHHëЙHOГO. To Жe CIIMOë CП]ЭlIBëДПHBO ДЛЯ
OДHOGBIIЗHbIX CПHCKOB. JfÕ M H ñf 38ëнa CПHCKa нeльзя cyдHTb O eгo
apxиmeкmype, мoжнo moлькo o чиcлe cвязeй.
Qo6IIBЛëHHë ЗBëHlI B П]3OHЗBOльHyю пo3HL[HIO 311 BeдyщHM ЗBë-
HOM.

void Insert2(Link2* Pred, Link2* Loc = new Link2;	int //	data) 1
Loc->data data;	//	2
106

Loc—>next Pred— >next;	//	3
Loc->prev Pred;	//	4
Pred->next Loc;	//	5
Loc->next->prev Loc;	//	6

QOJIéHHé 3BéHiI H3 JIIO6oFO MéCTlI CnHCKlI 3iI BepyulriM 3BéHOM.

void Delete2(Link2* Del)

Del->prev->next	=	Del->next;	//	1
Del->next->prev	=	Del->prev;	//	2
delete Del;			//	3

Key)
int Search2(Link2* Start, Link2*& Find, int

Link2* Cur = Start->next; int Success = 0;
while (Cur != Start && !Success) if (Cur->data == Key)
Find = Cur; Success = 1: break:

Cur = Cur->next;

return Success;

]3éK]3III1JéHHé HoucKII B cayuae Heypauri n]3OHCXOQHT H]3H QOC-