СД типа запись (прямое декартово произведение)

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

type Т = Record

S₁: T₁;

S₂: T₂;

……..

S_n: T_n;

End;

Здесь: T_i изменяется при i = 1, 2, …, n; S₁, …, S_n – идентификаторы полей; Т₁, …, T_n – типы данных. Если T_i также является в свою очередь записью, то S_i – иерархическая запись.

Если D_T1 – множество значений элементов типа Т₁, D_Т2 – множество значений элементов типа Т₂, …, D_Тn – множество значений элементов типа Т_n, то D_T – множество значений элементов типа Т будет определяться с помощью прямого декартова произведения: D_T = D_T1 ´ D_T2 ´ … ´ D_Тn. Другими словами, множество допустимых значений СД типа запись:

Допустимые операции для СД типа запись аналогичны операциям для СД типа массив.

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

Вообще, смещение – это адрес компоненты (поля) r_i относительно начального адреса записи r. Смещение вычисляется следующим образом:

k_i = S₁ + S₂ + … + S_i-1, i=1,2, …,n

где S_i – размер слота каждого элемента записи.

Дескриптор СД типа запись, в отличие от дескриптора СД типа массив, зависит от количества элементов записи.

СД типа таблица.

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

Классификация СД типа таблица:

СД типа таблица
неупорядоченная таблица	упорядоченная таблица	хеш-таблица
как отображение на массив	как отображение на список

Если один элемент d _i, то кортеж – это <d ₁, d ₂, …, d _n>, причем D _Ti Î d _i. Множество значений элементов типа Т (множество допустимых значений СД типа таблица) будет определяться с помощью прямого декартова произведения:

D_T = D_T1 ´ D_T2 ´ … ´ D_Тn, причем D _Ti Î <d ₁, d ₂, …, d _n>.

Сам же элемент таблицы можно представить в виде двойки <K, V>, где К – ключ, а V – тело элемента. В качестве ключа может быть разное число полей, которые определяют этот элемент. Ключ используется для операции доступа к элементу, так как каждый из ключей уникален для данного элемента. Таким образом, таблица является совокупностью двоек <K, V>.

На логическом уровне элемент СД типа таблица описывается следующим образом:

Type Element = record

Key: integer;

{описание остальных полей}

end;

При реализации таблицы как отображения на массив ее описание выглядит так:

Tabl = array [0.. N] of Element

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

Перед тем как определить операции, которые можно выполнять над таблицей рассмотрим классификацию операций:

1. Конструкторы – операции, которые создают объекты рассматриваемой структуры.

2. Деструкторы – операции, которые разрушают объекты рассматриваемой структуры. Признаком этой операции является освобождение памяти.

3. Модификаторы – операции, которые модифицируют соответствующие структуры объектов. К ним относятся динамические и полустатические модификаторы.

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

5. Итераторы – операторы доступа к содержимому объекта по частям в определенном порядке.

Операции над таблицей:

1. Операция инициализации (конструктор).

2. Операция включения элемента в таблицу (модификатор).

3. Операция исключения элемента из таблицы (модификатор).

4. Операции-предикаты:

а) таблица пуста / таблица не пуста (наблюдатель)

б) таблица переполнена / таблица не переполнена (наблюдатель).

5. Чтение элемента по ключу (наблюдатель).

Дата добавления: 2014-01-07