4.4. Двох зв'язаний список - кільце

Кільцем називається впорядкована динамічна структура, кожний елемент якої містить два посилання: на наступний і на попередній елементи. Оскільки у кільця немає кінця, то в структуру кільця вводиться один головний фіктивний елемент, з якого починається кільце.

first
		chr(0)

Фиктивный элемент кольца Три элемента кольца связаны

Наявність головного фіктивного елемента позбавляє від необхідності спеціально перевіряти, чи знаходиться елемент кільця, що видаляється, на початку або чи потрапляє запис, що туди додається.

Примітка. Двох зв'язані списки є найгнучкішою і мобільною структурою даних, що дозволяє організовувати проглядання елементів списку в двох напрямах. Цим можна пояснити ефективність їх використовування при організації сортувань великих масивів даних змінної розмірності.

Приклад 3. Сформувати двох зв'язаний список, що містить в інформаційній частині змінні типу string .

Визначимо динамічний запис типу s з полями, що містять два покажчики: uvp (ВПЕРЕД - по годинній стрілки) і unz (НАЗАД - проти годинникової стрілки), а також інформаційне поле fio.

Програма створення елементів списку у вигляді КІЛЬЦЯ з включенням, видаленням і виводом його інформаційної частини на екран в алфавітному і в зворотно-алфавітному порядку приведена нижче:

Program p6; {Створення, друк і вивід елементів КІЛЬЦЯ}

type ptr = ^ s;

s = record

uvp, unz : ptr;

fio : string[14]

end;

const ex:boolean=false;

var first,sl,rab:ptr; ch:char;

{--------------------------------------------------------------}

function menu : char;

var a : char;

begin

writeln(' МЕНЮ :');

writeln('F1 - Введення елемента кільця');

writeln('F2 - Видалення елемента кільця ');

writeln('F3 - Вивід елементів кільця в алфавітному порядку');

writeln('F4 - Вивід елементів кільця в зворотно-алфавітному порядку');

writeln('F10 - Вихід з програми');

write('Ваш вибір F? =>');

a:=readkey; if a=#0 then a:=ReadKey; menu:=a;

end;

{--------------------------------------------------------------}

procedure In_Posle; {F1 - Введення елемента кільця (після)}

var NewFio:string[14];

begin

write(' Введіть нове FIO: '); read(NewFio);

new(sl);

sl^.fio := NewFio;

rab := first^.uvp;

while (rab<>first) and (rab^.fio<NewFio) do rab:=rab^.uvp;

sl^.uvp := rab; sl^.unz := rab^.unz;

rab^.unz^.uvp := sl;

rab^.unz:=sl; readln;

end;

procedure Delete; {F2- Видалення елемента кільця }

var DelFio:string[14];

begin

write(' Введіть FIO, що видаляється: '); read(DelFio); readln;

rab :=first^.uvp;

while(rab<>first) and (rab^.fio<>DelFio) do rab:=rab^.uvp;

if rab<>first then

begin

rab^.uvp^.unz := rab^.unz;

rab^.unz^.uvp := rab^.uvp

end

end;

{--------------------------------------------------------------}

procedure Pr_Alf_Spiska; {F3- Вивід елементів кільця в алфавітному порядку }

begin

writeln(' Елементи кільця в алфавітному порядку.');

rab := first^.uvp;

while rab<>first do

begin writeln(' ':40,rab^.fio); rab:=rab^.uvp end;

readkey;

end;

{--------------------------------------------------------------}

procedure Pr_noAlf_Spiska; {F4- Елементи кільця в зворотно-алфавітному порядку }

begin

writeln('Елементи кільця в зворотно-алфавітному порядку');

rab := first^.unz;

while rab<>first do

begin writeln(' ':40,rab^.fio); rab:=rab^.unz end;

readkey;

end;

{--------------------------------------------------------------}

Begin

new(first); { Створення і наповнення головного }

first^.uvp := first; { фіктивного елемента, з якого}

first^.unz := first; { починається кільце}

first^.fio := chr(0); { }

repeat

case menu of

{F1} #59 : In_Posle;

{F2} #60 : Delete;

{F3} #61 : Pr_Alf_Spiska;

{F4} #62 : Pr_noAlf_Spiska;

{F10} #68 : ex:=true;

end

until ex

End.

Завдання: Для самоконтролю засвоєння розглянутого матеріалу промальовуйте зміну значень елементів кільця і змінних: first, sl і rab