Якщо елементи списку мають два вказівних поля, але список не лінійних, а розгалужений, то отримується список у вигляді бінарного дерева.

Тема: Лінійні однонапрямлені списки.

Такі списки складаються з елементів, які є комбінацією двох полів: інформаційного та вказівного на наступний елемент.

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

TYPE

list1=^el_list1;

el_list1=record

inf:integer;

Next:list1

END;

В програмі доступ до таких однонапрямлених змінних здійснюється через фіксований вказівник – статичну змінну. Ця змінна не може змінювати свого значення, оскільки може призвести до втрати адреси всього списку. Останній елемент списку вказує в nil.

Формування списку здійснюється при допомозі процедур створення динамічних змінних, при цьому кожний новий елемент зв’язується вказівником з попереднім елементом або своїм вказівником із наступним. Формування списку може здійснюватися за двома принципами:

Стек.

Черга.

При формуванні списку за правилом стеку: кожен новий елемент ставиться у список в якості голови.

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

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

Традиційно, над лінійними списками виконують наступні дії:

Формування.

Перегляд.

Пошук елемента за вказаним інформаційним полем.

Вставка нового елемента після деякого елемента із вказаним значенням.

Вставка елемента перед деяким елементом.

Видалення елемента із вказаним значенням.

Формування однонапрямленого списку.

Для реалізації операції в програмі достатньо мати 4 статичні змінні.

а). Стек.

VAR

first, last,p,q:list1;

o:string;

n,i,a,k:integer;

BEGIN

writeln('введіть кількість елементів у списку');

readln(n);

for i:=1 to n do

Begin

new(p);

writeln('введіть елемент списку');

readln(a);

p^.inf:=a;

p^.next:=first;

first:=p

end;

б). Черга.

writeln('введіть кількість елементів у списку');

readln(n);

first:=nil;

last:=nil;

new(p);

writeln('введіть елемент списку');

readln(a);

p^.inf:=a;

last:=p;

first:=p;

for i:=2 to n do

Begin

new(p);

writeln('введіть наступний елемент списку');

readln(a);

p^.inf:=a;

last^.next:=p;

last:=p

end;

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

Перегляд всього списку. Перегляд списку передбачає рух від голови списку до кінця.

PROCEDURE RESIV (first,p:list1);

BEGIN

p:=first;

while p<>nil do

Begin

write(p^.inf,',');

p:=p^.next

end;

Writeln

END;

Пошук за вказаним інформаційним полем.

writeln('введіть шуканий елемент');

readln(a);

while (p<>nil) do

Begin

if p^.inf=a then

Begin

writeln ('під номером № ‘,k+1);

i:=i+1;

end;

p:=p^.next;

k:=k+1

end;

if k=0 then writeln ('немає')

Else writeln ('кількість ',i)

Вставка нового елементу після деякого елементу.

p:=first;

writeln ('введіть елемент, після якого потрібно вставити новий');

readln(k);

while p<>nil do

Begin

if p^.inf=k then

Begin

new(q);

writeln('введіть елемент, який потрібно вставити');

readln(a);

q^.inf:=a;

q^.next:=p^.next;

p^.next:=q

end;

p:=p^.next

end;

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

writeln ('введіть елемент, перед яким потрібно вставити новий');

readln(k);

p:=first;

if p=nil then writeln ('список пустий')

Else

if p^.inf=k then {вставка перед першим}

Begin

new(q);

writeln ('введіть елемент, який потрібно вставити');

readln(a);

q^.inf:=a;

q^.next:=p;

first:=q

End

Else

Begin

while (p^.next<>nil) and (p^.next^.inf<>k) do

p:=p^.next;

if p^.next=nil then writeln ('немає такого елементу ')

Else

Begin

new(q);

writeln('введіть елемент, який потрібно вставити');

readln(a);

q^.inf:=a;

q^.next:=p^.next;

p^.next:=q

End

end;

Видалення. Для видалення елементу із вказаним інформаційним плем потрібно знову ж як і для вставки перед мати вказівник на попередній елемент, тому операція видалення матиме декілька варіантів: пустий список, видаляється перший елемент, відсутність у списку шуканого елементу, шуканий елемент довільний, крім першого.

writeln('введіть елемент, який потрібно вилучити');

readln(a);

p:=first;

if p=nil then writeln ('список пустий')

Else

if p^.inf=a then

Begin

first:=p^.next;

Dispose(p)

End

Else

Begin

while (p^.next<>nil) and (p^.next^.inf<>a) do

p:=p^.next;

if p^.next=nil then writeln ('такого елементу немає')

Else

Begin

q:=p^.next;

p^.next:=q^.next;

Dispose(q)

End

end;

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

У двонапрямлених списках і в розглянутих раніше однонапрямлених елементи утворюють лінійну структуру даних з послідовним доступом, але на відміну від них, рух по списку можливий у двох напрямках, тому кожен елемент міститиме, окрім інформаційного поля, два вказівні поля: на наступний і попередній елементи. Список матиме два фіксованих вказівники: на перший – first; на останній – last.

Оскільки рух по списку можливий у двох напрямках, то переміщення від first до last здійснюється через вказівник next; від last до first через вказівник prev, тому формування списку за правилом стеку від first до last – це та ж сама черга від last до first і навпаки.Як і в однонапрямлених списках над двонапрямленими виконують ті ж самі операції.

Оголошення структури списку може мати вигляд:

TYPE

list2=^el_list2;

el_list2=record

inf:integer;

Next,prev:list2

END;

1. Формування списку.

writeln('введіть кількість елементів у списку');

readln(n);

first:=nil;

last:=nil;

for i:=1 to n do

Begin

writeln('введіть елемент');

readln(a);

new(p);

p^.inf:=a;

if last=nil then last:=p;

p^.next:=first;

first^.prev:=p;

first:=p

end;

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

 

PROCEDURE RESIV;

BEGIN

p:=first;

while p^.next<>nil do

Begin

write(p^.inf,' ');

p:=p^.next

end;

writeln(p^.inf,' ')

END;

Пошук.

p:=first;

writeln('введіть шуканий елемент');

readln(a);

i:=0;

while (p<>nil) do

Begin

inc(k);

if p^.inf=a then

Begin

i:=i+1;

Writeln('під № ',k)

end;

p:=p^.next

end;

if i=0 then writeln ('немає')

Else writeln ('кількість ',i)

Вставка перед на відмінну від однонапрямленого списку аналогічна вставці після з точністю переміни вказівників prev і next.

write('введіть елемент, після якого потрібно вставити новий');

readln(n);

write('введіть новий елемент');

readln(a);

p:=first;

while p<>nil do

Begin

if p^.inf=n then

Begin

new(q);

q^.next:=p^.next;

p^.next:=q;

q^.prev:=p

end;

q^.inf:=a;

p:=p^.next

end;

 

Вилучення. Як і в попередніх випадках видалення елементу не потребує складного пошуку із порівнянням через один елемент, як у однонапрямлених списках.

write('введіть елемент, який потрібно вилучити');

readln(a);

p:=first;

while p<>nil do

Begin

if p^.inf=a then

Begin

if p=first then

Begin

first:=p^.next;

p^.prev:=nil

End

Else

Begin

if p^.next<>nil then

Begin

p^.next^.prev:=p^.prev;

p^.prev^.next:=p^.next^.next

End

Else

Begin

p^.prev^.next:=nil

end;

end;

End

Else

p^.prev^.next:=p;

p:=p^.next

end;

Тема: Бінарні дерева.

Особливим видом розгалужених списків є дерева. Особливістю таких динамічних структур даних є те, що кожен елемент має декілька вказівних полів (бінарні, тернарне, п-арні дерева).

На відмінну від двонапрямлених списків, дерева не мають лінійної структури. Підлеглість елементів має розгалужену структуру – це означає, що такі списки мають один верхній елемент – голову. Він має декілька підлеглих елементів, які в свою чергу мають декілька елементів, причому на будь-якому рівні всі вказівники повинні бути зв’язані з іншими елементами, якщо ж ні, то в таких випадках вони вказують в nil.

Доступ до елементів дерева здійснюється послідовно з вершини дерева через фіксований вказівник top. Елементи дерева, обидва вказівники яких зв’язані із підлеглими елементами, називають вузловими вершинами або гілками. Елементи дерева, обидва вказівники яких вільні, називаються листками або висячими вершинами. Елементи дерева, один з вказівників яких вільний, називаються напівисячими вершинами.

Шириною бінарного дерева називається кількість вузлів від крайнього лівого до крайнього правого елементу. Висотою бінарного дерева називається максимальна кількість рівнів елементів від вершини дерева до найдальшого листка.