Подразделы

Другие разделы

Дата и время

02/04/2025 04:21:34

Авторизация

Зарегистрироваться
Восстановить пароль

Абстракция и разработка программ

Декомпозиция и абстракция Методы абстрагирования Виды абстракций Абстрактный тип данных Классификация АТД

Классификация АТД

Свойство	_	_	_	_
Изменяемость	Неизменяемые объекты String в Java	Изменяемые объекты std::string в C++
Порядок первый/последний, следующий/предыдущий (опционально)	Определяется программистом Список, Очередь	Определяется значениями Очередь с приоритетами	Не важен Множество, Таблица в базе данных
Доступ к элементам	Последовательный, через итератор Список	Произвольный, по номеру Массив	Произвольный, по ключу Словарь	Частичный Стек (только верхний элемент)
Модель	Линейный (одномерный) Список, Очередь с приоритетами	Многомерный Матрица	Нелинейный Граф, DOM для HTML

Модель АТД не связана с используемыми для представления структурами данных. Модель служит для объяснения поведения АТД, а не требованиями к реализации. Например, линейный АТД Двухсторонняя очередь в C++ реализуется через нелинейные структуры данных, чтобы минимизировать количество операций с динамической памятью в критических приложениях. Нелинейный АТД Граф может быть реализован через матрицу смежности или список ребер, и выбор наиболее эффективного варианта будет зависеть от реализуемого алгоритма.

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

Для создания массива в языке C нужно написать
int a[100];
а в С++ нужно использовать
std::vector<int> a(100);
std::array<int,100> a;

Для получения размера массива в C++ нужно написать a.size(), а в C – (sizeof(a)/sizeof(a[0])). Совпадает только операция доступа к элементу: a[i].

Но программист может определить свою реализацию АТД Массив, в котором для получения размера нужно писать a.length, а для получения элемента a.at(i).