1.2. Абстрактные типы данных

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

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

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

Определение абстрактного типа данных

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

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

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

1. Сделать список пустым.

2. Выбрать первый элемент списка и, если список пустой, возвратить значение null.

3. Выбрать следующий элемент списка и возвратить значение null, если следующего элемента нет.

4. Вставить целое число в список.

Возможно применение различных структур данных, с помощью которых можно эффективно выполнить описанные действия. (Подробно структуры данных будут рассмотрены в теме 2.) Если в листинге 1.3 заменить соответствующие операторы выражениями

MAKENULL(newcJr);

w:= FIRST(newcJr);

w:= NEXT(newcfr);

INSERT(v, newclr);

то будет понятен один из основных аспектов (и преимуществ) абстрактных типов данных. Можно реализовать тип данных любым способом, а программы, использующие объекты этого типа, не зависят от способа реализации типа - за это отвечают процедуры, реализующие операторы для этого типа данных.

Вернемся к абстрактному типу данных GRAPH (Граф). Для объектов этого типа необходимы операторы, которые выполняют следующие действия.

1. Выбирают первую незакрашенную вершину.

2. Проверяют, существует ли ребро между двумя вершинами.

3. Помечают вершину цветом.

4. Выбирают следующую незакрашенную вершину.

Очевидно, что вне поля зрения процедуры greedy остаются и другие операторы, такие как вставка вершин и ребер в граф или помечающие все вершины графа как незакрашенные. Различные структуры данных, поддерживающие этот тип данных, будут рассмотрены в темах 6 и 7.

Необходимо особо подчеркнуть, что количество операторов, применяемых к объектам данной математической модели, не ограничено. Каждый набор операторов определяет отдельный АТД. Вот примеры операторов, которые можно определить для абстрактного типа данных SET (Множество).

1. MAKENULL(A), Эта процедура делает множество А пустым множеством.

2. UNION(A, В, С). Эта процедура имеет два "входных" аргумента, множества А и В, и присваивает объединение этих множеств "выходному" аргументу - множеству С.

3. SIZE(A). Эта функция имеет аргумент-множество А и возвращает объект целого типа, равный количеству элементов множества А. Термин реализация АТД подразумевает следующее: перевод в операторы языка программирования объявлений, определяющие переменные этого абстрактного типа данных, плюс процедуры для каждого оператора, выполняемого над объектами АТД. Реализация зависит от структуры данных, представляющих АТД. Каждая структура данных строится на основе базовых типов данных применяемого языка программирования, используя доступные в этом языке средства структурирования данных. Структуры массивов и записей - два важных средства структурирования данных, возможных в языке Pascal. Например, одной из возможных реализаций переменной S типа SET может служить массив, содержащий элементы множества S.

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

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

Абстрактным принято называть тип данных, в явном виде не имеющийся в языке программирования, в этом смысле это понятие относительное - тип данных, отсутствующий в одном языке программирования, может присутствовать в другом.

Абстрактный тип данных (АТД) определяется независимо от способа его реализации:

    множеством возможных значений этого типа,

    и набором операций со значениями этого типа.

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

    способ представления значений этого типа,

    и реализацию операций со значениями этого типа.

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

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

В современных «практических языках программирования» для конструирования АТД обычно используется предопределенная операция конструирования типов class , которая дает разработчику-программисту не только средства группировки данных и операций (с этими данными) в единое целое, но и средства инкапсуляции, наследования и полиморфизма для управления способами конструирования и доступа к таким данным. Отметим, что класс описывает одну возможную реализацию АТД, отображение класса в АТД выражается функцией абстракции, но обратное отношение, обычно, не является функциональным, реализаций одного и того же АТД может быть несколько.

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

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

    Сорт и сигнатура – эти понятия позволяют расклассифицировать и элементы носителя и операции с ними по их типам (для операций - по типам их аргументов и возвращаемого значения).

    Предикаты – отношения на элементах носителя. Это позволяет определять область возможных значений наложением ограничений (требований) на допустимые значения, а также в естественной трактовке работать с произвольными логическими выражениями, не принуждая интерпретировать их как функции принадлежности для множеств или как многозначные операции.

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

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

Но все же мы будем различать эти два понятия, учитывая:

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

    Структура данных - скорее некоторая схема организации данных и управления ими, которая предполагает соответствующие конкретизации при ее использовании в конкретных ситуациях при решении конкретных задач.

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

Тип данных описывает множество объектов со схожими свойствами. Все традиционные языки программирования используют набор базовых типов данных (real, integer, string, character). Базовые типы данных подчиняются предопределенному набору операций. Например, базовый тип данных integer позволяет выполнять такие операции, как сложение, вычитание, умножение, деление.

В традиционные языки программирования включаются конструкторы типов, самым распространенным из которых является конструктор record. Например, для записи типа CUSTOMER можно определить поля данных. Запись CUSTOMER будет представлять собой новый тип данных, в котором будет храниться информация о клиенте, можно напрямую получать доступ к этой структуре данных, ссылаясь на имена полей. Над записью можно выполнять такие операции, как WRITE, READ, DELETE, UPDATE. Для базовых типов данных определить новые операции нельзя.

Как и базовые типы данных, абстрактные типы данных (ATD, abstract data types) описывают множество схожих объектов. Есть отличия ATD от традиционного типа данных:

· операции под ATD определяются пользователем;

· ATD не допускают непосредственного доступа к внутреннему представлению данных и реализации методов.

В некоторых ОО-системах (например, Smalltalk) базовые типы данных реализованы как абстрактные.

Для создания абстрактного типа данных необходимо обеспечить:

· имя типа;

· представление данных или переменные экземпляра объекта, принадлежащего ATD; каждая переменная экземпляра имеет тип данных, который может быть либо базовым типом, либо другим ATD;

· операции под ATD и ограничения реализуются с помощью методов.

Определение ATD перестраивает определение класса. В некоторых ОО-системах для различения классов и типов при ссылки на структуры данных и методы класса используется ключевое слово type, а при ссылке на набор экземпляров объекта - ключевой слово class. Тип (type) более статичное понятие, а class связан в основном со временем выполнения. Отличие ОО-класса от ОО-типа можно проиллюстрировать на примере. Предположим, имеется шаблон для конструктора. К шаблону прилагается описание его структуры, а также инструкция по его использованию. Этот шаблон и есть описание типа (type definition). Комплект сделанных с помощью шаблона реальных изделий, каждое из которых имеет уникальный номер (или OID), составляет класс (class).

ATD совместно с наследованием позволяют создавать сложные объекты. Сложный объект (complex object) формируется путем комбинации других объектов, находящихся в сложных взаимосвязях друг с другом. Пример сложного объекта можно найти в системах безопасности, где используются различные типы данных:

1. стандартные (табличные) данные о сотруднике (ФИО, Таб. № и т.д.);

2. битовая карта для хранения фотографии сотрудника;

Возможность относительно просто работать с такой сложной средой данных повышает значение ОО-систем на современном рынке баз данных.

Доброго времени суток, хабравчане!

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

Введение

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

Что же означает слово “абстрактный”? В первую очередь понятие “абстрактность” означет сосредоточение внимания на чем-то важном и, при этом, нам нужно отвлечься от неважных, на данный момент, деталей. Определение абстрактности хорошо раскрыто в книге Гради Буча (“Grady Booch”). Звучит определение так:

Абстракция – это выделение и придание совокупности объектов общих свойств, которые определяют их концепутальные границы и отличают от всех других видов объектов.
Иными словами, абстракция позволяет “пролить свет” на нужные нам данные объектов и, при этом, “затенить” те данные, которые нам не важны.

Итак, что же будет, если слить понятия “тип данных” и “абстракция” воедино? Мы получим тип данных, который предоставляет нам некий набор операций, обеспечивающих поведение объектов этого типа данных, а также этот тип данных будет скрывать те данные, с помощью которых реализовано данное поведение. Отсюда, приходим к понятию АТД:

АТД – это такой тип данных, который скрывает свою внутреннюю реализацию от клиентов.
Удивительно то, что путем применения абстракции АТД позволяет нам не задумываться над низкоуровневыми деталями реализации, а работать с высокоуровневой сущностью реального мира (Стив Макконнелл).

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

Преимущества АТД

Использование АТД имеет массу преимуществ (все описанные преимущества можно найти в книге Стива Макконнелла «Совершенный код”):

  • Инкапсуляция деталей реализации.
    Это означает, что единожды инкапсулировав детали реализации работы АТД мы предоставляем клиенту интерфейс, при помощи которого он может взаимодействовать с АТД. Изменив детали реализации, представление клиентов о работе АТД не изменится.
  • Снижение сложности.
    Путем абстрагирования от деталей реализации, мы сосредатачиваемся на интерфейсе, т.е на том, что может делать АТД, а не на том как это делается. Более того, АТД позволяет нам работать с сущностью реального мира.
  • Ограничение области использования данных.
    Используя АТД мы можем быть уверены, что данные, представляющие внутреннюю структуру АТД не будут зависеть от других участков кода. При этом реализуется “независимость” АТД.
  • Высокая информативность интерфейса.
    АТД позволяет представить весь интерфес в терминах сущностей предметной области, что, согласитесь, повышает удобочитаемость и информативность интерфейса.

Стив Макконнелл рекомендует представлять в виде АТД низкоуровнеые типы данных, такие как стек или список. Спросите себя, что представляет собой этот список. Если он представляет список сотрудников банка, то и рассматривайте АТД как список сотрудников банка.

Итак, мы разобрались, что такое АТД и назвали преимущества его применения. Теперь стоит отметить, что при разработке классов в ООП следует думать, в первую очередь, об АТД. При этом, как сказал Стив МакКоннелл, Вы программируете не на языке, а с помощью языка. Т.е Вы будете программировать выходя за рамки языка, не ограничиваясь мыслями в терминах массивов или простых типов данных. Вместо этого Вы будете думать на высоком уровне абстракции (например, в терминах электронных таблицах или списков сотрудников). Класс – это не что иное как дополнение и способ реализации концепции АТД. Мы можем даже представить класс в виде формулы:
Класс = АТД + Наследование + Полиморфизм.
Так почему же следут думать об АТД, при разработке классов. Потому что, сперва мы должны решить какие операции будут составлять интерфейс будущего класса, какие данные скрыть, а к каким предоставить открытый доступ. Мы должны подумать об обеспечении высокой информативности интерфейса, легкости оптимизации и проверки кода, а также о том, как бы нам предоставить правильную абстракцию, чтобы можно было думать о сущностях реального мира, а не о низкоуровнеых деталях реализации. Я считаю, что именно после определения АТД мы должны думать о вопросах наследования и полиморфизма.

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

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

Использованные источники:

Стив Макконнелл – “Совершенный код”;
Роберт Седжвик – «Алгоритмы на Java».

Последнее обновление: 04.08.2018

Кроме обычных классов в C# есть абстрактные классы . Абстрактный класс похож на обычный класс. Он также может иметь переменные, методы, конструкторы, свойства. Единственное, что при определении абстрактных классов используется ключевое слово abstract :

Abstract class Human { public int Length { get; set; } public double Weight { get; set; } }

Но главное отличие состоит в том, что мы не можем использовать конструктор абстрактного класса для создания его объекта. Например, следующим образом:

Human h = new Human();

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

Abstract class Person { public string Name { get; set; } public Person(string name) { Name = name; } public void Display() { Console.WriteLine(Name); } } class Client: Person { public int Sum { get; set; } // сумма на счету public Client(string name, int sum) : base(name) { Sum = sum; } } class Employee: Person { public string Position { get; set; } // должность public Employee(string name, string position) : base(name) { Position = position; } }

Затем мы сможем использовать эти классы:

Client client = new Client("Tom", 500); Employee employee = new Employee ("Bob", "Apple"); client.Display(); employee.Display();

Или даже так:

Person client = new Client("Tom", 500); Person employee = new Employee ("Bob", "Операционист");

Но мы НЕ можем создать объект Person, используя конструктор класса Person:

Person person = new Person ("Bill");

Однако несмотря на то, что напрямую мы не можем вызвать конструктор класса Person для создания объекта, тем не менее конструктор в абстрактных классах то же может играть важную роль, в частности, инициализировать некоторые общие для производных классов переменные и свойства, как в случае со свойством Name. И хотя в примере выше конструктор класса Person не вызывается, тем не менее производные классы Client и Employee могут обращаться к нему.

Абстрактные члены классов

Кроме обычных свойств и методов абстрактный класс может иметь абстрактные члены классов, которые определяются с помощью ключевого слова abstract и не имеют никакого функционала. В частности, абстрактными могут быть:

  • Свойства

    Индексаторы

Абстрактные члены классов не должны иметь модификатор private. При этом производный класс обязан переопределить и реализовать все абстрактные методы и свойства, которые имеются в базовом абстрактном классе. При переопределении в производном классе такой метод или свойство также объявляются с модификатором override (как и при обычном переопределении виртуальных методов и свойств). Также следует учесть, что если класс имеет хотя бы одный абстрактный метод (или абстрактные свойство, индексатор, событие), то этот класс должен быть определен как абстрактный .

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

Абстрактные методы

Например, сделаем в примере выше метод Display абстрактным:

Abstract class Person { public string Name { get; set; } public Person(string name) { Name = name; } public abstract void Display(); } class Client: Person { public int Sum { get; set; } // сумма на счету public Client(string name, int sum) : base(name) { Sum = sum; } public override void Display() { Console.WriteLine($"{Name} имеет счет на сумму {Sum}"); } } class Employee: Person { public string Position { get; set; } // должность public Employee(string name, string position) : base(name) { Position = position; } public override void Display() { Console.WriteLine($"{Position} {Name}"); } }

Абстрактные свойства

Следует отметить использование абстрактных свойств. Их определение похоже на определение автосвойств. Например:

Abstract class Person { public abstract string Name { get; set; } } class Client: Person { private string name; public override string Name { get { return "Mr/Ms. " + name; } set { name = value; } } } class Employee: Person { public override string Name { get; set; } }

В классе Person определено абстрактное свойство Name. Оно похоже на автосвойство, но это не автосвойство. Так как данное свойство не должно иметь реализацию, то оно имеет только пустые блоки get и set. В производных классах мы можем переопределить это свойство, сделав его полноценным свойством (как в классе Client), либо же сделав его автоматическим (как в классе Employee).

Отказ от реализации абстрактных членов

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

Abstract class Person { public abstract string Name { get; set; } } abstract class Manager: Person { }

Пример абстрактного класса

Xрестоматийным примером является система геометрических фигур. В реальности не существует геометрической фигуры как таковой. Есть круг, прямоугольник, квадрат, но просто фигуры нет. Однако же и круг, и прямоугольник имеют что-то общее и являются фигурами:

// абстрактный класс фигуры abstract class Figure { // абстрактный метод для получения периметра public abstract float Perimeter(); // абстрактный метод для получения площади public abstract float Area(); } // производный класс прямоугольника class Rectangle: Figure { public float Width { get; set; } public float Height { get; set; } public Rectangle(float width, float height) { this.Width = width; this.Height = height; } // переопределение получения периметра public override float Perimeter() { return Width * 2 + Height * 2; } // переопрелеление получения площади public override float Area() { return Width * Height; } }