2. Абстрактный тип данных (1)

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

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

2. Что такое данные?

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

3.

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

4. Что такое тип данных?

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

5. Примеры типов данных

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

6. Целочисленные типы

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

7. Вещественный тип

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

8. Логический тип

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

9. Символьный тип

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

10. Перечисляемый тип

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

11. Интервальный тип

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

12. Общее для типов данных

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

13. Определение

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

14. АТД – обобщение типов данных

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

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

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

16. Пример

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

17. Уровни абстракции

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

18. Пример абстракции на уровне пользователя

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

19. Пример абстракции на уровне программиста

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

20. Конструкторы АТД

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

21. Рекомендации к выбору операций абстрактного типа данных

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

22. Первичный конструктор

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

23. Использование скрытых типов

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

24. Что такое спецификация и реализация у абстрактного типа данных

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

25. Классификация АТД по способу описания и защиты

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

26. Составляющие спецификации

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

27. П р и м е р спецификации

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

28. РЕАЛИЗАЦИЯ АБСТРАКТНОГО ТИПА ДАННЫХ

• Реализацию удобнее делать с помощью объектноориентированных языков программирования, таких как
C++ или Java, в которых абстрактные типы данных
поддерживаются с помощью классов
• Реализация АТД включает конкретное описание
объектов определяемого типа и реализацию операций
этого типа. Это означает, что объекты описываются
либо как данные простых типов, либо как массивы,
записи или объединения. Причем используются
предопределенные типы данных или АТД,
определенные ранее.
• Реализация операций состоит в описании подпрограмм,
выполняющих необходимые действия с указанными
объектами. Например операции +, *, = .. и т.п, но при
этом скрывается сама реализация этих операций.
28