Концепция абстрактного типа данных
Все встроенные типы данных, являются абстрактными, хотя так их называют редко.
Понятие абстракции
Абстракция - это суждение или представление о некотором объекте, которое содержит только свойства, являющиеся существенными в данном контексте. Абстракция позволяет объединять экземпляры объектов в группы, внутри которых общие свойства объектов можно не рассматривать, т.е. абстрагироваться от них. Абстракция - это эффективное средство против сложности программирования, позволяющее программисту сосредоточиться на существенных свойствах объектов. Виды абстракций: абстракция процесса и абстракция данных .
Абстракция процесса. Все подпрограммы являются абстракциями процессов, они определяют способ, с помощью которого программа устанавливает, что необходимо выполнить некоторый процесс, без уточнения деталей того, как именно это следует сделать. Возможность абстрагироваться от многочисленных деталей алгоритма, который выполняется подпрограммой, позволяет создавать, читать и понимать большие программы. Любой абстракции данных являются операции, определяемые как абстракции процессов.
Абстракция данных. Абстрактный тип данных - это инкапсуляция, которая содержит только представления данных одного конкретного типа и подпрограммы, которые выполняют операции с данными этого типа. С помощью управления доступом несущественные детали описания типа можно скрыть от внешних модулей, которые используют такой тип. Программные модули, которые используют абстрактный тип данных, могут объявлять переменные этого типа, даже несмотря на то, что реальное представление типа скрыто от них. Экземпляр абстрактного типа данных называется объектом.
Причина создания абстракции типа данных и абстракции процесса - это средство против сложности, способ сделать большие и/или сложные программы более управляемыми.
Инкапсуляция
Разделение программы на синтаксические контейнеры, которые содержат группы логически связанных подпрограмм и данных. Эти синтаксические контейнеры называются модулями, а процесс их разработки- модуляризацией.
Составление программы из наборов подпрограмм и данных, каждый из которых можно компилировать отдельно, без повторной компиляции остальной части программы. Такой набор называется единицей компиляции.
Инкапсуляция - это способ объединения в единое целое подпрограмм и данных, которые они обрабатывают. Инкапсуляция, которая компилируется либо отдельно, либо независимо от других, является основой абстрактной системы и логической организации набора соответствующих вычислений.
Абстрактные типы данных, определяемые пользователем
Абстрактные типы данных, определяемые пользователем, должны иметь следующие свойства:
1) определение типа, позволяющее программным модулям объявлять переменные этого типа, создавая при этом реальное представление этих переменных в памяти.
2) набор операций для манипуляций с объектами данного типа.
Формальное определение абстрактного типа данных в контексте типов, определенных пользователем: абстрактный тип данных - это тип данных, который удовлетворяет следующим двум условиям.
Представление (определение типа) и операции над объектами данного типа содержатся в одной синтаксической единице, переменные данного типа можно создавать и в других модулях.
Представление объектов данного типа скрыто от программных модулей, использующих этот тип, над объектами можно производить операции, которые прямо предусмотрены в определении типа.
Упаковка представления типа и операций в отдельную синтаксическую единицу, позволяет организовывать программу в виде логических единиц, которые можно компилировать отдельно. Во-вторых, появляется возможность модифицировать представления объектов данного типа или операции с ними в отдельной части программы. У сокрытия деталей представления типа есть преимущества. Клиенты не могут "видеть" детали представления объектов, и их код не зависит от этого представления. Таким образом, представления объектов можно изменять в любое время, не требуя при этом вносить изменения в код клиентов. Другим очевидным и важным преимуществом сокрытия информации является повышенная надежность. Клиенты не могут непосредственно изменять основные представления объектов ни преднамеренно, ни случайно, следовательно, возрастает целостность таких объектов. Объекты можно изменять только с помощью предусмотренных для этого операций.
Вопросы разработки типов
Должна существовать возможность делать имя типа и заголовки подпрограмм видимыми в клиентах абстракции. Это позволяет клиентам объявлять переменные абстрактного типа и манипулировать их значениями. Несмотря на то что имя типа должно быть видимым извне, его определение должно быть скрыто.
Существует очень мало общих встроенных операций, которые можно выполнять с объектами абстрактных типов, в отличие от операций, предусмотренных определением типа. К таким операциям относятся присваивания, а также проверки равенства и неравенства. Если язык не позволяет пользователям перегружать операцию присваивания, то она должна быть встроенной. Проверки равенства и неравенства в одних случаях должны быть заранее определены, а в других - нет. Разработчик типа должен определить операции для большинства абстрактных типов данных сам.
Языки Smalltalk, C++ и Java непосредственно поддерживают абстрактные типы данных.
Абстрактные типы данных в языке C++
Языки Ada и Modula-2 обеспечивают инкапсуляцию, которая может использоваться при моделировании абстрактных типов данных, в языке C++ введено понятие класса, который непосредственно поддерживает абстрактные типы данных. В языке C++ классы - это типы, а пакеты языка Ada и модули языка Modula-2 типами не являются. Пакеты и модули импортируются, позволяя импортирующей программной единице объявлять переменные любого типа, определенного в пакете или модуле. В программе на языке C++ переменные объявляются как сущности, имеющие тип данного класса. Таким образом, классы гораздо больше похожи на встроенные типы, чем пакеты или модули. Программная единица, которая видит пакет в языке Ada или модуль в языке Modula-2, имеет доступ к любым открытым сущностям просто по их именам. Программная единица на языке C++, которая объявляет экземпляр класса, также имеет доступ к любым открытым сущностям в этом классе, но только через экземпляр этого класса.
Разработка абстрактных моделей для данных и способов обработки этих данных является важнейшим компонентом в процессе решения задач с помощью компьютера. Примеры этого мы видим и на низком уровне в повседневном программировании (например, при использовании массивов и связных списков, рассмотренных в ), и на высоком уровне при решении прикладных задач (как при решении задачи связности с помощью леса объединение-поиск в "Введение"). В настоящей лекции рассматриваются абстрактные типы данных ( abstract data type , в дальнейшем АТД), позволяющие создавать программы с использованием высокоуровневых абстракций. Абстрактные типы данных позволяют отделять абстрактные (концептуальные) преобразования, которые программы выполняют над данными, от любого конкретного представления структуры данных и любой конкретной реализации алгоритма.
Все вычислительные системы основаны на уровнях абстракции: определенные физические свойства кремния и других материалов позволяют принять абстрактную модель бита, который может принимать двоичные значения 0-1; затем на динамических свойствах значений определенного набора битов строится абстрактная модель машины; далее, на основе принципа работы машины под управлением программы на машинном языке строится абстрактная модель языка программирования; и, наконец, строится абстрактное понятие алгоритма, реализуемое в виде программы на языке C++. Абстрактные типы данных дают возможность продолжать этот процесс дальше и разрабатывать абстрактные механизмы для определенных вычислительных задач на более высоком уровне, чем это обеспечивается системой C++, разрабатывать абстрактные механизмы , ориентированные на конкретные приложения и подходящие для решения задач в многочисленных прикладных областях, а также создавать абстрактные механизмы более высокого уровня, в которых используются эти базовые конструкции. Абстрактные типы данных предоставляют в наше распоряжение расширяемый до бесконечности набор инструментальных средств для решения все новых и новых задач.
С одной стороны, применение абстрактных конструкций освобождает от забот по их детальной реализации; с другой стороны, когда производительность программы важна, необходимо знать затраты на выполнение базовых операций. Мы используем множество базовых абстракций, встроенных в аппаратные средства компьютера и служащих основой для машинных инструкций; реализуем другие абстракции в программном обеспечении; и используем дополнительные абстракции, предоставляемые написанным ранее системным программным обеспечением. Абстрактные конструкции высокого уровня часто создаются на основе более простых конструкций. На всех уровнях действует один и тот же основной принцип: необходимо найти наиболее важные операции в программах и наиболее важные характеристики данных, а затем точно определить те и другие на абстрактном уровне и разработать эффективные конкретные механизмы для их реализации. В настоящей лекции мы рассмотрим множество примеров применения этого принципа.
Для разработки нового уровня абстракции потребуется (1) определить абстрактные объекты, с которыми необходимо манипулировать, и операции , которые должны выполняться над ними; (2) представить данные в некоторой структуре данных и реализовать операции ; (3) и (самое главное) обеспечить, чтобы эти объекты было удобно использовать для решения прикладных задач. Эти пункты применимы и к простым типам данных, так что базовые механизмы для поддержки типов данных, которые были рассмотрены в "Элементарные структуры данных" , можно адаптировать для наших целей. Однако язык C++ предлагает важное расширение механизма структур, называемое классом ( class ). Классы исключительно полезны при создании уровней абстракции и поэтому рассматриваются в качестве основного инструмента, который используется для этой цели в оставшейся части книги.
Определение 4.1. Абстрактный тип данных (АТД) - это тип данных (набор значений и совокупность операций для этих значений), доступ к которому осуществляется только через интерфейс. Программу, которая использует АТД, будем называть клиентом, а программу, содержащую спецификацию этого типа данных - реализацией.
Именно слово только делает тип данных абстрактным: в случае АТД клиентские программы не имеют доступа к значениям данных никаким другим способом, кроме операций, описанных в интерфейсе. Представление этих данных и функции, реализующие эти операции , находятся в реализации и полностью отделены интерфейсом от клиента. Мы говорим, что интерфейс является непрозрачным: клиент не может видеть реализацию через интерфейс .
В программах на языке C++ это различие обычно проводится немного четче, так как проще всего создать интерфейс , включив в него представление данных , но указав, что клиентским программам не разрешен прямой доступ к данным. Другими словами, разработчики клиентских программ могут знать представление данных , но никоим образом не могут его использовать.
В качестве примера рассмотрим интерфейс типа данных для точек ( программа 3.3) из раздела 3.1 "Элементарные структуры данных" . В этом интерфейсе явно объявляется, что точки представлены как структуры, состоящие из пары чисел с плавающей точкой, обозначаемых x и у. Подобное применение типов данных является обычным в больших системах программного обеспечения: мы разрабатываем набор соглашений о представлении данных (а также определяем ряд связанных с ними операций) и делаем эти правила доступными через интерфейс , чтобы ими могли пользоваться клиентские программы, входящие в состав большой системы. Тип данных обеспечивает согласованность всех частей системы с представлением основных общесистемных структур данных. Какой бы хорошей такая стратегия ни была, она имеет один изъян: если необходимо изменить представление данных , то потребуется изменить и все клиентские программы. Программа 3.3 снова дает нам простой пример: одна из причин разработки этого типа данных - удобство работы клиентских программ с точками, и мы ожидаем, что в случае необходимости у клиентов будет доступ к отдельным координатам точки. Но мы не можем перейти к другому представлению данных (скажем, к полярным координатам, или трехмерным координатам, или даже к другим типам данных для отдельных координат) без изменения всех клиентских программ.
В отличие от этого, программа 4.1 содержит реализацию абстрактного типа данных, соответствующего типу данных из программы 3.3, но с использованием класса языка C++, в котором сразу определены как данные, так и связанные с ними операции . Программа 4.2 является клиентской программой, работающей с этим типом данных. Эти две программы выполняют те же самые вычисления, что и программы 3.3 и 3.8. Они иллюстрируют ряд основных свойств классов, которые мы сейчас рассмотрим.
Когда мы пишем в программе определение наподобие int i, мы указываем системе зарезервировать область памяти для данных (встроенного) типа int , к которой можно обращаться по имени i. В языке C++ для подобных сущностей имеется термин объект . При записи в программе такого определения, как POINT p, говорят, что создается объект класса POINT , к которому можно обращаться по имени p. В нашем примере каждый объект содержит два элемента данных, с именами x и у. Как и в случае структур, к ним можно обращаться по именам вроде p.y.
Элементы данных x и у называются данными-членами класса. В классе могут быть также определены функции-члены, которые реализуют операции , связанные с этим типом данных. Например, класс , определенный в программе 4.1, имеет две функции-члена с именами POINT и distance .
Клиентские программы, такие как программа 4.2, могут вызывать функции-члены, связанные с объектом, указывая их имена точно так же, как и имена данных, находящихся в какой-нибудь структуре struct. Например, выражение p.distance(q) вычисляет расстояние между точками p и q (такое же расстояние должен возвращать и вызов q.distance(p) ). Функция POINT() - первая функция в программе 4.1 - является особой функцией-членом, называемой конструктором: у нее такое же имя, как и у класса, и она вызывается тогда, когда требуется создать объект этого класса.
Программа 4.1. Реализация класса POINT (точка)
В этом классе определен тип данных , который состоит из набора значений, представляющих собой "пары чисел с плавающей точкой" (предполагается, что они интерпретируются как точки на декартовой плоскости), а также две функции-члена, определенные для всех экземпляров класса POINT : функция POINT() , которая является конструктором, инициализирующим координаты случайными значениями от 0 до 1, и функция distance(POINT) , вычисляющая расстояние до другой точки. Представление данных является приватным ( private ), и обращаться к нему или модифицировать его могут только функции-члены. Сами функции-члены являются общедоступными ( public ) и доступны для любого клиента. Код можно сохранить, например, в файле с именем POINT .cxx.
#include
Программа 4.2. Программа-клиент для класса POINT (нахождение ближайшей точки)
Эта версия программы 3.8 является клиентом, который использует АТД POINT , определенный в программе 4.3. Операция new создает массив объектов POINT (вызывая конструктор POINT () для инициализации каждого объекта случайными значениями координат). Выражение a[i].distance(a[j]) вызывает для объекта a[i] функцию-член distance с аргументом a[j] .
#include
Определение POINT p в программе-клиенте приводит к выделению области памяти под новый объект и затем (с помощью функции POINT() ) к присвоению каждому из двух его элементов данных случайного значения в диапазоне от 0 до 1.
Этот стиль программирования, который иногда называется объектно-ориентированным программированием, полностью поддерживается конструкцией class языка C++. Класс можно считать расширением понятия структуры, где не только объединяются данные, но и определяются операции с этими данными. Может существовать много разных объектов, принадлежащих одному классу, но все они подобны в том, что их данные-члены могут принимать один и тот же набор значений, и с этими данными-чле-нами может выполняться одна и та же совокупность операций - в общем, это экземпляры одного и того же типа данных. В объектно-ориентированном программировании объекты предназначены для обработки своих данных-членов (в отличие от использования независимых функций для обработки данных, хранимых в объектах).
Мы рассматриваем описанный выше пример небольшого класса просто чтобы познакомиться с основными чертами классов; поэтому он далеко не полон. В реальном коде для класса точки у нас будет намного больше операций. Например, в программе 4.1 отсутствуют даже операции , позволяющие узнавать значения координат x и y . Как мы увидим, добавление этих и других операций - довольно простая задача. В части 5 мы более подробно рассмотрим классы для точки и других геометрических абстракций, например, линий и многоугольников.
В языке C++ (но не в С) у структур также могут быть связанные с ними функции. Ключевое различие между классами и структурами связано с доступом к информации, который характеризуется ключевыми словами
Язык С++ позволяет создавать типы данных, которые ведут себя аналогично базовым типам языка Си. Такие типы обычно называют абстрактными типами данных
(АТД).
Для реализации АТД в языке Си используются структуры. Но использование данных структурного типа значительно ограничено по сравнению с использованием базовых типов данных. Например, структурные данные нельзя использовать как операнды в различных операциях (сложение, вычитание). Для манипуляции с подобными данными надо писать набор функций, выполняющих различные действия, и вместо операций вызывать эти функции.
Кроме того, элементы структуры никак не защищены от случайной модификации. То есть любая функция (даже не из набора средств манипуляции структурными данными) может обратиться к элементу структуры. Это противоречит одному из основных принципов объектно-ориентированного программирования - инкапсуляции данных: никакие другие функции, кроме специальных функций манипуляции этим типом данных, не должны иметь доступ к элементам данных.
Рассмотрим реализацию понятия даты с использованием struct
для того, чтобы определить представление даты date
и множества функций для работы с переменными этого типа:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include
struct
date
{
int
month; // месяц
int
day; // день
int
year; // год
};
void
set_date(date* f, int
d, int
m, int
y)
{
f->day = d;
f->month = m;
f->year = y;
}
void
print_date(date* f)
{
printf("%d.%d.%d"
, f->day, f->month, f->year);
}
int
main()
{
date today;
set_date(&today, 2, 4, 2014);
print_date(&today);
getchar();
return
0;
}
Результат выполнения
Никакой явной связи между функциями и типом данных в этом примере нет. Для вызова любой из описанных функций требуется в качестве аргумента передать указатель на экземпляр структуры.
Такую связь можно установить, описав функции как члены структуры. Эти функции могут действовать на данные, содержащие в самой структуре.
По умолчанию при объявлении структуры ее данные и функции являются общими, то есть у объектов типа структура нет ни инкапсуляции, ни защиты данных:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include
struct
date
{
int
month; // месяц
int
day; // день
int
year; // год
void
set_date(int
d, int
m, int
y)
{
day = d; month = m; year = y;
}
void
print_date(void
);
};
void
date::print_date(void
)
{
printf("%d.%d.%d"
, day, month, year);
}
int
main()
{
date today;
today.set_date(2, 4, 2014);
today.print_date();
getchar();
return
0;
}
Функции-члены и данные-члены
Функции, описанные в теле абстрактного типа данных, представляют собой функции-члены или методы и могут вызываться только для специальной переменной соответствующего типа с использованием стандартного синтаксиса для доступа к данным-членам или полям структуры.
Определение функций-членов может осуществляться двумя способами:
- описание функции непосредственно при описании структуры;
- описание функции вне структуры.
Функции-члены, которые определены внутри структуры, являются неявно встроенными (). Как правило, только короткие, часто используемые функции-члены, должны определяться внутри структуры: void
set(int
m, int
d, int
y) {month = m; day = d; year = y;};
Поскольку разные структуры могут иметь функции-члены с одинаковыми именами, при определении функции члена необходимо указывать имя структуры, связывая их с помощью оператора разрешения контекста (двойное двоеточие)::
тип АТД::имя(список аргументов) {
тело функции-члена; }
- тип — тип возвращаемого значения функции-члена
- АТД — имя абстрактного типа данных (имя структуры или класса)
- имя — имя функции-члена
void
date::print_date(void
)
{ printf("%d.%d.%d"
,day, month, year);}
В функции-члене имена членов могут использоваться без явной ссылки на объект. В этом случае имя относится к члену того объекта, для которого функция была вызвана.
Функции-члены, одной и той же структуры могут быть полиморфными, то есть перегруженными.
Права доступа
Концепция структуры в языке С++ (в отличие от Си) позволяет членам структуры быть общими, частными или защищенными:
- public – общие;
- private – частные;
- protected – защищенные.
Использование ключевого слова protected связано с понятием наследования .
Использование ключевого слова private
ограничивает доступ к членам, которые следуют за этой конструкцией. Члены private
могут использоваться только несколькими категориями функций, в привилегии которых входит доступ к этим членам. В основном это функции-члены той же структуры.
Ключевое слово public
образует интерфейс к объекту структуры.
Стандартным является размещение член-данных в частной области (private ), а части функций-членов – в общей части (public ) абстрактного типа данных. В этом случае закрытая (private ) часть определяет данные объекта и служебные функции, а функции-члены общей части реализуют методы работы с объектом.
Изменим структуру date так, чтобы скрыть представление данных (инкапсуляция данных):
1
2
3
4
5
6
7
8
struct
date
{
private
:
int
month, day, year;
public
:
void
set(int
, int
, int
);
void
print();
};
Разработка абстрактных моделей для данных и способов обработки этих данных является важнейшим компонентом в процессе решения задач с помощью компьютера. Примеры этого мы видим и на низком уровне в повседневном программировании (например, при использовании массивов и связных списков, рассмотренных в ), и на высоком уровне при решении прикладных задач (как при решении задачи связности с помощью леса объединение-поиск в "Введение"). В настоящей лекции рассматриваются абстрактные типы данных ( abstract data type , в дальнейшем АТД), позволяющие создавать программы с использованием высокоуровневых абстракций. Абстрактные типы данных позволяют отделять абстрактные (концептуальные) преобразования, которые программы выполняют над данными, от любого конкретного представления структуры данных и любой конкретной реализации алгоритма.
Все вычислительные системы основаны на уровнях абстракции: определенные физические свойства кремния и других материалов позволяют принять абстрактную модель бита, который может принимать двоичные значения 0-1; затем на динамических свойствах значений определенного набора битов строится абстрактная модель машины; далее, на основе принципа работы машины под управлением программы на машинном языке строится абстрактная модель языка программирования; и, наконец, строится абстрактное понятие алгоритма, реализуемое в виде программы на языке C++. Абстрактные типы данных дают возможность продолжать этот процесс дальше и разрабатывать абстрактные механизмы для определенных вычислительных задач на более высоком уровне, чем это обеспечивается системой C++, разрабатывать абстрактные механизмы , ориентированные на конкретные приложения и подходящие для решения задач в многочисленных прикладных областях, а также создавать абстрактные механизмы более высокого уровня, в которых используются эти базовые конструкции. Абстрактные типы данных предоставляют в наше распоряжение расширяемый до бесконечности набор инструментальных средств для решения все новых и новых задач.
С одной стороны, применение абстрактных конструкций освобождает от забот по их детальной реализации; с другой стороны, когда производительность программы важна, необходимо знать затраты на выполнение базовых операций. Мы используем множество базовых абстракций, встроенных в аппаратные средства компьютера и служащих основой для машинных инструкций; реализуем другие абстракции в программном обеспечении; и используем дополнительные абстракции, предоставляемые написанным ранее системным программным обеспечением. Абстрактные конструкции высокого уровня часто создаются на основе более простых конструкций. На всех уровнях действует один и тот же основной принцип: необходимо найти наиболее важные операции в программах и наиболее важные характеристики данных, а затем точно определить те и другие на абстрактном уровне и разработать эффективные конкретные механизмы для их реализации. В настоящей лекции мы рассмотрим множество примеров применения этого принципа.
Для разработки нового уровня абстракции потребуется (1) определить абстрактные объекты, с которыми необходимо манипулировать, и операции , которые должны выполняться над ними; (2) представить данные в некоторой структуре данных и реализовать операции ; (3) и (самое главное) обеспечить, чтобы эти объекты было удобно использовать для решения прикладных задач. Эти пункты применимы и к простым типам данных, так что базовые механизмы для поддержки типов данных, которые были рассмотрены в "Элементарные структуры данных" , можно адаптировать для наших целей. Однако язык C++ предлагает важное расширение механизма структур, называемое классом ( class ). Классы исключительно полезны при создании уровней абстракции и поэтому рассматриваются в качестве основного инструмента, который используется для этой цели в оставшейся части книги.
Определение 4.1. Абстрактный тип данных (АТД) - это тип данных (набор значений и совокупность операций для этих значений), доступ к которому осуществляется только через интерфейс. Программу, которая использует АТД, будем называть клиентом, а программу, содержащую спецификацию этого типа данных - реализацией.
Именно слово только делает тип данных абстрактным: в случае АТД клиентские программы не имеют доступа к значениям данных никаким другим способом, кроме операций, описанных в интерфейсе. Представление этих данных и функции, реализующие эти операции , находятся в реализации и полностью отделены интерфейсом от клиента. Мы говорим, что интерфейс является непрозрачным: клиент не может видеть реализацию через интерфейс .
В программах на языке C++ это различие обычно проводится немного четче, так как проще всего создать интерфейс , включив в него представление данных , но указав, что клиентским программам не разрешен прямой доступ к данным. Другими словами, разработчики клиентских программ могут знать представление данных , но никоим образом не могут его использовать.
В качестве примера рассмотрим интерфейс типа данных для точек ( программа 3.3) из раздела 3.1 "Элементарные структуры данных" . В этом интерфейсе явно объявляется, что точки представлены как структуры, состоящие из пары чисел с плавающей точкой, обозначаемых x и у. Подобное применение типов данных является обычным в больших системах программного обеспечения: мы разрабатываем набор соглашений о представлении данных (а также определяем ряд связанных с ними операций) и делаем эти правила доступными через интерфейс , чтобы ими могли пользоваться клиентские программы, входящие в состав большой системы. Тип данных обеспечивает согласованность всех частей системы с представлением основных общесистемных структур данных. Какой бы хорошей такая стратегия ни была, она имеет один изъян: если необходимо изменить представление данных , то потребуется изменить и все клиентские программы. Программа 3.3 снова дает нам простой пример: одна из причин разработки этого типа данных - удобство работы клиентских программ с точками, и мы ожидаем, что в случае необходимости у клиентов будет доступ к отдельным координатам точки. Но мы не можем перейти к другому представлению данных (скажем, к полярным координатам, или трехмерным координатам, или даже к другим типам данных для отдельных координат) без изменения всех клиентских программ.
В отличие от этого, программа 4.1 содержит реализацию абстрактного типа данных, соответствующего типу данных из программы 3.3, но с использованием класса языка C++, в котором сразу определены как данные, так и связанные с ними операции . Программа 4.2 является клиентской программой, работающей с этим типом данных. Эти две программы выполняют те же самые вычисления, что и программы 3.3 и 3.8. Они иллюстрируют ряд основных свойств классов, которые мы сейчас рассмотрим.
Когда мы пишем в программе определение наподобие int i, мы указываем системе зарезервировать область памяти для данных (встроенного) типа int , к которой можно обращаться по имени i. В языке C++ для подобных сущностей имеется термин объект . При записи в программе такого определения, как POINT p, говорят, что создается объект класса POINT , к которому можно обращаться по имени p. В нашем примере каждый объект содержит два элемента данных, с именами x и у. Как и в случае структур, к ним можно обращаться по именам вроде p.y.
Элементы данных x и у называются данными-членами класса. В классе могут быть также определены функции-члены, которые реализуют операции , связанные с этим типом данных. Например, класс , определенный в программе 4.1, имеет две функции-члена с именами POINT и distance .
Клиентские программы, такие как программа 4.2, могут вызывать функции-члены, связанные с объектом, указывая их имена точно так же, как и имена данных, находящихся в какой-нибудь структуре struct. Например, выражение p.distance(q) вычисляет расстояние между точками p и q (такое же расстояние должен возвращать и вызов q.distance(p) ). Функция POINT() - первая функция в программе 4.1 - является особой функцией-членом, называемой конструктором: у нее такое же имя, как и у класса, и она вызывается тогда, когда требуется создать объект этого класса.
Программа 4.1. Реализация класса POINT (точка)
В этом классе определен тип данных , который состоит из набора значений, представляющих собой "пары чисел с плавающей точкой" (предполагается, что они интерпретируются как точки на декартовой плоскости), а также две функции-члена, определенные для всех экземпляров класса POINT : функция POINT() , которая является конструктором, инициализирующим координаты случайными значениями от 0 до 1, и функция distance(POINT) , вычисляющая расстояние до другой точки. Представление данных является приватным ( private ), и обращаться к нему или модифицировать его могут только функции-члены. Сами функции-члены являются общедоступными ( public ) и доступны для любого клиента. Код можно сохранить, например, в файле с именем POINT .cxx.
#include
Программа 4.2. Программа-клиент для класса POINT (нахождение ближайшей точки)
Эта версия программы 3.8 является клиентом, который использует АТД POINT , определенный в программе 4.3. Операция new создает массив объектов POINT (вызывая конструктор POINT () для инициализации каждого объекта случайными значениями координат). Выражение a[i].distance(a[j]) вызывает для объекта a[i] функцию-член distance с аргументом a[j] .
#include
Определение POINT p в программе-клиенте приводит к выделению области памяти под новый объект и затем (с помощью функции POINT() ) к присвоению каждому из двух его элементов данных случайного значения в диапазоне от 0 до 1.
Этот стиль программирования, который иногда называется объектно-ориентированным программированием, полностью поддерживается конструкцией class языка C++. Класс можно считать расширением понятия структуры, где не только объединяются данные, но и определяются операции с этими данными. Может существовать много разных объектов, принадлежащих одному классу, но все они подобны в том, что их данные-члены могут принимать один и тот же набор значений, и с этими данными-чле-нами может выполняться одна и та же совокупность операций - в общем, это экземпляры одного и того же типа данных. В объектно-ориентированном программировании объекты предназначены для обработки своих данных-членов (в отличие от использования независимых функций для обработки данных, хранимых в объектах).
Мы рассматриваем описанный выше пример небольшого класса просто чтобы познакомиться с основными чертами классов; поэтому он далеко не полон. В реальном коде для класса точки у нас будет намного больше операций. Например, в программе 4.1 отсутствуют даже операции , позволяющие узнавать значения координат x и y . Как мы увидим, добавление этих и других операций - довольно простая задача. В части 5 мы более подробно рассмотрим классы для точки и других геометрических абстракций, например, линий и многоугольников.
В языке C++ (но не в С) у структур также могут быть связанные с ними функции. Ключевое различие между классами и структурами связано с доступом к информации, который характеризуется ключевыми словами
Абстрактный тип данных
Абстра́ктный тип да́нных (АТД) - это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций , а также возможность создавать элементы этого типа при помощи специальных функций. Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения - в этом и заключается суть абстракции . Абстрактный тип данных определяет набор независимых от конкретной реализации типа функций для оперирования его значениями. Конкретные реализации АТД называются структурами данных .
В программировании абстрактные типы данных обычно представляются в виде интерфейсов , которые скрывают соответствующие реализации типов. Программисты работают с абстрактными типами данных исключительно через их интерфейсы, поскольку реализация может в будущем измениться. Такой подход соответствует принципу инкапсуляции в объектно-ориентированном программировании . Сильной стороной этой методики является именно сокрытие реализации. Раз вовне опубликован только интерфейс, то пока структура данных поддерживает этот интерфейс, все программы, работающие с заданной структурой абстрактным типом данных, будут продолжать работать. Разработчики структур данных стараются, не меняя внешнего интерфейса и семантики функций, постепенно дорабатывать реализации, улучшая алгоритмы по скорости, надежности и используемой памяти.
Различие между абстрактными типами данных и структурами данных, которые реализуют абстрактные типы, можно пояснить на следующем примере. Абстрактный тип данных список может быть реализован при помощи массива или линейного списка, с использованием различных методов динамического выделения памяти. Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализаций.
Абстрактные типы данных позволяют достичь модульности программных продуктов и иметь несколько альтернативных взаимозаменяемых реализаций отдельного модуля.
Примеры АТД
См. также
Ссылки
- Лапшин В. А. Абстрактные типы данных в программировании
Wikimedia Foundation . 2010 .
Смотреть что такое "Абстрактный тип данных" в других словарях:
абстрактный тип данных - Тип данных (абстрактный класс), определенный посредством перечисления его методов и свойств, без создания их конкретной реализации. Тематики информационные технологии в целом EN Abstract Data TypeADT … Справочник технического переводчика
В теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых… … Википедия
Целое, целочисленный тип данных (англ. Integer), в информатике один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел. Множество чисел этого типа представляет собой… … Википедия
У этого термина существуют и другие значения, см. Множество (значения). Множество тип и структура данных в информатике, является реализацией математического объекта множество. Данные типа множество позволяют хранить ограниченное число значений… … Википедия
Некоторые языки программирования предоставляют специальный тип данных для комплексных чисел. Наличие встроенного типа упрощает хранение комплексных величин и вычисления над ними. Содержание 1 Арифметика над комплексными 2 Поддержка в языках … Википедия
У этого термина существуют и другие значения, см. Указатель. Диаграмма указателей Указатель (пойнтер, англ. pointer) переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения нулевого адреса.… … Википедия
Один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности в языках ML и Haskell, причём в… … Википедия
Типаж (англ. trait) это абстрактный тип, в информатике, используемый, как «простая концептуальная модель для структурирования объектно ориентированных программ». Типажи подобны mixins, но могут включать определения методов класса.… … Википедия
Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия
- (top type) в теории типов, часто обозначаемый как просто вершина или «закрепленным» символом (⊤), универсальный тип, то есть такой тип, который содержит в себе каждый возможный объект в нужной системе типов. Высший тип иногда именуется… … Википедия