Користувач:Alex Minaev/Чернетка

Приклади

Наприклад, цілі числа — це абстрактний тип даних, який визначається як значення …, −2, −1, 0, 1, 2, … , і поводиться відповідно до звичної математики (з увагою про цілочисельне ділення), за допомогою операцій додавання, віднімання, множення і ділення, а також операції більше ніж, менше ніж і т. д. незалежно від того, як цілі числа представлені за допомогою комп'ютера. Очевидно, що «поведінка» включає в себе різні аксіоми (асоціативність і комутативність складання і т. д.) і умови за операціями (не може ділити на нуль). Зазвичай цілі числа представлені в структурі даних у вигляді двійкових чисел, найчастіше як доповняльний код, але може бути двійково-десятковий код або обернений код, але користувач абстрагується від конкретного вибору уявлення, і може просто використовувати ці дані у вигляді цілих чисел.

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

Наприклад, абстрактний стек, який має LIFO структуру, може бути визначений за допомогою трьох операцій: PUSH, котра вставляє елемент даних в стек; POP, яка видаляє елемент даних з нього; і PEEK або TOP, яка отримує доступ до елементу даних в вершині стека без видалення. Абстрактна черга, яка має FIFO структуру, також буде мати три операції: ENQUEUE, яка вставляє елемент даних в чергу; DEQUEUE, яка видаляє перший елемент даних з нього; і FRONT, що отримує доступ і служить першим елементом даних в черзі. Там не було б ніякої можливості диференціювати ці два типи даних, якщо математичне обмеження не вводиться, тоді це для стека вказує, що кожна POP завжди повертає найостанніший втиснутий елемент, який ще не вискочив. При аналізі ефективності алгоритмів, які використовують стеки, можна також вказати, що всі операції не приймають той же самий час, незалежно від того, скільки елементів даних були витіснені в стек, і що стек використовує постійну кількість схов для кожного елемента.

Вступ

Абстрактні типи даних — це чисто теоретичні об'єкти, які використовуються (між іншим) для спрощення опису абстрактних алгоритмів, також для класифікації та оцінки структури даних, і формального опису систем типів мов програмування. Проте АТД можуть бути реалізовані за допомогою певних типів даних або структур даних, у багатьох відношеннях і в багатьох мовах програмування; або описані в формальній мові специфікації. АТД часто реалізуються у вигляді модулів: інтерфейс модуля оголошує процедури, які відповідають операціям АТД, іноді з коментарями, які описують обмеження. Ця стратегія приховування інформації дозволяє реалізації модуля бути зміненою без порушення клієнтських програм.

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

Визначення абстрактного типу даних

Абстрактний тип даних визначається як математична модель об'єктів даних, які становлять тип даних, а також функції, які працюють на цих об'єктах. Там немає стандартних конвенцій, для визначення їх. Широкий поділ може бути проведений між «імперативними» і «функціональним» стилів визначення.

Визначення імперативного стилю

У філософії імперативних мов програмування, абстрактна структура даних задумана як сутність, яка є змінним-це означає, що він може перебувати в різних станах в різний час. Деякі операції можуть змінити стан АТД; таким чином, порядок, в якому оцінюються операції має важливе значення, і та ж сама операція на одних і тих же суб'єктах, можуть мати різні ефекти, якщо виконуються в різний час, так само, як інструкції комп'ютера, або команди і процедури імперативної мови. Щоб підкреслити цю точку зору, прийнято казати, що операції виконуються або застосовуються, не стільки, скільки оцінюються. Імперативний стиль часто використовується при описі абстрактних алгоритмів. (Дивіться Мистецтво програмування Дональда Кнута для отримання більш докладної інформації)

Абстрактна змінна

Визначення імперативного стилю АТД часто залежать від поняття абстрактної змінної, яку можна розглядати, як найпростіший нетривіальний АДТ. Абстрактна змінна V є змінний об'єкт, який допускає дві операції:

• store(V, х), де х є значення невизначеного характеру;
• fetch(V), що дає значення, з тим обмеженням, що
• fetch(V) завжди повертає значення х, котре використовуються в самий останній операції store(V, х) на тій же самій змінної V.

Як і в багатьох мовах програмування, операція store(V, x) часто пишеться V ← x (або деякі аналогічні позначення) і fetch(V) мається на увазі кожен раз, коли змінна V використовується в контексті, де потрібно значення. Так, наприклад, V ← V + 1 зазвичай розуміється, як скорочення для store(V,fetch(V) + 1).

У цьому визначенні неявно передбачається, що збереження значення в змінну U не робить ніякого впливу на стан окремої змінної V. Для того, щоб зробити це припущення явним, можна було б додати, що обмеження

• якщо U і V є різні змінні, то послідовність { store(U, x); store(V, y) } еквівалентна послідовності  store(V, y); store(U, x) }.

У більш загальному плані, при визначенні АТД часто припускають, що будь-яка операція, яка змінює стан одного екземпляра АТД не робить ніякого впливу на стан будь-якого іншого екземпляру (в тому числі інших екземплярів одного і того ж АТД), хіба тільки аксіоми АТД не означають, що два екземпляри пов'язані (псевдонімами) в цьому сенсі. Наприклад, при розширенні визначення абстрактної змінної, щоб включити абстрактні структури, операція, яка вибирає поле з структурою змінної R повинен дати змінну V, яка є псевдонімом до тієї частини R.

Означення абстрактної змінної V може також обмежити записані значення х членів певної множини X, називається діапазон, або тип V. Як і в мовах програмування, такі обмеження можуть спростити опис і аналіз алгоритмів, а також поліпшити їх читаність.

Зверніть увагу, що це визначення нічого не говорить про результат оцінки fetch(V), коли V є не-ініціалізована, тобто, перед виконанням будь-якої операції збереження на V. Алгоритм, який робить це, як правило, вважається недійсним, оскільки його ефект не визначений. (Проте, є деякі важливі алгоритми, ефективність яких значною мірою залежить від припущення, що така вибірка є законною, і повертає деяке довільне значення в діапазоні змінної.)

Створення екземпляра

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

• результат операції Create() відрізняється від будь-якого екземпляру, які використовується алгоритмом.

Ця аксіома може бути посилена, щоб виключити також часткове накладення спектрів з іншими екземплярами. З іншого боку, ця аксіома досі дозволяє реалізації операціі Create() отримати раніше створений екземпляр, який став недоступним для програми.

Приклад: абстрактний стек (імперативний стиль)

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

• push(S, x), де х деяке значення невизначеного характеру;
• pop(S), що надає значення як результат, з тим обмеженням, що
• Для будь-якого значення х і будь-якої абстрактної змінної V, послідовність операцій { push(S,x); V ← pop(S)} еквівалентна операціі V ← x.

Так як привласнення V ← x, за визначенням, не може змінити стан S, ця умова означає, що V ← pop(S) відновлює S в стан він мав до операціі push(S,x). З цієї умови і з властивостей абстрактних змінних, то це означає, наприклад, що послідовність

{ push(S, x); push(S, y); U ← pop(S); push(S, z); V ← pop(S); W ← pop(S) }

де х, у, г є будь-які значення, а U, V, W попарно різні змінні, еквівалентно

{ U ← y; V ← z; W ← x }

При цьому неявно передбачається, що операції на екземплярі стека не змінюють стан будь-якого іншого екземпляру АТД, в тому числі інших стеків; а саме

• Для будь-яких значень х, у, а також будь-яких різних стеків S і T, послідовність { push(S,x); push(T,y)} еквівалентна послідовності { push(T,y); push(S,x)}.

Абстрактне визначення стека зазвичай включає в себе також булеву функцію empty(S) і операцію create(), яка повертає екземпляр стека, з аксіом, еквівалентних

• create() ≠ S для будь-якого стека S (новостворений стек відрізняється від усіх попередніх стеків);
• empty(create()) (новостворений стек порожній);
• not empty(push(S, x)) (заштовхуючи щось в стек робить його непустим);

Стиль одного екземпляру

Іноді АТД визначається так, якби тільки один його екземпляр існував під час виконання алгоритму, і всі операції були застосовані до цього екземпляру, який явно не записаний. Наприклад, абстрактний стек, який вказано вище, може бути визначений з операціями push(x) та pop(), які працюють на єдиному існуючому стеку. Визначення АТД в цьому стилі можна легко переписати, щоб визнати, що кілька екземплярів АТД співіснують, шляхом додавання явного параметра екземпляру (наприклад, S в попередньому прикладі) для кожної операції, яка використовує або змінює неявне екземпляр.

З іншого боку, деякі АТД не можуть бути визначені за значенням, не припускаючи декількох екземплярів. Це той випадок, коли одна операція приймає два різних екземпляра АДТ в якості параметрів. Для прикладу, розглянемо доповнюючи визначення абстрактного стека з операцією compare(S, T), яка перевіряє, чи стеки S і Т містять одні й ті ж елементи в тому ж порядку.

Визначення функціонального стилю

Інший спосіб визначення АТД, ближче до духу функціонального програмування, це розглядати кожен стан структури, як окрему сутність. З цієї точки зору, будь-яка операція, яка змінює АТД моделюється як математична функція, яка приймає старий стан в якості аргументу, і повертає новий стан як частина результату. На відміну від імперативних операцій, ці функції не мають побічних ефектів. Таким чином, порядок, в якому вони оцінюються — несуттєвий, і та ж операція застосовується до тих же аргументів (в тому числі і тих же вхідних станів) завжди буде повертати ті ж результати (і вихідні стани).

У функціональному поданні, зокрема, не існує ніякого способу (або необхідності), щоб визначити «абстрактне змінну» з семантикою імперативних змінних (а саме, з операціями fetch і store). Замість того щоб зберігати значення в змінних, він передає їх в якості аргументів функції.

Приклад: абстрактний стек (функціональний стиль)

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

• push: приймає стан стека і довільне значення, повертає стан стека;
• top: приймає стан стека, повертає значення;
• pop: приймає стан стека, повертає стан стека.

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

Замість операціі create(), визначення абстрактного стека у функціональному стилі може припустити існування особливого стану стека, порожнього стека, який позначається спеціальним символом, як Λ або «()»; або визначити операцію bottom(), яка не приймає аргументів і повертає цей особливий стан стека. Зауважимо, що аксіоми мають на увазі, що

• push(Λ, x) ≠ Λ.

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

Зверніть увагу, що ці аксіоми не визначають дію top(s) або pop(s), якщо s не є станом стека повертається операцією push. Так як операція push залишає стек не порожнім, тоді ці дві операції не визначені (і, отже неспроможні) при s = Λ. З іншого боку, аксіоми (і відсутність побічних ефектів) слід, що push(s, x) = push(t, y) тоді й лише тоді, коли x = y та s = t.

Як і в деяких інших областях математики, прийнято вважати також, що стек станів тільки ті, чиє існування може бути доведено з аксіом в кінцеве число кроків. В прикладі абстрактного стеку, зазначений вище, це правило означає, що кожен стек — це кінцева послідовність значень, яка стає порожнім стеком (Λ) після кінцевого числа викликів операції pop(). Самі по собі, аксіоми, не виключають існування нескінченних стеків (на котрих операцію pop() можна викликати нескінчену кількість раз, щоразу отримуючи інший стан) або кругові стеки (які повертаються в той же стан після кінцевого числа викликів операції pop()). Зокрема, вони не виключають стани S такі, що pop(s) = s або push(s, x) = s для деякого х. Однак, так як ніхто не може отримати такий стек станів із заданими операціями, вони вважаються «не існуючими».

Чи слід включати складність

Крім поведінки з точки зору аксіом, можна також включити, в визначенні операції АТД, їх алгоритмічної складності. Олександр Степанов, дизайнер стандартної бібліотеки шаблонів C++, включені гарантії складності в специфікації STL, аргументуючи:

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

— Олександр Степанов

Типові операції

Деякі операції, які часто вказані для АТД (можливо, під іншими назвами) є

• compare(s, t), що перевіряє, чи є еквівалентні в деякому сенсі два стани екземплярів;
• hash(s), яка обчислює деякі стандартні геш-функції зі стану екземплярів;
• print(s) або show(s), яка виробляє зручний для читання представлення стану екземпляру.

У визначенні АТД в імперативному стилі також можливо знайти

• create(), що дає новий екземпляр АТД;
• initialize(s), що готує новий створений екземпляр s для подальших операцій, або скидає його в якийсь «початковий стан»;
• copy(s, t), що ставить екземпляр s у стан еквівалентний стану екземпляра t;
• clone(t), який виконує s ← create(), copy(s, t), і повертає s;
• free(s) або destroy(s), що звільняє пам'ять та інші ресурси, котрі використовуються екземпляром s.

Операція free зазвичай не актуальна або немає сенсу, оскільки АТД — це теоретичні об'єкти, які не «використовують пам'ять». Проте, це може бути необхідно, коли необхідно проаналізувати сховище, що використовується алгоритмом, який використовує АТД. У цьому випадку потрібно додаткові аксіоми, які визначають, скільки пам'яті кожен екземпляр АТД використовує, в залежності від його стану, і скільки пам'яті повертається в пул при використанні операціі free.

Приклади

Деякі загальні АТД, які довели свою корисність в найрізноманітніших додатках

• Контейнер
• Список
• Множина
• Multiset
• Map
• Multimap
• Об'єктний граф
• Стек
• Черга
• Черга з пріоритетом
• Двобічна черга
• Double-ended priority queue

Кожен з цих АТД може бути визначена різними способами і варіантами, не обов'язково еквівалентними. Наприклад, абстрактний стек може або не може мати операцію підрахунку, яка говорить, скільки елементів були добавлені і ще не видалні. Цей вибір робить відмінність не тільки для своїх клієнтів, але і для реалізації.

Абстрактний графічний тип даних

Розширення АТД для комп'ютерної графіки було запропонована в 1979 році: абстрактний тип графічних даних (AGDT). Воно було введено Надією Магненат Тельманн і Даніелем Тельманн. AGDT забезпечує переваги АТД зі зручностями для побудови графічних об'єктів в структурованому вигляді.

Реалізація

Реалізація АТД означає забезпечення однієї процедури або функції для кожної абстрактної операції. Екземпляри АДТ представлені будь-якою конкретною структурою даних, яка маніпулює цими процедурами, відповідно до специфікації АТД.

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

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

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

Сучасні об'єктно-орієнтовані мови, такі як C++ і Java, підтримують форму абстрактних типів даних. Коли клас використовується в якості типу, це абстрактний тип, який відноситься до прихованого уявлення. У цій моделі АТД зазвичай реалізується як клас, і кожен екземпляр АТД, як правило, об'єкт цього класу. Інтерфейс модуля зазвичай оголошує конструктори, як звичайні процедури, і більшість інших операцій АТД, як методи цього класу. Проте, такий підхід не легко інкапсулювати декілька репрезентативних варіанти, знайдених в АТД. Вона також може підірвати розширюваності об'єктно-орієнтованих програм. У чисто об'єктно-орієнтованої програми, яка використовує інтерфейси як типи, типи відносяться до поведінці, не уявленню.

Приклад: реалізація абстрактного стека

Як приклад, ось реалізація абстрактного стека в мові програмування C.

Імперативний стиль інтерфейсу

Інтерфейс в імперативному стилі може бути:

typedef struct stack_Rep stack_Rep;       // тип: уявлення екземпляру стека(непрозорий запис)
typedef stack_Rep* stack_T;               // тип: дескріптор до екземпляру стека (непрозорий вказівник)
typedef void* stack_Item;                 // тип: значення, збережене в екземплярі стека(довільний адрес)

stack_T stack_create(void);               // створює новий порожній екземпляр стека
void stack_push(stack_T s, stack_Item x); // додає елемент у вершину стека
stack_Item stack_pop(stack_T s);          // видаляє верхній елемент зі стека і повертає його
bool stack_empty(stack_T s);              // перевіряє, порожній чи стек

Цей інтерфейс може бути використаний в такий спосіб:

#include <stack.h>          // підключає інтерфейс стека

stack_T s = stack_create(); // створює новий порожній екземпляр стека
int x = 17;
stack_push(s, &x);          // додає адресу х у вершину стека
void* y = stack_pop(s);     // видаляє адресу х зі стека і повертає його
if(stack_empty(s)) { }      // робить щось, якщо стек порожній

Цей інтерфейс може бути реалізований різними способами. Реалізація може бути як завгодно неефективна, так як формального визначення АТД, вище, не визначає, скільки простору стека може використовуватися, і як довго кожна операція повинна зайняти. Він також не уточнює, чи продовжує стек стану s існувати після виклику x ← pop(s).

На практиці формальне визначення повинно бути зазначено, що простір пропорційно кількісті елементів заштовханих і ще не видалених; і що кожена з операцій вище, повинна закінчитися за постійну кількість часу, незалежно від цього числа. Для виконання цих додаткових специфікацій, реалізація може використовувати зв'язаний список або масив (з динамічною зміною розмірів) разом з двома цілими числами (кількість елементів і розмір масиву).

Функціональний стиль інтерфейсу

Функціональний стиль визначення АТД є більш придатними для функціональних мов програмування, і навпаки. Проте, можна забезпечити інтерфейс функціональним стилем навіть в імперативній мові программування, як C. Наприклад:

typedef struct stack_Rep stack_Rep;          // тип: уявлення стану стека (непрозорий запис)
typedef stack_Rep* stack_T;                  // тип: дескріптор до стану стека (непрозорий вказівник)
typedef void* stack_Item;                    // тип: значення стану стека (довільний адрес)

stack_T stack_empty(void);                   // повертає порожнє стан стека
stack_T stack_push(stack_T s, stack_Item x); // додає елемент у верхшину стану стека і повертає отриманий стан стека
stack_T stack_pop(stack_T s);                // видаляє верхній елемент зі стану стека і повертає отриманий стан стека
stack_Item stack_top(stack_T s);             // повертає верхній елемент стану стека

Бібліотеки АТД

Багато сучасних мов програмування, такі як C ++ і Java, поставляються зі стандартними бібліотеками, які реалізують кілька загальних АТД, таких як ті, які перераховані вище.

Вбудовані абстрактні типи даних

Специфікація деяких мов програмування навмисно розпливчаста про подання деяких вбудованих типів даних, визначаючи тільки ті операції, які можуть бути зроблені на них. Таким чином, ці типи можна розглядати як «вбудовані АТД». Прикладами є масиви в багатьох сценарних мовах, таких як Awk, Lua, і Perl, які можна розглядати як реалізацію абстрактного списку.

Див. також

• Concept (generic programming)
• Формальні методи
• Functional specification
• Generalized algebraic data type
• Initial algebra
• Принцип підстановки Лісков
• Type theory
• Walls and Mirrors

Джерела інформації

• Liskov, Barbara; Zilles, Stephen (1974). Programming with abstract data types. Proceedings of the ACM SIGPLAN symposium on Very high level languages. с. 50—59. doi:10.1145/800233.807045.
• Dale, Nell; Walker, Henry M. (1996). Abstract Data Types: Specifications, Implementations, and Applications. Jones & Bartlett Learning. ISBN 978-0-66940000-7.

Література

• Mitchell, John C.; Plotkin, Gordon (July 1988). Abstract Types Have Existential Type (PDF). ACM Transactions on Programming Languages and Systems. 10 (3). doi:10.1145/44501.45065.