_TPLab_My_Посібник

Схема видалення «середнього» елемента представлена на Рис.1.

Рисунок 1. Схема видалення елемента з двозв’язаного списку.

Пунктирними лініями зображені вказівники після видалення елемента, а цифрами позначені відповідні оператори процедури Del_Element.

КОНТРОЛЬНІ ЗАПИТАННЯ.

1.Які операції над списком вимагають переміщення ним (перегляду списку)?

2.Чому в двозв’язаному списку базові операції реалізуються ефективніше, ніж в однозв’язаному?

3.Навіщо в процедурі видалення елемента зі списку після переадресації вказівників застосовується процедура Dispose?

4.Приведіть приклади використання двозв’язаних списків в інформатиці/програмуванні.

5.Приведіть приклади використання двозв’язаних списків в математиці.

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ. Завдання 1.

Модифікувати програму опрацювання однозв’язаного списку (лабораторна робота №11), сформувавши двозв’язаний список, та виконати завдання свого варіанту.

Завдання 2.

1.Створити процедуру вставки нового елемента в двозв’язаний список.

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

3.Створити процедуру визначення інформаційної частини (ключа) елемента, заданого своїм порядковим номером (номером позиції) у двозв’язаному списку.

4.Створити процедуру сортування елементів двозв’язаного списку.

5.Використовуючи двозв’язаний список знайти всі менші 100 натуральні числа, квадрати яких є паліндромами. Паліндромом називається число, запис якого читається однаково з початку і з кінця, наприклад: 7, 33, 717, 27572.

111

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

ЛАБОРАТОРНА РОБОТА № 13 Проектування та відлагодження програм опрацювання стеків, деків, черг.

МЕТА РОБОТИ: Навчитись проектувати алгоритми та програми опрацювання абстрактних типів даних –стеків, деків, черг.

ЗАВДАННЯ:

Спроектувати алгоритми та програми розв’язання задач опрацювання стеків, деків, черг за варіантами завдань, номери яких визначає викладач.

МЕТОДИЧНІ ВКАЗІВКИ

1.Перед виконанням роботи необхідно пригадати:

логічну структуру програми на мові Turbo Pascal;

правила опису простих та структурованих типів даних;

правила запису виразів;

синтаксис основних операторів;

синтаксис опису та правила застосування стандартних (бібліотечних) процедур і функцій;

правила розподілу пам'яті при виконанні програми;

правила опису вказівників;

способи ініціалізації вказівників;

способи доступу до змінної за вказівником;

допустимі операції над вказівниками;

процедури та функції керування динамічною пам'яттю;

процедури та функції створення, опрацювання та знищення динамічних змінних;

правила опису та способи організації однозв’язаного списку;

правила та способи реалізації типових операцій над елементамиоднозв’язаного списку

2.Перед виконанням цієї роботи необхідно вивчити:

правила опису та способи організації стеків, деків, черг;

правила та способи реалізації базових операцій над елементами стеків, деків, черг.

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

ВІДОМОСТІ З ТЕОРІЇ.

СТЕК.

Означення 1. Стек (магазин) – це динамічна структура даних (спеціальний вид лінійного списку), в якій операції додання та видалення елементів виконуються тільки на одному кінці, який називається

вершиною стека.

Стек реалізує принцип обслуговування «останнім прийшов – першим обслуговується» (LIFO: Last Input – First Output).

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

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

Push(x, S) – додання нового елемента х у вершину стеку S («заштовхування у стек»);

Pop(S) – вибірка (зчитування) елемента з вершини стеку («виштовхування зі стеку»). Вибраний елемент видаляється зі стеку;

Top(S) – повернення елемента з вершини стеку;

Empty(S) – перевірка чи стек є порожнім;

MakeNull(S) – очистка стеку.

Для вказаних базових операцій над стеком вжиті традиційні назви.

112

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

РЕАЛІЗАЦІЯ СТЕКУ ЗА ДОПОМОГОЮ МАСИВУ.

Стек, як і однозв’язаний список, можна реалізувати як статичну структуру даних за допомогою одномірного масиву. Але приведена в лабораторній роботі №11 реалізація списку за допомогою масиву для представлення стеку є нераціональною, так як кожне виконання операцій Push і Pop вимагатиме переміщення всіх елементів стеку і тому час їх виконання буде пропорційний кількості елементів стеку.

А.Ахо запропонував більш ефективний спосіб реалізації стеку за допомогою масиву, врахувавши, що вставка і видалення елементів стеку здійснюється тільки через вершину стеку [Axo с.59]. За цією схемою фіксується «дно» стеку в комірці з найбільшим індексом і стеку дозволяється «рости» до вершини масиву, тобто до комірки з найменшим індексом. Допоміжна змінна Top (вершина) вказує на поточну позицію першого елемента стеку. Схема такої реалізації стеку приведена на Рис.1.

Рисунок 1. Схема реалізації стеку за допомогою масиву.

На приведеній схемі останній (за індексом) елемент масиву знаходиться у хвості стеку, тобто є

…

MaxLength останній елемент

першим доданим у стек елементом. Перший (за індексом) елемент масиву знаходиться у вершині стеку, тобто є останнім доданим у стек елементом.

Для такої реалізації стеку можна описати абстрактний тип даних TStack наступним чином: Const maxlength = 100;

Type TInfo = <ім’я_типу> { тип елементів стеку } TStack = Record

Info: Array [1.. MaxLength] Of TInfo; Top: Integer

End; Var Stack: TStack;

Очевидно, що при реалізації стеку за допомогою масиву необхідно резервувати масив, довжина якого (maxlength) рівна максимальній «глибині» стеку.

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

Procedure MakeNull (Var S: TStack);

Begin

S.Top MaxLength + 1

{якщо top = MaxLength + 1, то стек порожній }

End;

Function Empty (S: TStack): Boolean;

Begin

If S.Top > MaxLength Then Result True

Else Result False

End;

Function Top (Var S: TStack): TElement;

Begin

If Empty(S) Then Write (‘Стек порожній’)

Else Result S.Info[S.Top]

End;

Procedure Pop (Var S: TStack);

Begin

If Empty(S) Then Write (‘Стек порожній’)

Else S.Top S.Top + 1

113

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

End;

Procedure Push (x: TElement; Var S: TStack);

Begin

If S.Top = 1 Then Write (‘Стек повний’)

Else

Begin

S.Top S.Top - 1;

S.Info[S.Top] x

End

End;

Примітка 1: Очевидно, що можлива й інша реалізація стеку з фіксацією «дна» стеку в комірці з індексом 1. Тоді вершина стеку буде знаходитись в комірці з найбільшим індексом.

РЕАЛІЗАЦІЯ СТЕКУ ЗА ДОПОМОГОЮ СПИСКУ.

Так всі операції над стеком виконуються через його вершину, то досить легко реалізувати стек за допомогою лінійного однозв’язаного списку. Для такого списку достатньо зберігати тільки вказівник на перший елемент (вершину списку). Якщо стек порожній, то цей вказівник буде рівний Nil.

Рисунок 1. Схема реалізації стеку за допомогою лінійного однозв’язаного списку.

Для такої реалізації стеку опишемо абстрактний тип даних TStack наступним чином:

Next:TLink{поле вказівника на наступний елемент}

End;

Var Top: TLink;{вказівник на перший елемент – вершину стеку}

Приведемо приклади процедур, які реалізують базові операції над стеком.

Додання нового елемента у вершину стеку.

Var x: TInfo; { інформаційна частина нового елемента }

Read (x);

Procedure Push (x: TInfo; Var PtrTop: TLink);

{ Push заносить елемент x у вершину стеку PtrTop } Var Temp: TLink; { вказівник на новий елемент }

Begin

If MaxAvail>=SizeOf(x) Then {вільної пам’яті є достатньо}

Begin

вершиною стає новий елемент }

End {Then}

Else

Writeln(‘ недостатньо пам’яті, вставку не виконано ‘)

114

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

If PtrTop=Nil Then Empty true

Else Empty false

End;

End

End;

ЧЕРГА.

Означення 2. Черга – це динамічна структура даних (спеціальний вид лінійного списку), в якій додання нових елементів (постановка на чергу) здійснюється тільки у хвіст черги, а вибірка (видалення) елементів – тільки з голови черги.

Черга реалізує принцип обслуговування «першим прийшов – першим обслуговується» (FIFO: First Input – First Output).

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

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

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

MakeNull (Q) – очистка черги Q;

Front (Q) – повернення першого елемента черги Q;

Enqueue (x, Q) – додання нового елемента х у «хвіст» черги;

Dequeue (Q) – вибірка (видалення) елемента з «голови» черги;

Empty(Q) – перевірка чи черга Q є порожня.

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

Традиційними також є позначення: «хвіст» черги – rear (з англ. – тил), «голова» черги – front.

РЕАЛІЗАЦІЯ ЧЕРГИ ЗА ДОПОМОГОЮ МАСИВУ.

Чергу, аналогічно спискам та стекам, можна реалізувати за допомогою статичного масиву.

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

Спеціальні прийоми, які дозволяють вирішити в деякій мірі дану проблему, вимагають додаткових обчислювальних ресурсів – пам’яті або часу (внаслідок ускладнення базових операції над чергою).

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

– в напрямі індексу 1.

116

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

PtrFront PtrRear

End

Else

Begin { продовжуємо чергу }

{заповнюємо інформаційну частину нового елемента }

With PtrRear^. Do

Else

Writeln(‘ недостатньо пам’яті, вставку не виконано ‘)

End; { Enqueue }

Схема додання нового елемента у хвіст черги («постановка в чергу» приведена на Рис.6.

PtrFront PtrRear

Новий хвіст

2

Рисунок 6. Схема постановки нового елемента в чергу.

Пунктирними лініями зображені нові зв’язки (вказівники), а цифрами позначені відповідні оператори процедури Enqueue.

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

Вибірка (видалення) елемента з «голови» черги.

Procedure Dequeue (Var x: TInfo; Var PtrFront, PtrRear: TLink);

End

Else

{ в черзі більше одного елемента }

Begin

Temp PtrFront; {1}

PtrFront Temp^.Next;{2}

End

118

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Спроектувати алгоритм та програму формування динамічної структури даних і виконання операцій, визначених варіантом завдання.

Кількість елементів структури має бути ≥ 10. Інформаційну частину елементів структури заповнювати одним (якщо не вказано окремо) із способів:

a)введення з клавіатури (з опрацюванням спеціального символу – ознаки закінчення введення);

b)генерація за допомогою функції Random;

c)зчитування з попередньо підготовленого файлу даних.

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

Варіанти завдань.

1.З десяти чисел, які вводяться з клавіатури, сформувати два стеки – один з додатними числами, другий – з від’ємними та знайти суми елементів стеків.

2.В черзі цілих чисел обчислити суму елементів та видалити з черги від’ємні елементи.

3.В стеку дійсних чисел видалити всі елементи до першого від’ємного та обчислити їх суму.

4.Визначити максимальний елемент і його порядковий номер в черги цілих чисел та записати на його місце довільне число.

5.Перевірити, чи утворюють елементи стеку символів паліндром.

6.В черзі цілих чисел обчислити суму непарних елементів та видалити перший з них.

7.В стеку дійсних чисел обчислити суму елементів з парними номерами та видалити максимальний з них.

8.В черзі літер обчислити кількість голосних та видалити всі приголосні.

9.В стеку натуральних чисел обчислити середнє геометричне максимального та мінімального елементів.

10.В черзі цілих чисел видалити від’ємні елементи, а на їх місця записати 0 (нуль).

11.В стеку чисел замінити всі елементи менші заданого числа на 1.

12.В черзі символів видалити всі елементи рівні заданому символу і дописати в чергу відповідну кількість іншого символу.

13.В стеку цілих чисел видалити найдовшу послідовність нулів.

14.В черзі цілих чисел видалити більшу кількість парних чи непарних чисел.

15.В стеку літер видалити задане слово та в стек дописати нове слово з тією ж кількістю літер.

16.В черзі цілих чисел видалити всі числа, які належать заданому інтервалу.

17.В стеку чисел видалити максимальне число і дописати в стек різницю між ним та першим елементом.

18.В черзі чисел замінити числа, менші заданого, їх кубами.

19.Перевірити, чи утворюють елементи стеку цілих чисел паліндром.

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

21.В стеку чисел видалити елементи більші заданого і дописати в стек їх суму.

22.Перевірити чи є елементи черги цілих чисел записом двійкового числа та обчислити його десяткове значення.

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

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

25.Дописати в стек різницю сум елементів з парними та непарними порядковими номерами.

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

27.В стеку чисел видалити мінімальний елемент та дописати в стек його квадрат.

28.В черзі чисел видалити елемент рівний різниці між максимальним та мінімальним елементами черги та дописати в чергу їх суму.

29.Впорядкувати елементи двох стеків за зростанням та об’єднати стеки в один, впорядкований за спаданням.

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

Завдання 2.

120

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)