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

ТЕОРЕТИЧЕСКОЕ ВВЕДЕНИЕ

Формат АТД

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

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

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

Большинство АТД имеют инициализирующую операцию, которая присваивает начальные значения данным. В С++ такой инициализатор называется конструктором.

АТД имя.
Общая характеристика типа данных

ДАННЫЕ:
Описание общих параметров.
Описание структуры данных.

ОПЕРАЦИИ:
Конструктор:
Вход: данные от пользователя.
Начальные значения: данные для инициализации.
Процесс: инициализация данных.
Постусловие: состояние структуры и параметров после инициализации.

Операция:
Вход: данные от пользователя.
Предусловия: необходимое состояние структуры данных перед выполнением операции.
Процесс: действия, выполняемые над данными.
Выход: данные, возвращаемые пользователю.
Постусловие: состояние структуры после выполнения операции.

Операция:

Операция:

КОНЕЦ АТД.

Примечание. Надёжный массив в отличие от статического массива может изменять свой размер во время выполнения программы. Как АТД, надёжный массив наделяется операциями: инициализации массива с исходным размером (конструктор), опрос текущего размера, изменение текущего размера, доступ к элементу массива по индексу. Операция индексации надёжного массива наделяется новым свойством — проверкой границ массива. Если указанный индекс находится вне текущего размера массива, операция генерирует сообщение об ошибке.

Вариант №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 с.

Арифметика указателей. Указатели и массивы. Массив это указатель. C++ для начинающих. Урок #47


Похожие статьи.

Понравилась статья? Поделиться с друзьями: