Примеры представления деревьев абстрактные типы данных. Абстрактный тип данных. Абстрактный тип данных “Дерево двоичного поиска”

Последнее обновление: 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; } }

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

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

Рассмотрим реализацию понятия даты с использованием 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();
};

Абстрактный тип данных Общие положения о данных Абстрактный тип данных общие положения спецификация, представление, реализация 1

Что такое данные? Набор различных информационных объектов, над которыми выполняются те или иные действия операторами программы, называются данными. Данные - непременный атрибут любой программы. Ими могут быть: - отдельные биты; - последовательность независимых битов; -числа в разных формах представления; -байты и группы независимых байтов; -массивы чисел; -связные списки; -отдельные файлы и системы файлов. 2

Универсальное представление этого многообразия данных сложно и нецелесообразно Целесообразно разделить их на типы 3

Что такое тип данных? Тип данных определяется: – Форматом представления в памяти компьютера по определенным соглашениям алгоритмического языка, но без необходимости вычислений; – Множеством допустимых значений, которые может принимать принадлежащая к выбранному типу переменная или константа; – Множеством допустимых операций, применимых к этому типу. 4

Примеры типов данных Целочисленные типы Вещественный тип Логический тип Символьный тип Перечисляемый тип Интервальный тип Указатели 5

Целочисленные типы имеется пять предопределенных целочисленных типов: Shortint, Integer, Longint, Byte и Word. Каждый тип обозначает определенное подмножество целых чисел. Значение одного целочисленного типа может быть явным образом преобразовано к другому целочисленному типу с помощью приведения типов. 6

Вещественный тип К вещественному типу относится подмножество чисел, представляемых в формате с плавающей точкой и с фиксированным числом цифр. Запись значения в формате с плавающей запятой обычно включает три значения - m, b и e - таким образом, что m * b ^ e = n, где b всегда равен 2, а m и e являются целочисленными значениями в диапазоне вещественного типа. Эти значения m и e далее определяют диапазон представления и точность вещественного типа. Пример: 0. 143 E+22, где m - 0. 143; b=2(подразумевается), e=22. Имеется пять видов вещественных типов: вещественное (Real), с одинарной точностью (Single), с двойной точностью (Double), с повышенной точностью (Extended) и сложное (Comp). 7

Логический тип Существует 4 предопределенных логических (булевских) типа: Boolean, Byte. Bool, Word. Bool и Long. Bool. Значения булевского типа обозначаются встроенными идентификаторами констант False и True. Логические переменные могут использоваться для хранения результатов каких - либо логических вычислений. Для булевых переменных разрешены только 2 операции сравнения "="(равно) и ""(неравно). 8

Символьный тип Множеством значений этого типа являются символы, упорядоченные в соответствии с расширенным набором символов кода ASCII. Это буквы ["A". . . "Z", "a". . . "z"], цифры ["0". . . "9"], знаки препинания и специальные символы. Переменная этого типа в памяти занимает один байт. 9

Перечисляемый тип Перечислимые типы определяют упорядоченные множества значений через перечисление идентификаторов, которые обозначают эти значения. Упорядочение множеств выполняется в соответствии с последовательностью, в которой перечисляются идентификаторы. Type Week = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday); 10

Интервальный тип Интервальный тип представляет собой диапазон значений из порядкового типа. Определение интервального типа включает наименьшее и наибольшее значение в поддиапазоне. Type Interval = 0. . . 1000; Такая декларация типа указывает компилятору, что для переменных этого типа допустимы только числа из указанного диапазона. Тем самым в программе могут быть автоматически организованы проверки корректности операций присвоения для этих переменных. 11

Общее для типов данных Каждому из типов данных соответствует множество простых операций. INTEGER-операции +, -, *, div, mod REAL - операции + , -, *, / BOOLEAN- операции - конъюнкция (и), дизъюнкция V (или), отрицание (не) CHAR-операции ORD (с) -N: (С в ASCII), CHR (I) I -тый символ в ASCII По мере возрастания объемов и сложности представления информации возникает необходимость в удобных формах ее представления, хранения и обработки. 12

Определение абстрактный тип данных (АТД или abstract data type, или ADT), - это множество абстрактных объектов, представляющих элементы данных, и определенные на нем наборы операций, которые могут быть выполнены над элементами этого множества. 13

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

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

Пример Для автоматизированного управления температурой в различных комнатах большого здания полезным АТД был бы ТЕРМОСТАТ. В программе может быть много переменных типа ТЕРМОСТАТ, соответствующих реальным термостатам в различных помещениях здания. АТД может быть описан своим именем, множеством значений и допустимыми операциями так же, как и любой другой тип данных. Описание для типа ТЕРМОСТАТ: – Тип данных: ТЕРМОСТАТ – Область значений: температура может изменяться в диапазоне от 0 до 50 градусов (по Цельсию). – Операции: Выше, Ниже, Установить, Проверить, Тревога. (Можно придумать много полезных операций, но слишком большое их количество ухудшает абстракцию) 16

Уровни абстракции Уровни абстракции напоминают слои программного обеспечения. Высшие уровни абстракции отражают представление пользователя о решении задачи. Нижние уровни абстракции – возможности языка программирования. 17

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

Пример абстракции на уровне программиста Программист может предложить другой уровень абстракции для этих объектов, например, прямоугольник. Тип данных: Прямоугольник Операции: Рисовать. Прямоугольник Стереть. Прямоугольник Разделить. Прямоугольник. На. Части ……. Прямоугольник – абстракция более низкого уровня, поскольку она ближе к реализации. 19

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

Рекомендации к выбору операций абстрактного типа данных Целесообразно включение следующих операций: – операции-конструкторы, – операции проверки, – операции преобразования типов, – операции ввода-вывода, – операции копирования, – операции-селекторы. Постарайтесь свести к минимуму число операций. Простой АТД легче понять. Поддерживайте связь операций с выбранной абстракцией типа. 21

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

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

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

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

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

П р и м е р спецификации Абстрактный тип данных СТЕК, реализующий широко известную структуру данных, которая характеризуется тем, что в нее можно "поместить" некоторый элемент и "выбрать" из нее элемент, помещенный туда самым последним. Синтаксическая часть спецификации типа данных СТЕК имеет вид type СТЕК specification is СОЗДАТЬ: function () return (@); ВСТАВИТЬ: function (integer; @) return (@); УДАЛИТЬ: function (@) return (@); ВЕРШИНА: function (@) return (integer); ПУСТ: function (@) return (boolean); end specification; Здесь операция СОЗДАТЬ выдает в качестве результата пустой стек, ВСТАВИТЬ - стек с добавленным на "верх" его элементом, УДАЛИТЬ - стек с удаленным "верхним" элементом, ВЕРШИНА - значение "верхнего" элемента стека, ПУСТ - признак пустоты стека. Элементами стека здесь могут быть только целые числа. 27

РЕАЛИЗАЦИЯ АБСТРАКТНОГО ТИПА ДАННЫХ Реализацию удобнее делать с помощью объектноориентированных языков программирования, таких как C++ или Java, в которых абстрактные типы данных поддерживаются с помощью классов Реализация АТД включает конкретное описание объектов определяемого типа и реализацию операций этого типа. Это означает, что объекты описываются либо как данные простых типов, либо как массивы, записи или объединения. Причем используются предопределенные типы данных или АТД, определенные ранее. Реализация операций состоит в описании подпрограмм, выполняющих необходимые действия с указанными объектами. Например операции +, *, =. . и т. п, но при этом скрывается сама реализация этих операций. 28

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

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

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

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

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

Примеры АТД

См. также

Ссылки

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

Wikimedia Foundation . 2010 .

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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