ТЕОРЕТИЧЕСКОЕ ВВЕДЕНИЕ
Формат АТД
При создании любой программной системы, в основе которой лежит некоторая программно-управляемая структура данных, базируется на понятии абстрактного типа данных (АТД). АТД задает область значений, представление структуры данных и набор операций к данным.
Для описания АТД используется формат, который включает заголовок с именем АТД, описание типа данных и список операций. Формат АТД служит не только основой для проектирования программной системы. Не менее важен формат и для точного описания интерфейса, предоставляемого пользователю — программисту для управления структурой данных. Поэтому формулировки формата АТД должны быть исчерпывающими, точными и краткими. В описании формата АТД должны использоваться, понятия, объекты и переменные, использующиеся только на уровне интерфейса к структуре данных. На уровень интерфейса не должны выноситься детали внутренней реализации структуры данных и операций управления ею.
Для каждой операции в формате АТД определяются входные значения, предусловия, применяемые к данным до того, как операция может быть выполнена, процесс, который выполняется операцией. После выполнения операции определяются выходные значения и постусловия, указывающие на любые изменения данных.
Большинство АТД имеют инициализирующую операцию, которая присваивает начальные значения данным. В С++ такой инициализатор называется конструктором.
АТД имя.
Общая характеристика типа данных
ДАННЫЕ:
Описание общих параметров.
Описание структуры данных.
ОПЕРАЦИИ:
Конструктор:
Вход: данные от пользователя.
Начальные значения: данные для инициализации.
Процесс: инициализация данных.
Постусловие: состояние структуры и параметров после инициализации.
Операция:
Вход: данные от пользователя.
Предусловия: необходимое состояние структуры данных перед выполнением операции.
Процесс: действия, выполняемые над данными.
Выход: данные, возвращаемые пользователю.
Постусловие: состояние структуры после выполнения операции.
Операция:
…
Операция:
…
КОНЕЦ АТД.
Примечание. Надёжный массив в отличие от статического массива может изменять свой размер во время выполнения программы. Как АТД, надёжный массив наделяется операциями: инициализации массива с исходным размером (конструктор), опрос текущего размера, изменение текущего размера, доступ к элементу массива по индексу. Операция индексации надёжного массива наделяется новым свойством — проверкой границ массива. Если указанный индекс находится вне текущего размера массива, операция генерирует сообщение об ошибке.
Вариант №2. Линейные коллекции данных
Задание к работе
Цели работы: Освоение технологии реализации позиционных, линейных коллекций на примере АТД Список. Освоение методики тестирования трудоёмкости реализации коллекций.
Задание к работе:
1. Спроектировать, реализовать и провести тестовые испытания АТД Список для коллекции, содержащей данные произвольного типа. Тип данных задаётся клиентской программой.
Интерфейс АТД Список включает следующие операции:
- опрос размера списка,
- очистка списка,
- проверка списка на пустоту,
- опрос наличия элемента с заданным значением,
- доступ к значению элемента с заданным номером в списке,
- получение позиции в списке элемента с заданным значением,
- включение нового элемента в позицию с заданным номером,
- удаление элемента из позиции с заданным номером,
- итератор для доступа к элементам списка с операциями:
1) установка на начало списка,
2) проверка конца списка,
3) доступ к значению текущего элемента,
4) переход к следующему элементу списка,
5) переход к предыдущему элементу списка (для списков на базе массива или двусвязных структур),
Для тестирования эффективности операций интерфейс АТД Список включает дополнительную операцию.
- опрос числа элементов списка, просмотренных операцией.
2. Выполнить отладку и тестирование всех операций АТД Список с помощью меню операций.
3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов.
4. Провести анализ экспериментальных показателей трудоёмкости операций.
5. Пояснительная записка к работе. Записка должна содержать следующие пункты:
1) титульный лист,
2) цель работы,
3) общее задание (пункты 1 — 5) и вариант задания,
4) формат АТД,
5) определение шаблонного класса для коллекции Список, предназначенное для клиентской программы,
6) описание методики тестирования трудоёмкости операций,
7) таблицы и графики с полученными оценками трудоёмкости операций для среднего случая функционирования АТД. Должны быть приведены графики среднего числа просмотренных элементов для операций поиска, вставки и удаления (графики совмещены в одной системе координат),
сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,
9) выводы,
10) список использованной литературы,
11) приложение с текстами программ:
- полное определение класса и текстов методов класса,
- текст программы тестирования трудоёмкости операций.
Варианты задания
Структура данных — кольцевая, односвязная, на базе адресных указателей, с использованием фиктивного элемента.
Методические указания по выполнению задания
1. Для АТД Список разрабатываются формат АТД и шаблонный класс — контейнер.
2. Для тестирования разработанного класса — контейнера разрабатываются две программы: программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.
3. Тестирование операций через меню выполняется для списка небольшого размера (до 20 элементов). Тип данных и для некоторых вариантов размер списка задаются с клавиатуры перед началом тестирования. После выполнения операций необходимо вывести на экран содержимое списка с помощью итератора.
4. Перед тестированием трудоёмкости операций задаются тип и размер списка. Размер списка варьируется в пределах от 10 до 100 000 элементов. После тестирования на экран выводятся размер списка и средняя трудоёмкость операций поиска, вставки и удаления (среднее число просмотренных элементов списка).
Литература
1. Альфред Ахо, Джон Э. Хопкрофт, Д. Ульман Структуры данных и алгоритмы. — М. — СПб — Киев: Вильямс, 2000 г. — 384 с.
2. Н. Вирт Алгоритмы + структуры данных = программы. — М.: Мир, 1985 г. — 406 с.
3. Фрэнк М. Каррано, Джанет Дж. Причард. Абстракция данных и решение задач на С++. Стены и зеркала. — М. — СПб — Киев: Вильямс, 2003 г. — 848 с.
4. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. — М: Мир, 1976 г. (переиздание — М., Изд. Вильямс, 2000 г.) — 735 с.
5. Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. — М: Мир, 1978 г. (переиздание — М., Изд. Изд. Вильямс, 2000 г.) — 844 с.
6. Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Анализ и построение. — М: БИНОМ, 2000 г. — 960 с.
7. Дж. Макконелл. Анализ алгоритмов. Вводный курс. — М: Техносфера, 2002 г. — 304 с.
8. Роберт Сэджвик. Фундаментальные алгоритмы на С++. Части 1-4. — М: DiaSoft, 2001 г. — 688 с.
9. Уильям Топп, Уильям Форд. Структуры данных в С++. — М: Бином, 2000 г. — 816 с.
10. Хезфилд Р., Кирби Л. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. — Киев: ДиаСофт, 2001г. — 736 с.