Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

4)a₂:=a₂ + 2.

Однак ефективнішим для реалізації списку є використання покажчиків (мал. 18), а саме: розташування списку в дина-мічній пам'яті, а не в статичному масиві.

Отже, тепер можемо дати означения структури даних «спи­сок».

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

Опишемо структуру даних «список». Про список можна сказати так: кожен його елемент представлений значениям і покажчиком на наступний елемент, який представлений зна­чениям та покажчиком на наступний для нього елемент і т. д. Тобто явним чином проглядається рекурсивний опис цієї структури: будь-який наступний елемент є таким, як і той, що на нього посилається. Специфічними є лише початок і кінець списку. Початком списку є покажчик на його перший елемент, а кінцем — покажчик у «нікуди», тобто значения покажчика повинно бути nil.

Введемо власний тип «список»:

type list = "tlist; tlist = record

data: <тип>; next: list end;

Перш ніж організовувати роботу з елементами списку, його треба створити. Створення списку - це запис початкової послі-довності елементів. Може існувати декілька способів створення списку. Основна ідея полягає в тому, щоб кожного разу допису-вати в кінець поточного списку новий елемент.

Розглянемо рекурсивну функцію, яка за відомим значениям п заповнює список, таким чином створюючи його:

76

function create_list(n: integer): var q: list;

x: integer; begin

if n = 0 then q := nil else begin writelnCInput data:'); read (x): new (q); with q" do begin

I data := x; next := create list (n - 1); end; end; createlist := q; end;

Звернення до функції створення списку в основній програмі може бути таким:

а := createjist (n).

Ще одним варіантом створення списку може бути викорис-тання такої процедури:

procedure createjist (var х: list); begin

new (x\next);

x := x'.next;

write('lnput data:');

readln (x\data); end;

Наведемо деякі пояснения щодо роботи даної процедури. Послідовність дій виглядає так.

1) Процедура new(x'.next) визначає адресу в динамічній пам'яті, за якою далі записуватиметься значения нового еле- мента.

2) Далі здійснюється перехід до цього наступного елемента, що розташований на новою адресою:

х := x'.next;.

3) Новий елемент, що знаходитиметься за адресою x'.next, стає останнім, тобто в нього записуеться значения: read(x'.data);.

Використати процедуру createlist для створення списку можна, організувавши цикл:

new (а); {Визначення адреси «голови» списку.)

{Коліювання адреси «голови» списку} х := а; {в змінну х для подальше? роботи з нею.}

77

writef Input data: '); (Введения значения першого елемента списку.}

readln (x\data);

{Введения решти елементів списку за допомогою}

for і := 1 to n - 1 do {передавання у процедуру створення поточно!}

createjist (х); {адреси останнього елемента списку.}

x'.next := nil; {Визначення для останнього елемента ознаки кінця списку.}

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

- функція вимагає використання додаткової стекової пам'я- ті, але може створювати порожній список, якщо п = 0;

- процедура не вимагає додаткової стекової пам'яті, але передбачає на початку введения хоча б одного елемента списку.

Можна сказати, що кожний із цих варіантів мае право на існування.

Тепер варто розглянути процедуру перегляду елементів створеного списку. Для цього можна запропонувати таку про­цедуру:

procedure show (х: list); begin

while х О nil do begin

write(x".data,''); x := x'.next end end;

Пояснимо деякі окремі фрагменти наведено! процедури.

Цикл while x О nil do дає можливість «пробігти» всі еле-менти списку, які вже в ньому є. Цей перебіг елементами спис­ку досягається виконанням у циклі оператора х := x'.next. Тобто у змінну х, що мае містити адресу розміщення в пам'яті на-ступного елемента списку, пересилається адреса, записана у полі next даного елемента списку, що якраз і вказує на нього. Завершуеться цикл тоді, коли значениям х стае nil, тобто по-точний елемент списку є кінцевим.

Зауважимо, що для захисту попередньої та всіх наступних процедур, які працюють зі списком, варто передбачити пере-вірку наявності у списку елементів. Для цього можна додати в основну програму оператор

if а = nil then writeln ('Список порожній. ДіТ з ним неможливі');

Розглянемо процедуру читання (вилучення) елемента зі списку.

78

Може бути кілька варіантів читання елемента списку: чи­таемо вказаний елемент або читаемо елемент, розміщений піс-ля вказаного. Перш за все у будь-якому з цих варіантів треба спочатку проглянути список до заданого елемента. Подібний цикл ми вже використовували раніше.

Тепер послідовність перегляду елементів списку виглядати-ме так (мал. 20):

Як вилучити елемент, що знаходиться після заданого? Для цього треба лише значения покажчика цього наступного еле­мента скопіювати на місце покажчика заданого елемента (мал. 19):

Запишемо процедуру читання елемента списку, що знахо­диться після заданого елемента зі значениям I:

procedure deleteafter (х: list); var I: integer; begin

writef Delete after what? ');

read (I);

while x".data <> I do x := x'.next;

xⁿ.next := x".next".next end;

Для читання самого елемента зі значениям I спочатку треба переглянути список для його знаходження. В попередній на-веденій процедурі ми зупинялися саме на цьому елементі, але вилучали наступний. А як вилучити той елемент, на якому зу-пинилися? Давайте міркувати так. «Попередній елемент нам потрібний?» - «Так». - «Поточний елемент нам потрібний?» -«Hi». - «Наступний елемент нам потрібний?» - «Так». Тож да­вайте на місце поточного елемента скопіюємо всю інформацію про наступний елемент: його значения і значения покажчика на елемент, що слідує за ним. Схематично це виглядатиме так (мал. 21):

79

А тепер реалізація запропонованого алгоритму мовою Pascal:

procedure delete (х: list); var I: integer; begin

writeCDeletewhat?'); read (I);

while x'.data <> I do x := x'.next; x'.data := x".next\data; x\next := x*.next".next; end;

Мае право на існування ще одна версія алгоритму читання зі списку заданого елемента. Вона побудована на попередній про­цедур! читання наступного за задании елементом deleteafter. її смисл полягає в тому, що при перегляді списку будемо диви-тися не на поточний елемент, а на той, що слідує за ним:

while х".next".data ОI do x := x\next;

Зрозуміло, що ми зупинимося в списку на елементі, який пе­редув шуканому. Тепер процедура delete_after вилучить зі списку саме той елемент, що нам потрібний.

Розглянемо різноманітні операції запису або вставления елементів у список.

Першою розглянемо операцію запису в список елемента зі значениям I після елемента зі значениям k.

Прокоментуємо послідовність виконання операцій при за-писі нового елемента I після заданого елемента k (мал. 22). Пер­шим кроком треба визначити адресу х елемента k. Другим -

80

визначити адресу q для розміщення в пам'яті нового елемента I. Третім - скопіювати в поле next нового елемента значения по-кажчика, що записане в полі next за адресою х. Четвертям - за­писати значения I в поле data за адресою q. П'ятим - записати в поле next за адресою х значения адреси q. Запишемо текст процедури, що виконує ці операції:

procedure insert_after (x: list); var I, k: integer; begin

write('Input what:');

read (I);

write('lnput after? ');

read (k);

while x".data <> k do x := X^я.next; new (q);

q'.next := x'.next; q'.data := I;

x\next := q; end;

Запис нового елемента / перед задании елементом k вико-нується такою послідовністю дій. Спочатку знаходимо шуканий елемент k у списку. Потім визначаємо в пам'яті адресу q для но­вого елемента списку. Оскільки ми «бачимо» лише наступний, а не попередній елемент списку, то можна вдатися до таких хит-рощів. Відомо, що в результаті запису за попереднім елементом повинен іти иовий елемент, а потім елемент зі значениям k. То­му на місце нового елемента перепишемо значения елемента k i значения покажчика на наступний за ним елемент, а на звіль-нене місце - значения нового елемента I в його поле next - зна­чения адреси q. Схематично це виглядатиме так (мал. 23):

q'.data

х

Мал. 23

Наведемо текст процедури, що виконує описані операції:

procedure insert_previous (x: list); var I, k: integer; begin

| write('lnputwhat:');

81

read (I);

write('Input previous? ');

read (k);

while x^A.data о к do x := x^A.next;

new(q); q* := xⁿ;

x'.data := I; x'.next := q; end;

Ми розглянули односпрямований список, тобто список, кожен елемент якого мае покажчик лише на наступний еле-мент. Існує і двоспрямований список, тобто такий, кожний елемент якого мае два покажчики: на наступний і попередній елементи списку. Список може бути і кільцевим. Для одно-спрямованого кільцевого списку останній елемент мае покаж­чик на перший або перший елемент - на останній. Для двоспря-мованого списку обидві властивості присутні одночасно.

Тепер можемо зробити логічний висновок щодо доступу до елементів структури даних «список». Це структура послідов-ного доступу, оскільки дістатися будь-якого елемента списку не можна інакше, ніж переглянувши всі елементи, що йому передують, починаючи з першого, тобто з «голови» списку. Однак ця структура значно відрізняється від попередніх — сте­ка, черги та дека, оскільки дає можливість читання та запису елементів у будь-яке місце заданої послідовності.

/ Запитання для самоконтролю

1. Який принцип організаціі структури даних «зв'язний список»?

2. Зобразіть схематично операцію читання елемента зв'язного списку.

3. Зобразіть схематично операцію запису елемента зв'язного списку.

4. Як представляеться елемент списку?

5. Запишіть алгоритм читання елемента списку.

6. Запишіть алгоритм запису нового елемента в список.

7. Обґрунтуйте ефективність використання покажчиків для орга-нізації зв'язного списку.

8. Дайте означения структури даних «зв'язний список» у термінах використання покажчиків.

9. Наведіть два способи створення списку. Поясніть відмінність між ними та обґрунтуйте доцільність іх використання в кожній кон­кретно ситуації.

10. Запишіть текст процедури перегляду елементів списку.

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

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

82

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

цієї операції та запишіть відповідну процедуру. 14. Зобразіть схему запису нового елемента списку перед вказаним елементом з використанням покажчиків, поясніть ідею виконан­ня цієі операції та запишіть відповідну процедуру. 15. Поясніть принцип організації односпрямованого, двоспрямова-ного та кільцевого списків. 16. Який принцип доступу здійснюється до елементів зв'язного списку при Іх обробці? Обґрунтуйте свою відповідь.

Завдання

1. Розробити діалогову меню-орієнтовану програму роботи з елементами зв'язного списку за такими пунктами:

1. записати новий елемент у список після вказаного елемента;

2. записати новий елемент у список перед вказаним елемен­том;

3. прочитати заданий елемент зі списку;

4. прочитати елемент зі списку після вказаного;

5. прочитати елемент зі списку перед вказаним;

6. показати вміст зв'язного списку;

7. завершити роботу зі зв'язним списком.

2. Протестувати програму завдання 1, спостерігаючи за вміс- том зв'язного списку, за такою схемою:

• створити список;

• записати новий елемент після вказаного елемента в сере­дину списку;

• записати новий елемент перед вказаним елементом у сере­дину списку;

• записати новий елемент у початок списку;

• записати новий елемент у кінець списку;

• прочитати заданий елемент із середини списку;

• прочитати елемент із середини списку після вказаного;

• прочитати елемент із середини списку перед вказаним;

• прочитати перший елемент зі списку;

• прочитати останній елемент зі списку;

• прочитати всі елементи зі списку;

• прочитати відсутній елемент списку.

3. Зробити письмовий аналіз виконання завдань 1,2.

Дерево. Бінарне дерево

Якщо у списку кожний елемент мае покажчик лише на один наступний за ним елемент, то в дереві — на декілька. Таку структуру можна організувати за допомогою покажчиків.

83

_I

Деревом иазивається структура даних, кожнии елемент якої зв'язанин з декількома наступними за ним елементами за допомогою покажчиків.

Схематично дерево, кожнии елемент якого зв'язаний з дво-ма наступними елементами, можна зобразити так (мал. 24):

Розглянемо декілька прикладів представления дерев, де еле­ментами є множима літер.

Мал. 25

1. Вкладені множини (мал. 25):

2. Відступи: А В D

і Е

j к L С

F О

G М N

Н Р.

84

3. Вкладені дужки:

(А (В (D (i), EG,k, L)), С (F (О), G (M, N), H (P)))).

3 наведеними прикладами представления дерев ми досить часто маемо справу. Перший приклад - схематичне представ-лення структури деякого підприємства або організації із зоб-раженням підпорядкування різних підрозділів; другий - ієрар-хічна структура систематизованого запису: план твору, зміст книжки, текст Pascal-програми тощо; третій — математичне представления арифметичного виразу.

Наведемо деякі означения дерева як одного із способів пред­ставления інформації.

Упорядковане дерево - це дерево, в якого ребра, тобто гілки, що виходять з кожної вершини, упорядковані.

Наприклад, два упорядковані дерева на малюнку 26 різні:

Мал. 26

Вершина у, що знаходиться безпосередньо нижче від вер­шини х, називається нащадком х. У деревах, зображених на малюнку 26, вершини В і С е нащадками вершини А. Якщо вер­шина х знаходиться на рівні і, то кажуть, що вершина у зна­ходиться на рівні і + 1. I навпаки, вершину х називають без-посереднім предком у. Вважається, що корінь дерева (найвища вершина) знаходиться на рівні 0. Максимальний рівень деякої з вершин дерева називається його глыбиною або высотою. Якщо елемент не мае нащадків, то його називають термінальною вершиною, або лыстом, а нетермінальну вершину називають внутрішньою. Кількість безпосередніх нащадків внутрішньої вершини називають її степенем. Максимальний степінь усіх вершин дерева називають степенем дерева. Кількість ребер, які треба пройти від кореня дерева до вершини х, називають довжиною шляху до вершини х. Корінь дерева мае шлях 0, його безпосередш нащадки мають довжину шляху 1 і т. д. Вершина на рівні / мае довжину шляху, рівну і. Довжына шляху всього дерева визначаеться як сума довжин шляхів усіх його ком-понентів. ЇЇ також називають довжиною внутрішнього шляху. Наприклад, довжина внутрішнього шляху для дерева, зобра-женого на малюнку 27, дорівнює 36.

Для дерев існує поняття зовнішнього шляху. Для його визна-чення дерево треба доповнити спеціальними вершинами у тих

місцях, де в заданому дереві відсутні піддерева. Додаткові вер­шини добавляються за правилом: усі вершини повинні стати максимального степеня, який дорівнює степеню дерева. Розширене дерево матиме такий вигляд (мал. 27):