Для чего изучать структуры и абстрактные типы данных?¶
Чтобы управлять сложностью задач и процессом их решения, учёные-информатики используют абстракции, позволяющие им сфокусироваться на картине в целом, без блуждания в деталях. Создавая модель предметной области, мы можем использовать максимально эффективный процесс поиска решения. Такие модели позволяют описывать данные, которыми будут манипулировать наши алгоритмы, намного более подходящим для данной задачи образом.
Ранее мы ссылались на процедурную абстракцию, как на процесс сокрытия деталей конкретной функции, чтобы дать пользователю (или клиенту) возможность рассматривать её на очень высоком уровне. Сейчас мы переключаем наше внимание на аналогичную идею абстракции данных. Абстрактный тип данных, иногда обозначаемый аббревиатурой АТД, — это логическое описание того, как мы рассматриваем данные и разрешённые для них операции, безотносительно их реализации. Это значит, что мы сосредотачиваемся только на том, что данные из себя представляют, а не на том, как они в итоге будут сконструированы. Обеспечивая такой уровень абстракции, мы достигаем инкапсуляции данных. Идея здесь в том, что, инкапсулируя детали реализации, мы скрываем их от взгляда пользователя. Это называется сокрытием информации.
Рисунок 2 наглядно демонстрирует, что такое абстрактный тип данных и как он работает. Пользователь взаимодействует с интерфейсом, используя операции, определённые в АТД. По сути, абстрактный тип данных — это оболочка, с которой работает клиент. Реализация скрыта на уровень ниже, и её детали пользователя совершенно не беспокоят.
Рисунок 2: Абстрактный тип данных
Реализация АТД, часто называемая структурой данных, требует, чтобы мы смотрели на них с физической точки зрения, используя при этом некий набор из конструкций программирования и примитивных типов данных. Как уже обсуждалось ранее, разделение на две точки зрения приводит нас к определению сложных моделей данных для наших задач без углубления в подробности того, как эти модели в итоге будут реализованы. Так обеспечивается независящий от реализации взгляд на данные. Так как обычно существует множество различных способов воплотить абстрактный тип данных, независимость реализации позволяет программисту изменять её детали, оставляя прежним способ взаимодействия клиента с данными. Таким образом, пользователь всегда сосредоточен только на процессе решения задачи.
readers online now | | Back to top
© Copyright 2014 Brad Miller, David Ranum. Created using Sphinx 1.2.3.
Абстрактный тип данных
Абстра́ктный тип да́нных (АТД) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения — в этом и заключается суть абстракции. Абстрактный тип данных определяет набор независимых от конкретной реализации типа функций для оперирования его значениями. Конкретные реализации АТД называются структурами данных.
В программировании абстрактные типы данных обычно представляются в виде интерфейсов, которые скрывают соответствующие реализации типов. Программисты работают с абстрактными типами данных исключительно через их интерфейсы, поскольку реализация может в будущем измениться. Такой подход соответствует принципу инкапсуляции в объектно-ориентированном программировании. Сильной стороной этой методики является именно сокрытие реализации. Раз вовне опубликован только интерфейс, то пока структура данных поддерживает этот интерфейс, все программы, работающие с заданной структурой абстрактным типом данных, будут продолжать работать. Разработчики структур данных стараются, не меняя внешнего интерфейса и семантики функций, постепенно дорабатывать реализации, улучшая алгоритмы по скорости, надежности и используемой памяти.
Различие между абстрактными типами данных и структурами данных, которые реализуют абстрактные типы, можно пояснить на следующем примере. Абстрактный тип данных список может быть реализован при помощи массива или линейного списка, с использованием различных методов динамического выделения памяти. Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализаций.
Абстрактные типы данных позволяют достичь модульности программных продуктов и иметь несколько альтернативных взаимозаменяемых реализаций отдельного модуля.
Примеры АТД
См. также
- Интерфейс программирования приложений
- Объектно-ориентированное программирование
Ссылки
Логический • Низший тип • Коллекция • Перечисляемый тип • Исключение • First-class function • Opaque data type • Recursive data type • Семафор • Поток • Высший тип • Type class • Unit type • Void
Абстрактный тип данных • Структура данных • Интерфейс • Kind (type theory) • Примитивный тип • Subtyping • Шаблоны C++ • Конструктор типа • Parametric polymorphism
- Типы данных
- Структуры данных
- Теория типов
Wikimedia Foundation . 2010 .
Полезное
Смотреть что такое «Абстрактный тип данных» в других словарях:
- абстрактный тип данных — Тип данных (абстрактный класс), определенный посредством перечисления его методов и свойств, без создания их конкретной реализации. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN Abstract Data TypeADT … Справочник технического переводчика
- Алгебраический тип данных — в теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых… … Википедия
- Целое (тип данных) — Целое, целочисленный тип данных (англ. Integer), в информатике один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел. Множество чисел этого типа представляет собой… … Википедия
- Множество (тип данных) — У этого термина существуют и другие значения, см. Множество (значения). Множество тип и структура данных в информатике, является реализацией математического объекта множество. Данные типа множество позволяют хранить ограниченное число значений… … Википедия
- Комплексный тип данных — Некоторые языки программирования предоставляют специальный тип данных для комплексных чисел. Наличие встроенного типа упрощает хранение комплексных величин и вычисления над ними. Содержание 1 Арифметика над комплексными 2 Поддержка в языках … Википедия
- Указатель (тип данных) — У этого термина существуют и другие значения, см. Указатель. Диаграмма указателей Указатель (пойнтер, англ. pointer) переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения нулевого адреса.… … Википедия
- Обобщённый алгебраический тип данных — один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности в языках ML и Haskell, причём в… … Википедия
- Типаж (абстрактный тип) — Типаж (англ. trait) это абстрактный тип, в информатике, используемый, как «простая концептуальная модель для структурирования объектно ориентированных программ»[1]. Типажи подобны mixins, но могут включать определения методов класса.… … Википедия
- Структура данных — Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия
- Высший тип — (top type) в теории типов, часто обозначаемый как просто вершина или «закрепленным» символом (⊤), универсальный тип, то есть такой тип, который содержит в себе каждый возможный объект в нужной системе типов. Высший тип иногда именуется… … Википедия
- Обратная связь: Техподдержка, Реклама на сайте
- Путешествия
Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.
- Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
- Искать во всех словарях
- Искать в переводах
- Искать в ИнтернетеИскать в этой же категории
СУЭБ ИВТ СО РАН
Словарь терминов в коллекции: Thesaurus of Information Technology (zthes_cat)
Абстрактная структура данных [ru]
Абстрактная структура данных
— структура данных, определенная функционально посредством выполняемых на ней операций. Такая структура не связана с поименованными типами объектов.
(NT) Абстрактная структура данных (add ) [ru]
Головные термины: [BT] Структура данных [ru] Термин на другом языке: [LE] Abstract logic design [LE] Абстракты деректер құрылымы [kz]
© 2013-2023, Евразийский национальный университет им. Л.Н.Гумилева, Астана © 2007-2023, Новосибирский государственный университет, Новосибирск © 1998-2023, Институт вычислительных технологий СО РАН, Новосибирск © 1998-2023, Федотов А.М. | ФИТ НГУ НГУ ЕНУ им.Гумилева ИВТ СО РАН |
Дата последней модификации: 14.05.2015
Абстрактные типы данных
Язык С++ позволяет создавать типы данных, которые ведут себя аналогично базовым типам языка Си. Такие типы обычно называют абстрактными типами данных (АТД).
Для реализации АТД в языке Си используются структуры. Но использование данных структурного типа значительно ограничено по сравнению с использованием базовых типов данных. Например, структурные данные нельзя использовать как операнды в различных операциях (сложение, вычитание). Для манипуляции с подобными данными надо писать набор функций, выполняющих различные действия, и вместо операций вызывать эти функции.
Кроме того, элементы структуры никак не защищены от случайной модификации. То есть любая функция (даже не из набора средств манипуляции структурными данными) может обратиться к элементу структуры. Это противоречит одному из основных принципов объектно-ориентированного программирования — инкапсуляции данных: никакие другие функции, кроме специальных функций манипуляции этим типом данных, не должны иметь доступ к элементам данных.
Рассмотрим реализацию понятия даты с использованием 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 date::print_date( void )
< printf( "%d.%d.%d" ,day, month, year);>
В функции-члене имена членов могут использоваться без явной ссылки на объект. В этом случае имя относится к члену того объекта, для которого функция была вызвана.
Функции-члены, одной и той же структуры могут быть полиморфными, то есть перегруженными.
Права доступа
Концепция структуры в языке С++ (в отличие от Си) позволяет членам структуры быть общими, частными или защищенными:
- public – общие;
- private – частные;
- protected – защищенные.
Использование ключевого слова protected связано с понятием наследования.
Использование ключевого слова private ограничивает доступ к членам, которые следуют за этой конструкцией. Члены private могут использоваться только несколькими категориями функций, в привилегии которых входит доступ к этим членам. В основном это функции-члены той же структуры.
Ключевое слово public образует интерфейс к объекту структуры.
Стандартным является размещение член-данных в частной области ( private ), а части функций-членов – в общей части ( public ) абстрактного типа данных. В этом случае закрытая ( private ) часть определяет данные объекта и служебные функции, а функции-члены общей части реализуют методы работы с объектом.
Изменим структуру date так, чтобы скрыть представление данных (инкапсуляция данных):