ТЕОРЕТИЧЕСКОЕ ВВЕДЕНИЕ
Формат АТД
При создании любой программной системы, в основе которой лежит некоторая программно-управляемая структура данных, базируется на понятии абстрактного типа данных (АТД). АТД задает область значений, представление структуры данных и набор операций к данным.
Для описания АТД используется формат, который включает заголовок с именем АТД, описание типа данных и список операций. Формат АТД служит не только основой для проектирования программной системы. Не менее важен формат и для точного описания интерфейса, предоставляемого пользователю - программисту для управления структурой данных. Поэтому формулировки формата АТД должны быть исчерпывающими, точными и краткими. В описании формата АТД должны использоваться, понятия, объекты и переменные, использующиеся только на уровне интерфейса к структуре данных. На уровень интерфейса не должны выноситься детали внутренней реализации структуры данных и операций управления ею.
Для каждой операции в формате АТД определяются входные значения, предусловия, применяемые к данным до того, как операция может быть выполнена, процесс, который выполняется операцией. После выполнения операции определяются выходные значения и постусловия, указывающие на любые изменения данных.
Большинство АТД имеют инициализирующую операцию, которая присваивает начальные значения данным. В С++ такой инициализатор называется конструктором.
АТД имя.
Общая характеристика типа данных
ДАННЫЕ:
Описание общих параметров.
Описание структуры данных.
ОПЕРАЦИИ:
Конструктор:
Вход: данные от пользователя.
Начальные значения: данные для инициализации.
Процесс: инициализация данных.
Постусловие: состояние структуры и параметров после инициализации.
Операция:
Вход: данные от пользователя.
Предусловия: необходимое состояние структуры данных перед выполнением операции.
Процесс: действия, выполняемые над данными.
Выход: данные, возвращаемые пользователю.
Постусловие: состояние структуры после выполнения операции.
Операция:
...
Операция:
...
КОНЕЦ АТД.
Примечание. Надёжный массив в отличие от статического массива может изменять свой размер во время выполнения программы. Как АТД, надёжный массив наделяется операциями: инициализации массива с исходным размером (конструктор), опрос текущего размера, изменение текущего размера, доступ к элементу массива по индексу. Операция индексации надёжного массива наделяется новым свойством - проверкой границ массива. Если указанный индекс находится вне текущего размера массива, операция генерирует сообщение об ошибке.
Вариант №2. "Линейные коллекции данных"
Задание к работе
Цели работы: Освоение технологии реализации позиционных, линейных коллекций на примере АТД "Список". Освоение методики тестирования трудоёмкости реализации коллекций.
Задание к работе:
1. Спроектировать, реализовать и провести тестовые испытания АТД "Список" для коллекции, содержащей данные произвольного типа. Тип данных задаётся клиентской программой.
Интерфейс АТД "Список" включает следующие операции:
· опрос размера списка,
· очистка списка,
· проверка списка на пустоту,
· опрос наличия элемента с заданным значением,
· доступ к значению элемента с заданным номером в списке,
· получение позиции в списке элемента с заданным значением,
· включение нового элемента в позицию с заданным номером,
· удаление элемента из позиции с заданным номером,
· итератор для доступа к элементам списка с операциями:
1) установка на начало списка,
2) проверка конца списка,
3) доступ к значению текущего элемента,
4) переход к следующему элементу списка,
5) переход к предыдущему элементу списка (для списков на базе массива или двусвязных структур),
Для тестирования эффективности операций интерфейс АТД "Список" включает дополнительную операцию.
· опрос числа элементов списка, просмотренных операцией.
2. Выполнить отладку и тестирование всех операций АТД "Список" с помощью меню операций.
3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов.
4. Провести анализ экспериментальных показателей трудоёмкости операций.
5. Пояснительная записка к работе. Записка должна содержать следующие пункты:
1) титульный лист,
2) цель работы,
3) общее задание (пункты 1 - 5) и вариант задания,
4) формат АТД,
5) определение шаблонного класса для коллекции "Список", предназначенное для клиентской программы,
6) описание методики тестирования трудоёмкости операций,
7) таблицы и графики с полученными оценками трудоёмкости операций для среднего случая функционирования АТД. Должны быть приведены графики среднего числа просмотренных элементов для операций поиска, вставки и удаления (графики совмещены в одной системе координат),
8) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,
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 с.