Абстрактные типы данных в С++ (ADT)

1. Тема 15: Абстрактные типы данных в С++ (ADT)

2.

Один из наиболее важных этапов разработки программ
заключается в выборе эффективного способа
представления данных. Во многих случаях
недостаточно объявить простую переменную или
массив. С++ имеет встроенный тип struct,
представляющий запись. Структура это особый случай
класса, в котором все поля являются открытыми.
Пример
struct student {
int id;
char name [20]; };
struct student s= { 567, “Пупкин Вася”}

3.

Тип определяет два типа информации:
набор свойств и набор операций.
Предположим, что нужно определить
новый тип данных, для этого:
необходимо обеспечить способ хранения
данных, возможно разработав структуру.
необходимо обеспечить способы
манипулирования данными.

4. Трехэтапный процесс перехода от абстрактного понятия к конкретной реализации:

1. Создайте абстрактное описание
свойств типа и операций, которые можно
выполнять с данным типом. Это описание
не должно быть связано с конкретной
реализацией. Оно даже не должно быть
связано с конкретным языком
программирования. Такое формальное
абстрактное описание называется
абстрактным типом данных(ADT).

5. Трехэтапный процесс перехода от абстрактного понятия к конкретной реализации:

2. Разработайте программный интерфейс,
реализующий ADT, т.е. укажите, как
следует хранить данные, и опишите
набор функций, выполняющий требуемые
операции.

6. Трехэтапный процесс перехода от абстрактного понятия к конкретной реализации:

3. Создайте код для реализации
интерфейса. Конечно, этот этап имеет
большое значение, но программисту,
который использует новый тип, не
обязательно знать подробности
реализации.

7. Некоторые операции с абстрактными типами

Инициализация пустого списка.
Добавление элемента в конец списка.
Определение того, является ли список пустым.
Определение того, является ли список
заполненным.
Определение количества элементов в списке.
Обращение к каждому элементу списка для
выполнения какого-либо действия.
Вставка элемента в любое место списка.
Удаление элемента из списка.
Замена одного элемента списка другим.
Поиск элемента в списке

8. Краткое описание типа

Имя типа:
Simple List ( Простой список )
Свойства типа:Может содержать
последовательность элементов.
Операции с типом:
Инициализация пустого списка. Определение
того, является ли список пустым.
Определение того, является ли список
заполненным.
Определение количества элементов в списке.
Добавление элемента в конец списка.
Перемещение по списку с обработкой каждого
элемента списка.