Работа с пользовательскими типами данных. Создание собственного типа.

 

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

 

Все пользовательские типы данных можно разбить на 2 типа:

- простые: перечисляемые (все возможные значения), интервальные (интервал значений; только для порядковых). К таким типам данных применяется прямая адресация

- структурированные (применяется косвенная или индексная адресация).

 

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

 

Типы объявляются в секции type.

Формат записи типа:

 

Type

Имя = (существующий тип, перечисляемый тип, интервал, запись, множество, процедура и т.д.)

 

16. Организация работы с записями. Записи с вариантами.

Запись – структурированный тип, состоящий из набора компонентов, к которым можно обратиться однократно через указание одного имени. Никаких ограничений на количество компонентов и их структурный состав не накладывается.

 

Для того, чтобы выполнить создание записи, необходимо определить тип в разделе типов.

 

Type

TBuffer = record

 

end;

 

Элементы записи называются полями, а обращение к ним производится через использование их имен – идентификаторов полей. Отличие записи от обычной переменной состоит в том, что имена полей должны предваряться ссылкой на идентификатор записи и отделяться от него точкой. Такая запись называется уточняющий идентификатор.

 

Для того, чтобы избежать дублирования имени переменной при обращении к компонентам, используют оператор with. Данный оператор определяет, что все дальнейшие обращения к полям записи будут производиться без указания переменной.

 

Записи с вариантами – особый тип, набор компонентов которого определяется значением одного из компонентов. Запись с вариантом в своей структуре имеет ключевое слово case, после которого указывается имя компонента, значение которого определяет возможность выбора состава.

 

В зависимости от селектора в записи с вариантами формируется соответствующий вариант; обращение будет выполняться по именам полей, объявленным в структуре.

 

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

 

В ряде случаев удобно использовать записи-константы. Типичный случай – координаты точки:

Const

Origin: TPoint = (X: 0; Y: -1);

 

 

Множества. Операции над множествами. Примеры использования.

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

 

Все элементы множества должны принадлежать одному из порядковых типов, содержащему не более 256 значений. Этот тип называется базовым типом множества. Базовый тип задается интервалом или перечислением.

Область значений множества – набор всевозможных подмножеств, составленных из элементов базового типа. Значения элементов множества указываются в квадратных скобках. Если множество не имеет элементов, оно называется пустым и обозначается как [ ]. Количество элементов множества называется его мощностью.

 

Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char, boolean и производные от них типы.

 

Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Максимальное число элементов множества 256, а данные типа множество могут занимать не более 32 байт.

 

Не имеет значения порядок записи элементов множества внутри конструктора. Например, [1, 2, 3] и [3, 2, 1] — это эквивалентные множества.

Каждый элемент во множестве учитывается только один раз. Поэтому множество [1, 2, 3, 4, 2, 3, 4, 5] эквивалентно [1..5].

 

Нельзя вводить значения во множественную переменную процедурой ввода Read и выводить процедурой вывода Write.

 

Формат записи:

Type

CharSet = set of Char;

 

Допустимые операции для множеств – это объединение (+), пересечение (*), разность (-), операция включения (in), =, <>, >=, <=.

 

Объединение – множество, состоящее из элементов, входящих хотя бы в одно из множеств A или B.

Пересечение – множество, состоящее из элементов, одновременно входящих во множество A и во множество B.

Разность – множество, состоящее из элементов множества A, не входящих во множество B.

 

Операция in позволяет проверить принадлежность значения множеству. Если X входит в M, то эта операция возвращает True, иначе – False.

 

Добавление нового элемента в множество может происходить с помощью операции объединения: Include; удаление элемента – с помощью операции "разность множеств": Exclude.

 

Приоритеты: *; +-; =, >=, <=, …

 

Примеры использования:

- Некоторые выражения можно записать более компактно, например: if (n >= 10) and (n <= 99) then -> if n in [10..99] then.

- Сохранение в строке только первых вхождений символов.

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

 

Классификация структур данных. Элементарные структуры данных на основе статической памяти. Стек, очередь, дек.

 

Все элементарные структуры данных можно классифицировать по ряду признаков:

- По сложности: простые и интегрированные

Простые – такие структуры данных, которые не могут быть разделены на составные части.

Интегрированные – структуры данных, состоящие из простых или интегрированных структур.

Конструируются пользователем.

- По способу представления: физические и логические

Физические структуры определяют, каким образом данные размещаются в памяти.

Логические (абстрактные) рассматриваются без учета машинного представления.

- По наличию связи между элементами данных: несвязные и связные.

- По изменчивости: статические, полустатические и динамические.

Статические – массивы, множества, записи и таблицы.

Полустатические – стеки, очереди и деки, т.е. структуры, имеющие определенные правила доступа к

собственным элементам. В таких структурах в каждый момент времени можно получить доступ

только к одному элементу.

Динамические – линейные или связные списки, не имеющие определенных операций доступа к

элементам. В любой момент времени можно получить доступ к произвольному элементу списка.

- По характеру упорядоченности элементов: линейные и нелинейные.

Линейные: в зависимости от характера расположения в памяти разделяют на структуры с

последовательным доступом и структуры с произвольным доступом.

Последовательный доступ: стеки, очереди.

Произвольный доступ: односвязные и двусвязные списки.

Нелинейные: представляют собой многосвязные списки – графы или деревья; каждый элемент в

один момент времени может быть связан с несколькими другими элементами структуры.

- По виду памяти, используемой для хранения данных: в ОЗУ или на внешних носителях.

 

 

Среди элементарных структур имеются структуры со строго определенными правилами доступа: стек, очередь, дек.

Правила доступа определяют, как осуществляется вставка и удаление элемента в структуре.

 

Стек.

Стек (stack) – полустатическая структура, правила доступа к элементам которой определяются как LIFO (первый вошел, последний вышел). Стек имеет указатель на дно, т.е. 1 элемент стека. Если на дне нет элемента, то стек является пустым.

 

Для работы со стеком определяется вершина стека. В зависимости от выбранной стратегии вершина стека может указывать на последнюю занятую или первую свободную ячейку стека.

 

Для организации работы со стеком используют 2 операции: push/pop.

push: запись элемента в вершину стека с последующим увеличением значения указателя вершины.

pop: извлечение элемента из стека с уменьшением значения указателя, при этом считанный элемент считается более недоступным в стеке.

 

Операции: Push, Pop, Empty, StackTop (прочтение без удаления). Структура – record elems: []; top.

StackTop: ret elems[top]

InitStack: top:= 0;

FullStack: top:= stacksize;

EmptyStack: ret top = 0;

Очередь.

Очередь - полустатическая структура, для работы с которой используются два указателя: хвост и голова. Голова хранит указатель на первые элемент очереди, хвост может указывать на последний занятый либо первый свободный элемент. Правила доступа к элементам очереди – FIFO (First In, First Out).

 

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

 

Операции:

Clear, Remove (inc head), Insert (inc tail), Empty

 

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