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

УІ И

Мал. 10

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

Тепер запишемо удосконалену процедуру запису в чергу:

procedure write_to_queue; begin

if (j = i) and (<«хвіст» передує «голові» > ) then writeln('Queue is full') else begin

readln(a[j]); if j = n then begin

| j := 1; <«хвіст» передує «голові»> end else inc(j); end end;

68

Аналогічно можна поставити запитання і щодо «голови» черги, коли вона досягне останнього елемента масиву. Якщо «хвіст» не збігається з початком масиву, тобто там ще є місце для нашої черги, то чому б не почати відлік «голови» з початку масиву. Тобто якщо і > п, то потрібно виконати операцію і:- 1.

Удосконалимо і процедуру читання з черги:

procedure read_from_queue; begin

if (i = j) and (<«голова» передує «хвосту»>) then writeln ('Queue is empty') else begin

writeln(a[i]); if i = П then begin

| i := 1; <«голова» передує «хвосту»> end else inc(i); end end;

Ми можемо сказати, що удосконалюючи алгоритм обробки елементів черги, зробили її кільцевою.

Процедуру перегляду елементів черги можна записати в та­кому вигляді:

procedure printqueue; var k: word; begin

if <«голова» передує «хвосту» > then

for k := i to j - 1 do write(a[k],'') else begin

for k := i to n do write(a[k],''); for k := 1 to j - 1 do write(a[k],''); end; writeln end;

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

69

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

1. Яка структура даних називається чергою?

2. Як структура даних «чєрга» відображається на пам'ять ком-п'ютера?

3. Який елемент називають «головою» черги?

4. Який елемент називають «хвостом» черги?

5. Як відбувається читання елементів черги? Запишіть алгоритм читання елемента з черги.

6. Як відбувається запис елементів у чергу? Запишіть алгоритм за-пису елемента в чергу.

7. Яким чином організовано ефективну обробку елементів черги?

8. Зобразіть схематично роботу з елементами черги.

9. Запишіть процедуру запису елемента в чергу.

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

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

12. Який принцип доступу здійснюється до значень елементів черги при їх обробці? Обґрунтуйте свою відповідь.

Завдання

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

1. записати елемент у чергу;

2. прочитати елемент із черги;

3. показати вміст черги;

4. показати вміст масиву;

5. завершити роботу з чергою.

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

• заповнити повністю чергу;

• спорожнити чергу;

• заповнити чергу до половини;

• вичитати один елемент;

• записати два елементи;

• вичитати два елементи;

• записати чотири елементи;

• спробувати записати п'ятий елемент;

• вичитати шість елементів;

• спробувати прочитати сьомий елемент.

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

ДЕК

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

70

Англійською мовою дек - deque, що походить від double-ended queue, тобто дослівно «черга з двома кінцями».

Так само як і для стека та черги, основою організації дека вважатимемо одновимірний масив.

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

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

Оскільки ми фактично маемо двосторонню чергу, то кіль-цевий запис і читання буде відбуватися не лише з кінця масиву в початок, а й із початку в кінець (мал. 11).

_LL

J±

Мал. 11

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

Алгоритм читання справа буде виглядати так:

Dj:=j-1; 2) х := а,.

Тобто спочатку зменшуємо індекс «хвоста» черги на 1, а по-тім елементу х присвоюємо значения елемента масиву з індек-сом /.

Алгоритм запису зліва буде мати такий вигляд:

1)і:=і-1; 2)а,:-х.

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

Реалізація наведених вище алгоритмів мовою програмуван-ня Pascal може бути такою:

procedure readfrom dequejitgh; begin

if (j = i) and (<«голова» передує «хвосту»>) then writeln ('Deque is empty') else '

begin I dec(j);

71

end;

ifj = 0 then begin

| j := n; <«голова» передує «хвосту»> end; writeln (a[j]); end

procedure write_to_deque_left; begin

if (i = j) and (<«хвіст» передує «голові»>) then writeln('Deque is full') else begin dec(i); ifi = 0 then begin

I i := n; охвіст» передує «голові»> end; readln(a[i]); end end;

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

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

/-

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

1. Яка структура даних називається деком?

2. Зобразіть схематично роботу з елементами дека.

3. За яким алгоритмом відбувається читання елемента дека зліва?

4. За яким алгоритмом відбувається читання елемента дека справа?

5. За яким алгоритмом відбувається запис елемента в дек зліва?

6. За яким алгоритмом відбувається запис елемента в дек справа?

7. Запишіть процедуру читання елемента дека зліва.

72

18. Запишіть процедуру читання елемента дека справа. 9. Запишіть процедуру запису елемента в дек зліва. 10. Запишіть процедуру запису елемента в дек справа. И.Який принцип доступу здійснюється до значень елементів структури даних «дек»? Обґрунтуйте свою відповідь. 12. Якими вважаються структури даних «стек», «черга» та «дек»? Обґрунтуйте свою відповідь.

Завдання

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

1) записати зліва елемент у дек;

2) записати справа елемент у дек;

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

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

5) показати вміст дека;

6) показати вміст масиву;

7) завершити роботу з деком.

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

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

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

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

• спорожнити дек, читаючи елементи справа;

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

• вичитати один елемент зліва;

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

• записати два елементи зліва;

• записати два елементи справа;

- заповнити дек і спробувати записати ще один, сьомий, еле­ мент;

• вичитати шість елементів;

• спробувати прочитати сьомий елемент.

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

ЗВ'ЯЗНИЙ СПИСОК

Інколи виникає потреба у доступі до елементів структури, які не є останніми. Така структура існує, і називається вона зв'язним списком.

Перш ніж дати означения структури даних «список», розгля-немо принцип виконання основних операцій над ЇЇ елементами.

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

7 3

i так само читати елементи в будь-якому місці. Реально в дано-му випадку відбуватиметься вилучення цих елементів зі спис­ку, але за традицією будемо надалі продовжувати називати цю операцію читанням.

Читання елемента списку можна організувати шляхом зсу-ву вліво решти елементів, які розташовані за тим, що читаєть-ся. Однак ці дії характеризуються певним часом виконання. Ефективнішим буде шлях «небачення» цього елемента в спис­ку. Тобто якщо після (ft - 1)-го елемента в списку йшов ft-й, а після нього - (ft + 1)-й, то після вилучення ft-ro елемента за (ft - 1)-им буде слідувати (ft + 1)-й. Схематично це можна зобра-зити так (мал. 12):

(ft - 1) елемент —> ft елемент —► (ft + 1) елемент|

Мал. 12

Запис нового елемента списку в указане місце (наприклад, після ft-ro елемента) викликатиме зсув усіх елементів, що зна-ходяться після ft-ro, на одну позицію вправо. Зрозуміло, що і такий підхід не є оптимальним. Простіше було б записати його в кінець списку, але змінити послідовність перегляду елемен-тів списку: після ft-ro елемента переходити до нового елемента, записаного в кінець, а потім до (ft + 1)-го. Зобразимо схематич­но цю операцію (мал. 13):

Структуру «список» можна реалізувати на одновимірному масиві. Кожний елемент списку буде займати два сусідні еле­менти масиву, тобто таку ланку: перший - сам елемент списку, другий - індекс масиву, що вказує на місце знаходження на-ступного елемента списку (мал. 14):

»,

а,+ 1

74

Мал. 14

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

Наведемо приклад заміни слова «школа» на слово «кома». Спочатку занесено у список слово «школа» (мал. 15).

а, а_г а₃ а₄ а₅ а_в а₇ а₈ а_д а₁₀ а„ а₁₂ а₁₃

Мал. 15

Тепер вилучимо, тобто прочитаємо, зі списку перший (ш) і четвертий (л) елементи (мал. 16).

а, а₂ а₃ а₄ а₅ а₆ а₇ а₈ а₉ а₁₀ а,, а₁₂ а₁₃

Мал. 16

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

Тепер вставимо, тобто запишемо, в список після елемента «о» новий елемент «м» і отримаємо слово «кома» (мал. 17).

^Q! ^а2 «3 °4 ^а5 °6 ^а7 °8 S «10 °П °12 °13 «14 °15

Мал. 17

Неважно тепер записати алгоритми читання і запису еле-ментів у структурі даних «список» при відображенні и на одно-вимірний масив.

Операція читання виглядатиме так:

&&*г -~ ^а2к*4-

75

Запис нового елемента у список після ft-ro елемента можна подати такою послідовністю дій:

Da :=х;

³)^а21е2^:_а2-