Пример разработки абстрактного типа данных

АТД.

Пример разработки абстрактного типа данных

Рассмотрим пример разработки абстрактного типа данных (АТД ). Представьте себе, что мы создаем компьютерный вариант записной книги для записи деловых встреч, охватывающий один год. Допустим, что деловую встречу можно назначать только с 8 утра до 5 вечера. Мы хотим, чтобы система хранила краткое описание деловой встречи, а также ее дату и время.
Для того чтобы решить эту проблему, можно определить абстрактный тип данных

Записная книжка.

К данным этого АТД относятся дата, время и цель встречи. Какие операции можно выполнять с данными этого типа? Очевидно, нужно предусмотреть следующие две операции.
Назначить встречу на определенную дату и время, указав ее цель. (Следует быть осторожным, чтобы не назначить встречу на уже занятое время)
 Отменить встречу, назначенную на определенную дату и время.
В дополнение к этим операциям можно предусмотреть еще несколько операций.
 Запросить, назначена ли встреча на заданное время.
 Определить цель встречи, назначенной на заданное время.
Кроме того, в абстрактных типах данных обычно определяются операции инициализации и уничтожения. Еще раз обратите внимание на то, что приложения, использующие операции над абстрактными типами данных, можно разрабатывать, ничего не зная о деталях реализации АТД.
АТД на основе других АТД. В обоихсистемах, рассмотренных выше, нужно было работать с датами. В примере, связанном с записной книжкой, к дате добавилось время. В языке С есть структура, позволяющая хранить время и дату. Она определена в файле time.h. Кроме того, можно разрабатывать собственные абстрактные типы данных, позволяющие представлять эти элементы в объектно-ориентированном виде. На практике часто приходится определять один АТД через другой.
АТД можно использовать при реализации другого АТД
В последнем примере описывается АТД, для реализации которого используются другие АТД. Допустим, нам нужно разработать базу данных для хранения рецептов. Эту базу можно считать абстрактным типом данных.
На этом этапе проектирования не указываются никакие подробности, например, где именно операция размещает рецепт.
Теперь представьте себе, что нам нужно написать функцию, уточняющую рецепт, полученный из базы данных. Например, рецепт может быть рассчитан на Х человек, а нам нужно уточнить его для А персон. Допустим, в рецепт входят разные измерения, скажем, 212 стакана, 1 столовая ложка и 4 чайной ложки. Как видим, эти величины представляют собой смешанные числа — целые и дроби, — измеренные в стаканах, а также столовых и чайных ложках.
Поскольку мы планируем использовать для этой цели язык С, в котором нет отдельного типа для дробных чисел, а арифметика с плавающей точкой не точна, нам потребуется другой абстрактный тип данных под названием Дробь. Его операции должны включать в себя сложение, вычитание, умножение и деление дробей.
Более того, можно предусмотреть операции для преобразования смешанных чисел в дроби и наоборот, если это возможно.
Единица измерения можно использовать АТД – ” Дробь”.
Аксиома — это математическое правило
Аксиомы
Предыдущие спецификации АТД были сформулированы довольно нечетко. Например, они апеллируют к интуиции, предполагая, будто программисту известно, что означает выражение элемент находится на i-1 позиции абстрактного списка. Однако некоторые абстрактные типы данных гораздо сложнее списков и гораздо труднее поддаются интуитивному пониманию. Для таких АТД следует применять более строгий метод. При описании их операций необходимо задать совокупность математических правил, называемых аксиомами (axioms), которые точно определяют смысл каждой операции.
Фактически аксиома — это инвариант (истинное утверждение) операции АТД. Например, известны аксиомы алгебраических операций; в частности операции умножения формулируются такие аксиомы. Эти правила, или аксиомы, истинны для любых чисел а, и с и описывают поведение оператора умножения х.
Совершенно аналогично можно задать совокупность аксиом, полностью описывающих свойства операций над абстрактным списком. Например, высказывание:”Вновь созданный список всегда пуст представляет собой аксиому, поскольку это утверждение истинно для любого вновь созданного списка”. В терминах операций над абстрактным списком эту аксиому можно выразить так:

“Значение выражения равно true . “. Это означает, что список пуст. Высказывание:”Если вы вставляете элемент х на i-ю позицию абстрактного списка, то результатом операции извлечения i-го элемента будет элемент х истинно для любых списков, поэтому его можно считать аксиомой”. Это означает, что операция извлекает из i-й позиции списка элемент х, который был вставлен туда операцией. Для упрощения обозначений аргумент пропускается, а операция выполняется так, как если бы она была функцией, возвращающей какое-то значение.

Совокупность аксиом не заменяет собой постусловий операций АТД. Например, приведенные аксиомы никак не описывают поведение операции при попытке вставить элемент в 50-ю позицию списка, состоящего из двух элементов. Для того чтобы справиться с этой ситуацией, необходимо предусмотреть в предусловии операции ограничение.
Еще один способ, который мы применим при реализации абстрактного списка в этой статье, не связан с ограничениями на переменную. Просто, когда значение переменной выходит за пределы допустимого диапазона, параметру присваивается значение false. Таким образом, для полного описания операций над абстрактным типом данных необходимы как аксиомы, так и пред- и постусловия. Аксиомы позволяют вычислять результат.

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

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

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

В языке С классы представляют собой новые типы данных, экземплярами которых являются объекты. Синтаксис класса напоминает синтаксис структуры в языке С. Как и структура, класс может содержать данные-члены. Обращаться к этим данным можно точно так же, как и к данным-членам структуры. Для этого указывается экземпляр класса и имя его члена.
По умолчанию все члены класса являются закрытыми (private) — программа не имеет к ним прямого доступа, пока вы не объявите их открытыми (public). Однако реализации функций-членов класса имеют доступ к любым закрытым членам этого класса. В противоположность этому все члены структуры по умолчанию являются открытыми, пока вы не объявите их закрытыми.
Поскольку структуры в языке С также могут содержать функции-члены, класс и структура работают одинаково, если в них явно объявлены открытые и закрытые члены. Несмотря на то что ключевые слова struct и class являются взаимозаменяемыми, делать этого не следует. Структура подходит для хранения данных разных типов, когда не нужно определять новый тип данных. В этой статье структуры используются только для хранения данных и могут иногда содержать одну функцию-член для своей инициализации. Класс нужно применять при реализации АТД для определения нового типа данных. Ключевое слово class используется в статье только для определения типов объектов, причем открытые и закрытые разделы класса всегда указываются явно.