Концепция абстрактного типа данных. Абстрактные типы данных

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1. Последовательность (Sequence).

Бесконечная (конечная) последовательность формально определяется как функция, областью определения которой является множество положительных целых чисел: f(i)= , . Во многих случаях индексирование последовательности более удобно начинать с нуля; тогда областью определения / будет множество целых неотрицательных чисел. Аналогично определим конечную последовательность или список как функцию, областью определения которой является множество {1, 2, ..., }.

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

¨ Множество возможных значений – конечные последовательности элементов одинакового типа.

¨ Набор операций:

§ Вставить элемент в последовательность.

§ Удалить элемент из последовательности.

§ Посмотреть – функция, возвращающая значение элемента последовательности.

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

Для АТД этого вида стек (stack) , очередь (queue) и дек (deque от Double Ended Queue - двусторонняя очередь) характерно разрушающее чтение , т.к. доступ к элементам (для всех трех операций) ограничен одним из концов последовательности и операцию «посмотреть другой элемент» можно выполнить, только удалив мешающие этому элементы. Для АТД вектор(array, vector),файл (file) и линейный список (linear list) ограничения на доступ обеспечивают неразрушающее чтение , поэтому особое значение имеет (производная) операция просмотра последовательности .

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

Понятия «номер» и «позиция» элемента – близкие, но могут не совпадать:

§ Номер - это собственно порядковый номер элемента в последовательности. Но порядковый номер элемента изменяется в результате выполнения операций вставки и удаления предшествующих элементов, это создает ряд неудобств в идентификации элементов последовательности.

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

Для АТД «Последовательность» представляют интерес дополнительные операции вида: сцепить две последовательности, расцепить на две последовательности. Например, в АТД строка(string) такого вида операции фактически являются основными.

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

2.2. Множество (Set).

¨ Множество возможных значений – конечные множества элементов одинакового типа.

¨ Набор операций:

§ Вставить элемент во множество.

§ Удалить элемент из множества.

§ Принадлежать – функция, возвращающая значение true, если элемент принадлежит множеству.

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

Специализированные расширения АТД «Множество» рассматриваются в различных направлениях:

§ Близким к понятию «множество» является понятие «набор». Набор (Bag, MultiSet) – также как и множество является семейством элементов, безотносительно к тому задано ли на элементах отношение порядка, но элементы в наборе могут повторяться по значению. Вообще говоря, набор можно представить множеством, например, элементы которого являются парами [значение элемента, количество вхождений в набор].

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

§ Естественным представляется задание на множестве отношения порядка, частичного или линейного, АТД «Очередь с приоритетом» - пример такого специализированного расширения АТД «Множество». Аналогично в предметной области решаемой задачи могут представлять интерес и другие отношения на множестве .

§ Фундаментальное положение в математике занимает понятие отношение эквивалентности и соответственно – понятие разбиение множества на классы эквивалентности. Естественно, что это понятие широко используется и в практических разработках моделей решения задач предметных областей. АТД «Семейство непересекающихся множеств» (Disjoint Sets, Partitions, Разбиения) - пример соответствующего специализированного расширения АТД «Множество».

Для специализированных расширений АТД «Множество» естественно соответствующим образом уточняются вышеотмеченные операции и появляются свои новые операции, представляющие интерес.

2.3. Словарь (Dictionary, Map), другое название – ассоциативный массив .

¨ Множество возможных значений – конечные множества элементов одинакового типа, вида , где Key – уникальный ключ элемента, Value - собственно значение.

¨ Набор операций:

§ Вставить элемент (с ключом) во множество.

§ Удалить элемент (заданный ключом) из множества.

§ Найти элемент – функция, возвращающая по ключу значение элемента или «пустое» значение, если элемента с таким ключом нет во множестве.

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

2.4. Очередь с приоритетом (Priority queue).

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

Отметим, что такое множество возможных значений можно трактовать и как множество последовательностей (с перечислением её элементов в заданном линейном порядке).

¨ Набор операций:

§ Вставить элемент в (линейно упорядоченное) множество.

§ Удалить минимальный элемент из множества.

§ Найти минимальный – функция, возвращающая значение минимального элемента во множестве.

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

§ Расцепить очередь на две по заданному значению (приоритету) элемента – на очередь элементов с меньшим приоритетом и очередь остальных.

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

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

§ Уменьшить значение (приоритет) заданного элемента.

§ Удалить (произвольно) заданный элемент из множества.

2.5. Непересекающиеся множества (Disjoint Sets, Partitions, Разбиения) .

¨ Множество возможных значений – конечные множества (семейства) непересекающихся конечных множеств. Элементы семейства идентифицированы, т.е. каждое множество из семейства имеет (уникальное) имя.

¨ Набор операций:

§ Объединить(А,В) – операция вида А:= А È В без сохранения исходных объединяемых множеств (а значит новое значение семейства останется семейством непересекающихся множеств, причем их количество уменьшится).

§ Найти множество – функция, возвращающая для заданного х имя такого множества Х в семействе, что х Î Х.

2.6. Деревья, графы и отношения общего вида.

В дискретной математике особое внимание уделяется (конечным) отношениям вида - дерево, граф и сеть (мультиграф, гиперграф), имеющим определенно выраженную геометрическую трактовку:

¨ Граф – (конечное) бинарное отношение (симметричное – в случае неориентированных графов), E Í V 2 , где V – множество вершин, а E – множество ребер графа.

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

¨ Дерево – это бинарное отношение (строгого) частичного порядка, дополнительно удовлетворяющее требованиям (иерархичности, древесности):

§ из того, что х<у,z следует, что у и z сравнимы, т.е. либо у£z либо z£у (х<у трактуется как: х встречается раньше у в пути к корню дерева, х – потомок, у - предок);

§ во множестве V (вершин дерева) существует наибольший элемент (корень дерева).

Деревья можно различать, если порядок сыновей (хотя бы для одной) вершины дерева различен. Упорядоченное дерево – дерево, в котором для каждой вершины задан порядок на множестве дочерних вершин, т.е. детей можно определить как первый, второй и т.д.

¨ Сеть – это отношение общего вида, которое можно трактовать как обобщение – E Í VÈV 2 È...V k , а можно – как отношение (E Í V k) с множеством элементов V, имеющим «пустой» (фиктивный) элемент.

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

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

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 не очень подходящий язык для реализации различных АТД, но, с другой стороны, трудно найти иной язык программирования, в котором можно было бы так непосредственно декларировать АТД. Дополнительную информацию о таких языках программирования см. в библиографических примечаниях в конце темы.

Абстрактный тип данных

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

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

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

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

Примеры АТД

См. также

Ссылки

• Лапшин В. А. Абстрактные типы данных в программировании

Wikimedia Foundation . 2010 .

Смотреть что такое "Абстрактный тип данных" в других словарях:

абстрактный тип данных - Тип данных (абстрактный класс), определенный посредством перечисления его методов и свойств, без создания их конкретной реализации. Тематики информационные технологии в целом EN Abstract Data TypeADT … Справочник технического переводчика

В теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых… … Википедия

Целое, целочисленный тип данных (англ. Integer), в информатике один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел. Множество чисел этого типа представляет собой… … Википедия

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

Некоторые языки программирования предоставляют специальный тип данных для комплексных чисел. Наличие встроенного типа упрощает хранение комплексных величин и вычисления над ними. Содержание 1 Арифметика над комплексными 2 Поддержка в языках … Википедия

У этого термина существуют и другие значения, см. Указатель. Диаграмма указателей Указатель (пойнтер, англ. pointer) переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения нулевого адреса.… … Википедия

Один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности в языках ML и Haskell, причём в… … Википедия

Типаж (англ. trait) это абстрактный тип, в информатике, используемый, как «простая концептуальная модель для структурирования объектно ориентированных программ». Типажи подобны mixins, но могут включать определения методов класса.… … Википедия

Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия

- (top type) в теории типов, часто обозначаемый как просто вершина или «закрепленным» символом (⊤), универсальный тип, то есть такой тип, который содержит в себе каждый возможный объект в нужной системе типов. Высший тип иногда именуется… … Википедия

Все встроенные типы данных, являются абстрактными, хотя так их называют редко.

Понятие абстракции

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

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

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

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

Инкапсуляция

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

Составление программы из наборов подпрограмм и данных, каждый из ко­торых можно компилировать отдельно, без повторной компиляции остальной части про­граммы. Такой набор называется единицей компиляции.

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

Абстрактные типы данных, определяемые пользователем

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

1) определение типа, позволяющее про­граммным модулям объявлять переменные этого типа, создавая при этом реальное пред­ставление этих переменных в памяти.

2) набор операций для манипуляций с объектами данного типа.

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

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

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

Упаковка представления типа и операций в отдельную син­таксическую единицу, позволяет организо­вывать программу в виде логических единиц, которые можно компилировать отдельно. Во-вторых, появляется возможность модифицировать представления объектов данного типа или операции с ними в отдельной части программы. У сокрытия деталей представ­ления типа есть преимущества. Клиенты не мо­гут "видеть" детали представления объектов, и их код не зависит от это­го представления. Таким образом, представления объектов можно изменять в любое время, не требуя при этом вносить изменения в код клиентов. Другим очевидным и важным преимуществом сокрытия информации является повы­шенная надежность. Клиенты не могут непосредственно изменять основные представле­ния объектов ни преднамеренно, ни случайно, следовательно, возрастает целостность та­ких объектов. Объекты можно изменять только с помощью предусмотренных для этого операций.

Вопросы разработки типов

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

Существует очень мало общих встроенных операций, которые можно выполнять с объектами абстрактных типов, в отличие от операций, предусмотренных определением типа. К таким операциям относятся присваивания, а также проверки равенства и неравенства. Если язык не позво­ляет пользователям перегружать операцию присваивания, то она должна быть встроен­ной. Проверки равенства и неравенства в одних случаях должны быть заранее определе­ны, а в других - нет. Разработчик типа должен определить операции для большинства абстрактных типов данных сам.

Языки Smalltalk, C++ и Java непосредственно поддерживают абстрактные типы данных.

Абстрактные типы данных в языке C++

Языки Ada и Modula-2 обеспечивают инкапсуляцию, которая может использоваться при моделировании абстрактных типов данных, в языке C++ введено по­нятие класса, который непосредственно поддерживает абстрактные типы данных. В язы­ке C++ классы - это типы, а пакеты языка Ada и модули языка Modula-2 типами не являют­ся. Пакеты и модули импортируются, позволяя импортирующей программной единице объявлять переменные любого типа, определенного в пакете или модуле. В программе на языке C++ переменные объявляются как сущности, имеющие тип данного класса. Таким образом, классы гораздо больше похожи на встроенные типы, чем пакеты или модули. Программная единица, которая видит пакет в языке Ada или модуль в языке Modula-2, имеет доступ к любым открытым сущностям просто по их именам. Программная едини­ца на языке C++, которая объявляет экземпляр класса, также имеет доступ к любым от­крытым сущностям в этом классе, но только через экземпляр этого класса.