Loading AI tools
Абстрактний тип даних (АТД) — це математична модель для типів даних, де тип даних визначається поведінкою (семантикою) з точки зору користувача даних, а саме в термінах можливих значень, можливих операцій над даними цього типу і поведінки цих операцій. Вся внутрішня структура такого типу захована від розробника програмного забезпечення — в цьому і полягає суть абстракції. Абстрактний тип даних визначає набір функцій, незалежних від конкретної реалізації типу, для оперування його значеннями. Конкретні реалізації АТД називаються структурами даних.
В програмуванні абстрактні типи даних зазвичай подаються у вигляді інтерфейсів, які приховують відповідні реалізації типів. Програмісти працюють з абстрактними типами даних виключно через їх інтерфейси, оскільки реалізація може в майбутньому змінитися. Такий підхід відповідає принципу інкапсуляції в об'єктно-орієнтованому програмуванні. Сильною стороною цієї методики є саме приховування реалізації. Раз зовні опублікований тільки інтерфейс, то поки структура даних підтримує цей інтерфейс, всі програми, що працюють із заданою структурою абстрактним типом даних, будуть продовжувати працювати. Розробники структур даних намагаються, не змінюючи зовнішнього інтерфейсу і семантики функцій, поступово допрацьовувати реалізації, покращуючи алгоритми по швидкості, надійності і використовуваної пам'яті.
Різниця між абстрактними типами даних і структурами даних, які реалізують абстрактні типи, можна пояснити на наступному прикладі. Абстрактний тип даних список може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не за швидкістю) для всіх реалізацій.
Абстрактні типи даних дозволяють досягти модульності програмних продуктів і мати кілька альтернативних взаємозамінних реалізацій окремого модуля.
Наприклад, цілі числа — це абстрактний тип даних, який визначається як значення …, −2, −1, 0, 1, 2, … , і поводиться відповідно до звичної математики (з увагою про цілочисельне ділення), за допомогою операцій додавання, віднімання, множення і ділення, а також операції більше ніж, менше ніж і т. д. незалежно від того, як цілі числа представлені за допомогою комп'ютера.[a] Очевидно, що «поведінка» включає в себе різні аксіоми (асоціативність і комутативність складання і т. д.) і умови за операціями (не може ділити на нуль). Зазвичай цілі числа представлені в структурі даних у вигляді двійкових чисел, найчастіше як доповняльний код, але може бути двійково-десятковий код або обернений код, але користувач абстрагується від конкретного вибору уявлення, і може просто використовувати ці дані у вигляді цілих чисел.
АТД складається не тільки з операцій, але і значень початкових даних і обмежень на операції. «Інтерфейс», як правило, стосується лише операцій, і, можливо, деяких з обмежень на операції, зокрема попередні умови і постумови, але не інші обмеження, такі як відносини між операціями.
Наприклад, абстрактний стек, який має LIFO структуру, може бути визначений за допомогою трьох операцій: PUSH, котра вставляє елемент даних в стек; POP, яка видаляє елемент даних з нього; і PEEK або TOP, яка отримує доступ до елементу даних в вершині стека без видалення. Абстрактна черга, яка має FIFO структуру, також буде мати три операції: ENQUEUE, яка вставляє елемент даних в чергу; DEQUEUE, яка видаляє перший елемент даних з нього; і FRONT, що отримує доступ і служить першим елементом даних в черзі. Там не було б ніякої можливості диференціювати ці два типи даних, якщо математичне обмеження не вводиться, тоді це для стека вказує, що кожна POP завжди повертає найостанніший втиснутий елемент, який ще не вискочив. При аналізі ефективності алгоритмів, які використовують стеки, можна також вказати, що всі операції не приймають той же самий час, незалежно від того, скільки елементів даних були витіснені в стек, і що стек використовує постійну кількість схов для кожного елемента.
Абстрактні типи даних — це чисто теоретичні об'єкти, які використовуються (між іншим) для спрощення опису абстрактних алгоритмів, також для класифікації та оцінки структури даних, і формального опису систем типів мов програмування. Проте АТД можуть бути реалізовані за допомогою певних типів даних або структур даних, у багатьох відношеннях і в багатьох мовах програмування; або описані в формальній мові специфікації. АТД часто реалізуються у вигляді модулів: інтерфейс модуля оголошує процедури, які відповідають операціям АТД, іноді з коментарями, які описують обмеження. Ця стратегія приховування інформації дозволяє реалізації модуля бути зміненою без порушення клієнтських програм.
Термін Абстрактний Тип Даних також можна розглядати, як узагальнений підхід ряду алгебричних структур, таких, як решітки, групи і кільця.[1] Поняття абстрактних типів даних пов'язане з поняттям абстракції даних, це важливо в об'єктно-орієнтованому програмування та методології проектування за контрактом на розробку програмного забезпечення.[2]
Абстрактний тип даних визначається як математична модель об'єктів даних, які становлять тип даних, а також функції, які працюють на цих об'єктах. Там немає стандартних конвенцій, для визначення їх. Широкий поділ може бути проведений між «імперативними» і «функціональним» стилів визначення.
Визначення імперативного стилю
У філософії імперативних мов програмування, абстрактна структура даних задумана як сутність, яка є змінним-це означає, що він може перебувати в різних станах в різний час. Деякі операції можуть змінити стан АТД; таким чином, порядок, в якому оцінюються операції має важливе значення, і та ж сама операція на одних і тих же суб'єктах, можуть мати різні ефекти, якщо виконуються в різний час, так само, як інструкції комп'ютера, або команди і процедури імперативної мови. Щоб підкреслити цю точку зору, прийнято казати, що операції виконуються або застосовуються, не стільки, скільки оцінюються. Імперативний стиль часто використовується при описі абстрактних алгоритмів. (Дивіться Мистецтво програмування Дональда Кнута для отримання більш докладної інформації)
Абстрактна змінна
Визначення імперативного стилю АТД часто залежать від поняття абстрактної змінної, яку можна розглядати, як найпростіший нетривіальний АТД. Абстрактна змінна 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 членів певної множини 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) }
де х, у та z є будь-які значення, а U, V, W попарно різні змінні, еквівалентно
{ U ← y; V ← z; W ← x }
При цьому неявно передбачається, що операції на екземплярі стека не змінюють стан будь-якого іншого екземпляру АТД, в тому числі інших стеків; а саме
- Для будь-яких значень x, y, а також будь-яких різних стеків S і T, послідовність {
push(S,x);push(T,y)} еквівалентна послідовності {push(T,y);push(S,x)}.
Абстрактне визначення стека зазвичай включає в себе також булеву функцію empty(S) і операцію create(), яка повертає екземпляр стека, з аксіом, еквівалентних
create() ≠ S для будь-якого стека S (новостворений стек відрізняється від усіх попередніх стеків);empty(create()) (новостворений стек порожній);notempty(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.
Деякі загальні АТД, які довели свою корисність в найрізноманітніших додатках
Кожен з цих АТД може бути визначена різними способами і варіантами, не обов'язково еквівалентними. Наприклад, абстрактний стек може або не може мати операцію підрахунку, яка говорить, скільки елементів були добавлені і ще не видалені. Цей вибір робить відмінність не тільки для своїх клієнтів, але і для реалізації.
Абстрактний графічний тип даних
Розширення АТД для комп'ютерної графіки було запропоновано в 1979 році:[4] абстрактний тип графічних даних (AGDT). Воно було введено Надією Магненат Тельманн і Даніелем Тельманн. AGDT забезпечує переваги АТД зі зручностями для побудови графічних об'єктів в структурованому вигляді.
Реалізація АТД означає забезпечення однієї процедури або функції для кожної абстрактної операції. Екземпляри АДТ представлені будь-якою конкретною структурою даних, яка маніпулює цими процедурами, відповідно до специфікації АТД.
Як правило, існує багато способів реалізувати той же АТД, з використанням декількох різних конкретних структур даних. Так, наприклад, абстрактний стек може бути реалізований за допомогою зв'язаного списку або масивом.
Для того, щоб запобігти клієнтів від залежності від реалізації, АТД часто упакований в вигляді непрозорого типу даних в одному або декількох модулях, чий інтерфейс містить тільки підпис (кількість і типи параметрів і результатів) від операцій. Реалізація модуля, а саме тіла процедур і конкретна структура даних, яка використовується — тоді можуть бути приховані від більшості клієнтів модуля. Це дає можливість змінити реалізацію, не зачіпаючи клієнтів. Якщо реалізація піддається впливу, відомо, замість цього, як прозорий тип даних.
При реалізації АТД, кожен екземпляр (в термінах імперативного стилю) або кожне стан (в термінах функціонального стилю), як правило, представлений дескриптором якогось виду.[5]
Сучасні об'єктно-орієнтовані мови, такі як 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); // додає адресу 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, які можна розглядати як реалізацію абстрактного списку.
- Концепція (узагальнене програмування)[en]
- Формальні методи
- Функціональна специфікація[en]
- Узагальнений алгебричний тип даних
- F-алгебра
- Принцип підстановки Лісков
- Теорія типів
- Walls and Mirrors[en]
- Список
- Стек
- Черга (структура даних)
- Асоціативний масив
- Черга з пріоритетом
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
