program Form2;

type

Link=*LRiad;

LRiad=Record

Elem: Char;

Next: Link;

end;

function SeekElem(Rjad:Link; Elm:char; var Res;Link): Boolean;

var Rb: Link;

begin

SeekElem:=False; Res:=nil;

Rb:=Real^.Next;

while (Res=nil)

and (Rbonil) do

If Rb^.Elem=Elm then

begin

SeekElem:=True;

Res:=Rb;

end

else Rb:=Rb^.next;

end;

begin

end.

Параметрами функції SeekElem є: вказівна змінна Rjad, що вказує на рядок символів; Elm, що містить шуканий елемент -символ; Res – вказівна змінна-результат, вказує на ланку, що містить шуканий елемент; Rb – робоча змінна вказівного типу.

2. Вилучення заданого елемента з рядка. Описуючи цю процедуру, будемо задавати елемент, який треба вилучити, за допомогою вказівки на ту ланку ланцюга, після якої є елемент, що його потрібно вилучити.

Схематично процедуру вилучення зобразимо так. Нехай вихідний ланцюг є (опишемо фрагмент) таким, як показано на рис. 16.

Вилучення елемента В треба організувати так, щоб вказівка з ланки А була на ланку С, оминаючи ланку з елементом В (рис. 17).

Рис. . Фрагмент динамічного рядка

Рис. . Вилучення ланки динамічного рядка

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

program Form3;

type

Link=^LRiad;

LRiad=record

Elem: Char;

Next: Link;

end;

procedure DelElem(Lanka: Link);

var Rb: Link;

begin

Rb:=Lanka^Next;

Lanka^.Next:=Lanka^.Next^.Next;

dlspose(Rb);

end;

begin end.

Знищуємо ланку, що містить шуканий елемент, для економії пам'яті.

3. Вставляння заданого елемента. Заданий елемент у рядок вставлятимемо за вказівкою на ланку, після якої він повинен бути. Нехай початковий динамічний рядок має вигляд, показаний на рис. 16. Після В треба вставити D. Цей випадок схематично зображено на рис. 18.

Рис. . Вставляння ланки в динамічний рядок

Отже, для того, щоб вставити ланку в рядок, треба:

1) створити новий динамічний об'єкт того ж типу, що й кожна ланка ланцюга;

2) у поле .Elem створеної ланки ввести значення елемента, який вставляють;

3) у поле вказівки .next створеної ланки ввести значення вказівки, взяте з поля вказівки ланки, після якої вставляють елемент;

4) у поле вказівки ланки, після якої вставляють елемент, ввести вказівку на новостворену ланку.

Процедура вставляння має такий вигляд:

program Form4;

type Link=^LRiad;

LRiad:=record

Elem: Char;

Next: Link;

end;

procedure lnsElem(Lanka: Link; Elm: Char);

var Rb: Link;

begin new(Rb);

Rb^.Elem=^Elm;

Rb^.Next:=Lanka^.Next;

Lanka^.NextP:=Rb;

end;

begin

end.

2.3. Списки як динамічна структура даних

Розглянуті рядки символів, зображені у вигляді ланцюгів, тобто як динамічна структура, є частковим випадком такої структури – лінійного однонапрямленого списку. Різниця полягає в тому, що коли для рядків інформаційними елементами можуть бути тільки значення типу char, то в загальному випадку списків елементами можуть бути значення довільного типу – як прості, так і складені. Однак з метою уніфікації під час опрацювання списку вважатимемо, що всі елементи є значеннями одного типу.

Схематично однонапрямлений список показаний на рис. 19.

Рис. . Однонапрямлений список

За аналогією з динамічними рядками тут визначено вказівник Sp, який вказує на весь список як на єдину структуру, а також нульову ланку, у якій вказівник вказує на перший елемент.

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

Тому введемо нову динамічну структуру – двонапрямлений список. Для цього в кожній ланці списку додамо ще по одному полю. Значенням цього поля буде вказівник на попередню ланку списку. Оскільки кожна ланка зобраажена як запис, то в цей запис відповідно додамо ще одне поле. Тоді структуру ланки опишемо таким списком типу:

type

TypeElm=Char;

Link^.Lanka;

Lanka=record

Bern: Char;

Next: Link;

Predd: Link;

end;

Така структура схематично зображена на рис. 20.

Рис. . Двонапрямлений список

Як видно з рис. 11.7, у полі Predd нульової ланки, як і в полі Next останньої ланки, вказівник має значення nil, що відповідає ситуації, коли нульова ланка не має попередньої, а остання – наступної.

Варіантом двонапрямлених є кільцеві списки. Їх утворюють на базі двонапрямлених, якщо вказівній змінній у полі Next останньої ланки присвоїти значення вказівника, що вказує на початок, тобто на нульову ланку, а в полі Predd нульової ланки – значення вказівника, що вказує на останню ланку. Тобто одержимо кільцеву структуру (рис. 21).

Рис. . Кільцевий список

Над списками визначені ті ж самі операції, що й над динамічними рядками, тобто пошук елемента в списку, вставляння елемента у визначене місце і вилучення зі списку.

1. Вставляння елемента в список виконують за алгоритмом, що подібний до вставляння символу в рядок. Процедура вставляння має два формальні параметри: перший – елемент, який вставляють, і другий – вказівку на ланку, після якої вставляють елемент:

program Form5;

type

ТуреЕlm:=Char;

Link=^Lanka;

Lanka=record

Elem: Char;

Next: Link;

Predd: Link;

end;

procedure lnList(Elm: TypeElm; LanLst: Link);

var Rb: Link;

begin

New(Rb);

Rb^.Elen:=Elm;

Rb^.NexKanLst:=Next;

Rb^.Predd:=LanLst^.Next^.Predd;

LanLs^.Next.=Rb;

LanLst^.Next^.Predd:=Rb;

end;

begin end.

Тут Elm – елемент, який вставляють, LanLst - вказівник на ланку, після якої виконують вставляння.

2. Вилучення елемента зі списку. Для цього треба змінити вказівку в полі Next попередньої ланки і в полі Predd наступної після тої, яку вилучають. Доцільно ланку, елемент якої вилучають, знищити:

program Form6;

type

TypeElm=Char;

Link=^Lanka;

Lanka=record

Elem: Char;

Next: Link;

Predd; Link;

end;

procedure OutList(LanLst:Link);

begin

LanLs^.Nex^.Predd:=LanLs^.Predd;

LanLst^.Predd^.Next:=LanLst^.Next;

Dispose(LanLst);

end;

begin end.

Тут значення LanLst вказує на ланку, яку вилучають.

3. Шукання елемента списку. Алгоритм шукання елемента в списку аналогічний до шукання в динамічному рядку. Тому для списку теж складемо логічну функцію, побічним ефектом якої є інформація про першу за порядком ланку, яка містить шуканий елемент.

Особливістю використання кільцевих списків є формальна відсутність у них початку і кінця. Це потрібно врахувати під час конструювання функції.

Формальні параметри функції шукання елемента в кільцевому списку такі: List – вказівного типу, що міститиме вказівку на початкову ланку списку (тобто у цьому випадку на нульову ланку, з якої починається шукання); Elm – міститиме значення шуканого елемента; LanLst – вказівного