Білет № 10

Білет № 9.

Білет № 8.

Специфікація – це опис суттєвих властивостей об’єкта.

Специфікація абстрактного типу даних: опис множини значень, опис операцій.

До-умова – опис стану фактичних параметрів до виконання операції.

Після-умова - опис стану параметрів після виконання операції.(результат операціі)

1.Специфікація – це опис суттєвих властивостей об’єкта.

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

До-умова – опис стану фактичних параметрів до виконання операції.

Після-умова - опис стану параметрів після виконання операції.(результат операціі)

2. Визначимо формально дерево як скінчену множину Т, яка складається з одного або більше вузлів, таких що

a) Існує один особливо позначений вузол, що його називають коренем даного дерева.

b) Решта вузлів (за виключенням кореня) містяться у m >= 0 множин Т ₁, Т ₂, …, Т _m, що попарно не перетинаються і кожна з яких є у свою чергу деревом. Дерева Т ₁, Т ₂, …, Т _m називаються піддеревами даного кореня.

Це визначення є рекурсивним, тобто ми визначили дерево у термінах самих же дерев. Звісно, жодного «зачарованого» кола тут не виникає, оскільки дерева з n >= 1 вузлами визначаються через поняття дерева з числом вузлів, меншим за n; відтак, наше визначення дає поняття дерев з двома, трьома, і у кінцевому рахунку з довільним числом вузлів. Можливо дати й нерекурсивне визначення дерева, але рекурсивне визначення видається більш підходящим, через те, що рекурсивність є природньою характеристикою структур типу дерева. Рекурсивний характер дерев присутній також і в природі: бруньки молодого дерева виростають у гілки, які мають свої власні бруньки, що дають нові гілки тощо.

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

Подання. Перш за все ми маємо вибрати певний спосіб зберігання значень типу СтрічкаЛітер. Будемо послуговуватися Pascal’ем як мовою для втілення. Припустимо, що ми скористалися вбудованими типами даних цієї мови у наступний спосіб:

type letterstring = record

n: 0..80 {поточна довжина стрічки}

str: array [1..80] of letter {елементи даних}

end;

Зауважимо, що якщо s є letterstring, то перша літера знаходиться у s.str[1], друга літера є у s.str[2], і так до останньої, яка розміщується у s.str[n].

Вибір конкретної комбінації вбудованих типів даних визначає подання АТД.

Втілення. Далі, потрібно написати код, який втілює абстрактні операції. Колекція алгоритмів, які втілюють абстрактні операції АТД, називається втіленням АТД. За умови, що не виникатиме двозначностей, ми будемо скорочувати термінологію, послуговуючись терміном «втілення» аби позначати комбінацію подання та втілення у тому сенсі, як їх визначено вище. На показано можливе втілення розглядуваного АТД мовою Pascal. Зауважимо, що процедура firstletter (ПершаЛітера) у цьому втіленні не передбачає жодної дії, коли вхідна стрічка є пустою (тобто s.n = 0 – довжина є нульовою). Вона навіть не перевіряє, чи має місце саме цей випадок. За допомогою до-умови користувачу повідомляється, що він не має права послуговуватися цією процедурою, якщо стрічкалітер є пустою. Подібне справедливо й стосовно операції append (Долучити), коли стрічкалітер має 80 літер.

Поняття інкапсуляції. Одним з головних мотивів застосування АТД є бажання приховати усі несуттєві деталі подання та втілення від користувача. Ми інкапсулюємо (encapsulate) такі деталі всередині модуля для того, аби забезпечити приховування інформації.

Для того, щоб підкреслити щойно викладену точку зору, ми будемо користуватися спеціальним графічним зображенням, яке називатимемо капсулою. Приклад капсули наведено на мал. (Капсула_СтрічкаЛітер.jpg). Значок функції (<>) символізує той факт, що її значення повертається як значення імені функції.

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

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

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

Дата добавления: 2015-05-26