Перш ніж знати про абстрактний тип даних, ми повинні знати, що таке структура даних.
Що таке структура даних?
Структура даних — це техніка організації даних, щоб дані могли ефективно використовуватися. Існує два способи перегляду структури даних:
Чому структура даних?
Нижче наведено переваги використання структури даних:
- Це основні інгредієнти, які використовуються для створення швидких і потужних алгоритмів.
- Вони допомагають нам керувати та впорядковувати дані.
- Структури даних роблять код чистішим і легшим для розуміння.
Що таке абстрактний тип даних?
Абстрактний тип даних — це абстракція структури даних, яка надає лише інтерфейс, якому має відповідати структура даних. Інтерфейс не дає жодних конкретних деталей про те, що має бути реалізовано, або на якій мові програмування.
Іншими словами, можна сказати, що абстрактні типи даних — це сутності, які є визначеннями даних і операцій, але не мають деталей реалізації. У цьому випадку ми знаємо дані, які ми зберігаємо, і операції, які можна виконувати з даними, але ми не знаємо про деталі реалізації. Причина відсутності деталей реалізації полягає в тому, що кожна мова програмування має різну стратегію реалізації, наприклад; структура даних C реалізована за допомогою структур, тоді як структура даних C++ реалізована за допомогою об’єктів і класів.
Наприклад, Список — це абстрактний тип даних, реалізований за допомогою динамічного масиву та зв’язаного списку. Черга реалізована за допомогою зв’язаної черги на основі списку, черги на основі масиву та черги на основі стека. Карта реалізується за допомогою карти дерева, хеш-карти або хеш-таблиці.
Модель абстрактного типу даних
Перш ніж знати про модель абстрактного типу даних, ми повинні знати про абстракцію та інкапсуляцію.
сортування купи
Абстракція: це техніка приховування внутрішніх деталей від користувача та показу лише необхідних деталей користувачеві.
Інкапсуляція: це техніка об’єднання даних і функції-члена в одному блоці, відома як інкапсуляція.
На малюнку вище показано модель ADT. У моделі ADT є два типи моделей, тобто публічна функція та приватна функція. Модель ADT також містить структури даних, які ми використовуємо в програмі. У цій моделі спочатку виконується інкапсуляція, тобто всі дані загортаються в єдиний блок, тобто ADT. Потім виконується абстракція, що означає показ операцій, які можна виконати над структурою даних, і які структури даних ми використовуємо в програмі.
сонячний деол
Давайте розберемося з абстрактним типом даних на прикладі реального світу.
Якщо розглядати смартфон. Ми розглядаємо високі характеристики смартфона, такі як:
- 4 Гб оперативної пам'яті
- Процесор Snapdragon 2,2 ГГц
- 5-дюймовий РК-екран
- Подвійна камера
- Android 8.0
Наведені вище характеристики смартфона є даними, і ми також можемо виконувати такі операції на смартфоні:
Смартфон — це об’єкт, чиї дані або характеристики та операції наведено вище. Абстрактне/логічне подання та операції є абстрактними або логічними поданнями смартфона.
Нижче наведено представлення реалізації наведеного вище абстрактного/логічного подання:
class Smartphone { private: int ramSize; string processorName; float screenSize; int cameraCount; string androidVersion; public: void call(); void text(); void photo(); void video(); }
Наведений вище код є реалізацією специфікацій і операцій, які можна виконувати на смартфоні. Вид реалізації може відрізнятися, оскільки синтаксис мов програмування відрізняється, але абстрактний/логічний вигляд структури даних залишиться незмінним. Тому ми можемо сказати, що абстрактне/логічне подання не залежить від подання реалізації.
Примітка. Ми знаємо операції, які можна виконувати з попередньо визначеними типами даних, такими як int, float, char тощо, але ми не знаємо деталей реалізації типів даних. Таким чином, можна сказати, що абстрактний тип даних розглядається як прихований ящик, який приховує всі внутрішні деталі типу даних.
Приклад структури даних
Припустімо, що у нас є масив індексів розміром 4. Ми маємо розташування індексів, починаючи з 0, 1, 2, 3. Масив — це структура даних, де елементи зберігаються в безперервному місці. Адреса пам’яті першого елемента – 1000, другого – 1004, третього – 1008, четвертого – 1012. Оскільки він цілого типу, він займатиме 4 байти, а різниця між адресами кожного елемента – 4 байтів. Значення, що зберігаються в масиві: 10, 20, 30 і 40. Ці значення, позиції індексів і адреси пам’яті є реалізаціями.
Абстрактне або логічне подання цілочисельного масиву можна сформулювати так:
- Він зберігає набір елементів цілого типу.
- Він зчитує елементи за позицією, тобто за індексом.
- Він змінює елементи за індексом
- Виконує сортування
Перегляд реалізації цілочисельного масиву:
a[4] = {10, 20, 30, 40} cout<< a[2] a[3] = 50