Создание программной системы, в основе которой лежит некоторая программно управляемая структура данных, базируется на понятии абстрактного типа данных (АТД). АТД задает представление структуры данных и набор операций над данными, область значений, хранящихся в структуре.
Для описания АТД используется формат, который включает заголовок с именем АТД, описание типа структуры данных и список операций. Формат АТД служит не только основой для проектирования программной системы. Не менее важен формат и для точного описания интерфейса, предоставляемого пользователю – программисту для управления структурой. Поэтому формулировки формата АТД должны быть исчерпывающими, точными и краткими. В описании формата АТД должны использоваться понятия, объекты и переменные, вынесенные на уровень интерфейса со структурой данных. На уровень интерфейса не должны фигурировать детали внутренней реализации структуры данных и операций управления ею.
Для каждой операции в формате АТД определяются входные значения, предусловия, при которых операция может быть выполнена, процесс, который выполняется операцией. После выполнения операции определяются выходные значения и постусловия, указывающие на любые изменения данных или порождаемые структурой события.
Большинство АТД имеют инициализирующую операцию, которая исходное состояние структуры. В С++ такой инициализатор называется конструктором.
АТД – формат.
АТД имя.
Данные:
Описание структуры данных.
Операции:
Конструктор:
Начальные значения: данные для инициализации.
Процесс: инициализация данных.
Операция:
Вход: данные от пользователя.
Предусловия: необходимое состояние структуры данных перед выполнением операции.
Процесс: действия, выполняемые над данными.
Выход: данные, возвращаемые пользователю.
Постусловие: состояние структуры после выполнения операции.
Операция:
……
Операция:
…..
Конец АТД.
Язык С++ поддерживает определяемый АТД с помощью классов.
Класс состоит из членов, которые включают данные и операции, называемые методами.
Класс содержит открытую (public) и закрытую (private) части. Открытая часть описывает интерфейс , позволяющий манипулировать объектами типа класса. Закрытая часть содержит данные и внутренние операции.
Класс инкапсулирует информацию, связывая вместе члены и методы в единое целое – объект. Структура класса скрывает реализацию деталей и ограничивает внешний доступ к данным и операциям.
Данные обычно скрыты в закрытой части класса и модифицируются только методами класса.
Класс С++ сначала вводится объявлением этого класса, содержащим определение членов данных и объявление прототипов методов. Фактическое определение методов дается в реализации класса, отдельной от объявления класса.
Пример формата АТД – список.
АТД List
Структура данных: динамический односвязный список элементов на базе адресных указателей,
Размерсписка: количество значений, находящихся в данный момент в списке,
Область значений в списке: любые значения, кроме заданного пользователем
nil – значения.
Операции:
Начальные значения: nil–значение данных.
Процесс: создание пустого списка, установление размера списка в 0.
Вход: нет.
Предусловие: нет.
Процесс: чтение размера списка.
Выход: размер списка.
Постусловие: нет.
Вход: нет.
Предусловие: нет.
Процесс: проверка размера списка.
Выход: логическое значение true(1), если список пуст;
логическое значение false(0), если список не пуст.
Постусловие: нет.
Вход: нет.
Предусловие: нет.
Процесс: удаление всех значений из списка и установка размера списка в 0.
Выход: нет.
Постусловие: список пустой.
Вход: значение, которое нужно найти в списке.
Предусловие: нет.
Процесс: сканирование списка для нахождения указанного значения.
Выход: логическое значение true(1), если заданное значение найдено,
логическое значение false(0), если заданное значение не найдено.
Постусловие: нет.
Вход: значение, номер позиции в списке для вставки.
Предусловие:
значение 
nil-значению,
0 
номер позиции размер
списка
Процесс: добавление значения в указанную позицию списка. Не выполняется никакое действие, если не выполнено предусловие.
Выход: логическое значение true(1), если значение вставлено,
логическое значение false(0), если значение не вставлено.
Постусловие: список имеет новый элемент с указанным значением в указанной позиции; его размер увеличен на 1.
Вход: значение, которое нужно удалить из списка.
Предусловие: нет.
Процесс: сканирование списка и удаление первого найденного указанного значения из списка. Не выполнятся никакое действие, если заданного значения в списке нет.
Выход: нет
Постусловие: если указанное значение найдено, размер списка уменьшается на 1.
Вход: значение в списке,
Предусловие: нет.
Процесс: сканирование списка для нахождения указанного значения.
Выход: номер первого вхождения в список указанного значения.
-1, если значения в списке нет.
Постусловие: нет.
Вход: номер позиции в списке,
Предусловие: 0 номер
позиции размер списка.
Процесс: чтение значения из списка, с указанным номером позиции. Не выполняется никакое действие, если не выполнено предусловие.
Выход: значение элемента с указанным номером позиции,
nil-значение, если не выполнено предусловие.
Постусловие: нет.
Конец АТД List.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
