Структурные типы данных

Структурные ТД содержат набор упорядоченных элементов, обработка которых проводится как над отдельными объектами, так и на уровне отдельных элементов. Эти ГД строятся из базовых типов и различаются функциями конструирования и механизмами обработки. В качестве основных структурных типов в работе рассматриваются массивы и записи.

Массивы. Функция конструирования массива осуществляется с помощью базовых типов путем отображения множества индексов и значений:

где I — множество индексов, Y — множество значений элементов массива. В общем случае отображение М может не быть взаимно однозначным, если в элементах массива (элементы с разными индексами) содержатся одинаковые значения. Множество 7 включает в себя множество значений перечислимого типа или отрезок целого типа. Элементы множества Y могут быть элементами любого типа, допустимого в теории структурной организации данных.

Над массивами выполняются операции:

• 1) отношение для упорядоченных массивов (определяется как совокупность операций отношения для всех элементов массивов);
• 2) сложение и вычитание однотипных массивов, т. е. массивов с одним и тем же множеством индексов (определяется как совокупность соответствующих операций над всеми элементами массивов с одинаковыми индексами);
• 3) умножение двухмерных массивов по правилам умножения матриц.

Операции сложения и вычитания выполняются только на числовых массивах.

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

где /(дг) — множество индексов для массива х, Y (x) — множество значений элементов массива х, Y {X¹) — множество значений элементов массива рассматриваемого типа, Т {[) — ТД индексов массива; Т {Y) — ТД множество значений элементов массивов типа V. К данному типу принадлежат только те массивы, у которых множества индексов совпадают, а множество значений их элементов принадлежат одному и тому же множеству рассматриваемого типа. Для всех jr и постоянное 7 отображение имеет вид

Множество Q? состоит только из одного предиката. Операции выполняются над массивами, как над единым структурным значением. Кроме того, над элементами множеств 7 и Y могут выполняться операции, соответствующие их ТД.

Многомерные массивы определяются рекурсивно. ТД T (Y) в описании массива V могут быть массивами: type Т = array Д/¹) of Д У¹), type ДУ¹) = array Д/²) of Д У²). Эти описания типов эквивалентны описанию: type Т = array Т (/' х У²) of ДУ). В нем множество индексов массивов, принадлежащих типу Т представлено в виде прямого произведения множеств значений для типов Д/¹) и Д/²).

Запись. Структурный тип запись, как и массив, состоит из нескольких компонентов, которые могут быть разнородными, т. с. принадлежат простым или структурным типам. Функция конструирования записей представляет конкатенацию отдельных компонентов. Множество значений тина запись — прямое произведение множества значений ее компонентов. Над записями выполняются только операции отношения.

Пусть запись состоит из п компонентов. Каждый m — компонент (т = 1,2,…, п) имеет тип Т'^т и ей соответствует алгебраическая система I'" ' = <�Х^т, Q^vm>. Индекс у_т — один из индексов ТД.

Алгебраическая система для записи имеет вид:

где S_Vi,…, S_y — селекторы, а У" ', …, У"" - ТД для компонентов записи.