Глава 6. Структурные типы данных
Переменные структурного типа содержат более чем одну величину. Структурные типы включают множества, массивы, записи, файлы, классы. За исключением множеств, которые содержат только порядковые величины, структурные типы могут содержать другие структурные типы.
По умолчанию, величины в структурном типе выравниваются по границам Word или DWord для более быстрого доступа. При объявлении структурного типа, можно включить зарезервированное слово packed для того, чтобы сжимать память данных. Например,
type TNumbers = packed array[1..100] of Real;
Использование packed замедляет доступ к данным и, в случае символьного массива, влияет на совместимость типов.
6.1. Совместимость типов
Object Pascal накладывает строгие ограничения на совместимость типов данных. Нельзя, например, переменной целого типа присвоить вещественное значение или строке присвоить целое. В том случае, если типы не совместимы, появляется сообщение «Type mismatch».
Для совместимости типов в выражениях необходимо выполнение одного из условий:
Оба типа одинаковы;
Оба типа - вещественные;
Оба типа - целые;
Один тип является поддиапазоном второго;
Оба типа являются отрезками одного и того же базового типа;
Оба типа являются множественными типами с совместимыми базовыми типами;
Один тип Pointer, второй - любой ссылочный тип.
Для совместимости типов Т1 и Т2 по присваиванию необходимо выполнение одного из условий:
Т1 и Т2 имеют тождественные типы, и ни один из них не является файловым типом или структурным типом, содержащим поле файлового типа.
Т1 и Т2 являются совместимыми порядковыми типами и значение типа Т2 попадают в диапазон значений Т1.
Т1 и Т2 являются вещественными типами, и значения типа Т2 попадают в диапазон значений Т1.
Т1 является вещественным типом, а Т2 - целочисленным типом.
Т1 и Т2 являются строковыми типами.
Т1 является строковым типом, а Т2 - символьным типом (Char).
Т1 и Т2 являются совместимыми множественными типами, и все значения типа Т2 попадают в диапазон значений Т1.
Т1 и Т2 являются совместимыми типами указателей.
Для приведения типов переменых или выражений можно использовать имя типа. Например,
Ch:=Char(n); n:=Byte(ch);
Преобразование может привести к уменьшению или увеличению объема памяти: n:=Integer(x).
6.2. Массивы
Массив представляет индексированный набор элементов одного типа (называемого базовым типом). Т.к. каждый элемент имеет уникальный номер, массив, в отличие от множеств, может содержать одну и ту же величину неоднократно. Массив может быть распределен статически или динамически.
6.2.1. Статические массивы
Определяется конструкцией
array[index_1, ..., index_N] of ТИП
где каждый index - порядкового типа с областью изменения, не превышающей 2GB. Т.к. index индексирует массив, количество элементов массива ограничивается размером index. Обычно, index целого типа.
В самом простом случае одномерного массива, есть только единственный index. Например,
var MyArray: array[10..100] of Char;
объявляет переменную MyArray, которая содержит массив из 91 символьной величины. MyArray[13] обозначает тринадцатый символ в MyArray. Если создан статический массив, но не назначены значения во все элементы, неиспользованные элементы занимают память и содержат произвольные данные.
Многомерный массив. Например,
type TMatrix = array[1..10] of array[1..10] of Real;
эквивалентно
type TMatrix = array[1..10, 1..10] of Real;
Переменная типа TMatrix представляет собой массив из 100 вещественных величин. Переменная MyMatrix: TMatrix может индексироваться как MyMatrix[2,5] или MyMatrix[2][5].
Стандартные функции Low и High действуют для идентификаторов типа массива и переменных. Они возвращают нижние и верхнии границы массива. Стандартная функция Length возвращает количество элементов первого измерения массива.
Одномерный, упакованный, статический массив символьных величин называется упакованной строкой. Типы упакованной строки совместимы с типами строки и с другими типами упакованной строки, имеющей такое же количество элементов.
Элементы одномерного массива (вектора) размещаются в памяти в подряд расположенных ячейках памяти. Под элемент массива выделяется количество байт памяти, определяемое базовым типом элемента этого вектора. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом. Размер памяти для хранения массива определяется произведением длины слота на число элементов.
В языках программирования вектор представляется одномерным массивом с синтаксисом описания вида (PASCAL):
< Имя > : array [n..k] of < тип >;
где n-номер первого элемента, k-номер последнего элемента. Представление в памяти вектора будет такое, как показано на рис. 6.1.
Рис. 6.1. Представление вектора в памяти
где @ Имя - адрес вектора или, что тоже самое, адрес первого элемента вектора,
Sizeof(тип) - размер слота (количество байтов памяти для записи одного элемента вектора), (k-n)*Sizeof(тип) - относительный адрес элемента с номером k, или, что тоже самое, смещение элемента с номером k.
Например:
var m1:array[-2..2] of real;
представление данного вектора в памяти будет как на рис. 6.2.
Рис. 6.2. Представление вектора m1 в памяти
В языках, где память распределяется до выполнения программы на этапе компиляции (C, PASCAL, FORTRAN), при описании типа вектора граничные значения индексов должны определены. В языках, где память может распределяться динамически (ALGOL, PL/1), значения индексов могут быть заданы во время выполнения программы.
Количество байтов непрерывной области памяти, занятых одновременно вектором, определяется по формуле:
ByteSise = ( k - n + 1 ) * Sizeof (тип)
Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение i-ого элемента вектора определяется по формуле:
ByteNumer = ( i- n ) * Sizeof (тип),
а адрес его: @ ByteNumber = @ имя + ByteNumber.
где @ имя - адрес первого элемента вектора.
Например:
var МAS: array [ 5..10 ] of word.
Базовый тип элемента вектора - Word требует 2 байта, поэтому на каждый элемент вектора выделяется по два байта. Тогда таблица 6.1 смещений элементов вектора относительно @Mas выглядит так:
Таблица 6.1.
Смещение |
+ 0 |
+ 2 |
+ 4 |
+ 6 |
+ 8 |
+ 10 |
Идентификатор поля |
MAS[5] |
MAS[6] |
MAS[7] |
MAS[8] |
MAS[9] |
MAS[10] |
Этот вектор будет занимать в памяти: (10-5+1)*2 = 12 байт. Смещение к элементу вектора с номером 8: (8-5)*2 = 6. Адрес элемента с номером 8: @ MAS + 6.
При доступе к вектору задается имя вектора и номер элемента вектора. Таким образом, адрес i-го элемента может быть вычислен как:
@Имя[i] = @Имя + i*Sizeof(тип) - n*Sizeof(тип) (6.1)
Это вычисление не может быть выполнено на этапе компиляции, так как значение переменной i в это время еще неизвестно. Следовательно, вычисление адреса элемента должно производиться на этапе выполнения программы при каждом обращении к элементу вектора. Но для этого на этапе выполнения, во-первых, должны быть известны параметры формулы (3.1): @Имя Sizeof(тип), n, а во-вторых, при каждом обращении должны выполняться две операции умножения и две - сложения. Преобразовав формулу (6.1) в формулу (6.2),
@Имя[i] = A0 + i*Sizeof(тип) -- (6.2)
A0 = @Имя - n*Sizeof(тип) --
сократим число хранимых параметров до двух, а число операций - до одного умножения и одного сложения, так как значение A0 может быть вычислено на этапе компиляции и сохранено вместе с Sizeof(тип) в дескрипторе вектора. Обычно в дескрипторе вектора сохраняются и граничные значения индексов. При каждом обращении к элементу вектора заданное значение сравнивается с граничными и программа аварийно завершается, если заданный индекс выходит за допустимые пределы.
Таким образом, информация, содержащаяся в дескрипторе вектора, позволяет, во-первых, сократить время доступа, а во-вторых, обеспечивает проверку правильности обращения. Но за эти преимущества приходится платить, во-первых, быстродействием, так как обращения к дескриптору - это команды, во-вторых, памятью как для размещения самого дескриптора, так и команд, с ним работающих.
Можно ли обойтись без дескриптора вектора?
В языке C, например, дескриптор вектора отсутствует, точнее, не сохраняется на этапе выполнения. Индексация массивов в C обязательно начинается с нуля. Компилятор каждое обращение к элементу массива заменяет на последовательность команд, реализующую частный случай формулы (6.1) при n = 0:
@Имя[i] = @Имя + i*Sizeof(тип)
Программисты, привыкшие работать на C, часто вместо выражения вида: Имя[i] употребляют выражение вида: *(Имя+i).
Но, во-первых, ограничение в выборе начального индекса само по себе может являться неудобством для программиста, во-вторых, отсутствие граничных значений индексов делает невозможным контроль выхода за пределы массива. Программисты, работающие с C, хорошо знают, что именно такие ошибки часто являются причиной "зависания" C-программы при ее отладке.
Массив - такая структура данных, которая характеризуется:
фиксированным набором элементов одного и того же типа;
каждый элемент имеет уникальный набор значений индексов;
количество индексов определяют мерность массива, например, два индекса - двумерный массив, три индекса - трехмерный массив, один индекс - одномерный массив или вектор;
обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента.
Другое определение: массив - это вектор, каждый элемент которого - вектор.
Синтаксис описания массива представляется в виде:
< Имя > : Array [n1..k1] [n2..k2] .. [nn..kn] of < Тип >.
Для случая двумерного массива:
Mas2D : Array [n1..k1] [n2..k2] of < Тип >, или
Mas2D : Array [n1..k1 , n2..k2] of < Тип >
Наглядно двумерный массив можно представить в виде таблицы из (k1-n1+1) строк и (k2-n2+1) столбцов.