Постановка задачи.

Введение

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

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

В рамках лабораторных работ по дисциплине «Структуры и алгоритмы обработки данных» используется технология создания коллекций данных, предназначенных для использования в больших задачах. Коллекция должна обеспечивать хранение данных, объём которых меняется в широких пределах. Набор операций, выполняемых над объектами, хранящимися в коллекции, должен быть достаточным, чтобы удовлетворить запросы широкого круга задач, использующих коллекцию.

Технология проектирования и реализации коллекций данных.

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

· постановка задачи,

· разработка структур данных и алгоритмов,

· кодирование,

· отладка и тестирование,

· сопровождение.

Постановка задачи.

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

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

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

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

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

АТД «НАДЁЖНЫЙ МАССИВ»

Общая характеристика:

Массив данных указанного типа Т. Массив имеет переменную размерность. При создании массив имеет исходный, минимальный размер size₀. Массив может увеличивать и уменьшать свою размерность. Операция индексирования массива выполняет проверку соответствия индекса текущему размеру массива size.

ДАННЫЕ:

Параметры:

Минимальный размер массива size₀

Текущий размер массива size

Структура хранения коллекции:

Динамический массив элементов указанного типа Т – T array [ size ]

ОПЕРАЦИИ:

Конструктор

Вход: исходный, минимальный размер массива size₀

Начальные значения: текущий размер массива size = size₀

Процесс: Создание динамического массива T array [ size ] с размером size = size₀

Постусловия: Создан массив с размером size = size₀

Опрос размера массива

Вход: нет

Предусловия: нет

Процесс: чтение текущего размера size

Выход: текущий размер size

Постусловия: нет

Изменение размера массива

Вход: новый размер массива size_n

Предусловия: size_n size₀,

Процесс: выделение памяти указанного размера size_n, копирование size или size_n значений из старого массива в новый массив

Выход: TRUE – массив изменён, FALSE - массив не изменён при невыполнении предусловия

Постусловия:

массив содержит size значений старого массива, если size_n> size,

массив содержит size_n значений старого массива, если size_n< size,

текущий размер массива size = size_n

Операция индексирования

Вход: значение индекса i

Предусловия: 0 i size- 1

Процесс: вычисление адреса элемента массива array [ i ]

Выход: ссылка на элемент массива array [ i ]

Постусловия: генерация сообщения об ошибке при невыполнении предусловия

КОНЕЦ АТД

Дата добавления: 2015-11-04