ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одномерный массив) - структура
данных с фиксированным числом элементов одного и того же типа ти-
па. Каждый элемент вектора имеет уникальный в рамках заданного
вектора номер. Обращение к элементу вектора выполняется по имени
вектора и номеру требуемого элемента.
МАШИННОЕ ПРЕДСТАВЛЕНИЕ. АДРЕСАЦИЯ ЭЛЕМЕНТОВ СТРУКТУР. Эле-
менты вектора размещаются в памяти в подряд расположенных ячейках
памяти. Под элемент вектора выделяется количество байт памяти,
определяемое базовым типом элемента этого вектора. Необходимое
число байтов памяти для хранения одного элемента вектора называ-
ется слотом. Размер памяти для хранения вектора определяется про-
изведением длины слота на число элементов.
В языках программирования вектор представляется одномерным
массивом с синтаксисом описания вида (PASCAL):
<Имя> : array [n..k] of <тип>;
где n-номер первого элемента, k-номер последнего элемента. Предс-
тавление в памяти вектора будет такое, как показано на рис. 3.1.
@ Имя│+0 │+Sizeof(тип) │ │+(k-n)*Sizeof(тип)
├─────────┼──────────────┐ ├───────────┼─────────────┐
│ Имя [n] │Имя [n+1] │...│ Имя [k-1] │ Имя [k] │
└─────────┴──────────────┘ └───────────┴─────────────┘
Рис. 3.1. Представление вектора в памяти
где @ Имя -адрес вектора или, что тоже самое, адрес первого эле-
мента вектора,
Sizeof(тип)-размер слота (количество байтов памяти для запи-
си одного элемента вектора),
(k-n)*Sizeof(тип) - относительный адрес элемента с номером
k, или, что тоже самое, смещение элемента с номером k.
Например:
var m1:array[-2..2] of real;
представление данного вектора в памяти будет как на рис. 3.2.
Смещение элем. ┌────────┬────────┬────────┬────────┬────────┐
относ.адреса m1 │ +0 │ +6 │ +12 │ +18 │ +24 │
(байт) ├────────┼────────┼────────┼────────┼────────┤
Значения │ m1[-2] │ m1[-1] │ m1[0] │ m1[1] │ m1[2] │
эл.массива └────────┴────────┴────────┴────────┴────────┘
Рис. 3.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 байта, поэтому
на каждый элемент вектора выделяется по два байта. Тогда таблица
3.1 смещений элементов вектора относительно @Mas выглядит так:
Таблица 3.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(тип) (3.1)
Это вычисление не может быть выполнено на этапе компиляции,
так как значение переменной i в это время еще неизвестно. Следо-
вательно, вычисление адреса элемента должно производиться на эта-
пе выполнения программы при каждом обращении к элементу вектора.
Но для этого на этапе выполнения, во-первых, должны быть известны
параметры формулы (3.1): @Имя Sizeof(тип), n, а во-вторых, при
каждом обращении должны выполняться две операции умножения и две
- сложения. Преобразовав формулу (3.1) в формулу (3.2),
@Имя[i] = A0 + i*Sizeof(тип) ─┐ (3.2)
A0 = @Имя - n*Sizeof(тип) ─┘
сократим число хранимых параметров до двух, а число операций - до
одного умножения и одного сложения, так как значение A0 может
быть вычислено на этапе компиляции и сохранено вместе с Size-
of(тип) в дескрипторе вектора. Обычно в дескрипторе вектора сох-
раняются и граничные значения индексов. При каждом обращении к
элементу вектора заданное значение сравнивается с граничными и
программа аварийно завершается, если заданный индекс выходит за
допустимые пределы.
Таким образом, информация, содержащаяся в дескрипторе векто-
ра, позволяет, во-первых, сократить время доступа, а во-вторых,
обеспечивает проверку правильности обращения. Но за эти преиму-
щества приходится платить, во-первых, быстродействием, так как
обращения к дескриптору - это команды, во-вторых, памятью как для
размещения самого дескриптора, так и команд, с ним работающих.
Можно ли обойтись без дескриптора вектора?
В языке C, например, дескриптор вектора отсутствует, точнее,
не сохраняется на этапе выполнения. Индексация массивов в C обя-
зательно начинается с нуля. Компилятор каждое обращение к элемен-
ту массива заменяет на последовательность команд, реализующую
частный случай формулы (3.1) при n = 0:
@Имя[i] = @Имя + i*Sizeof(тип)
Программисты, привыкшие работать на C, часто вместо выраже-
ния вида: Имя[i] употребляют выражение вида: *(Имя+i).
Но во-первых, ограничение в выборе начального индекса само
по себе может являться неудобством для программиста, во-вторых,
отсутствие граничных значений индексов делает невозможным конт-
роль выхода за пределы массива. Программисты, работающие с C, хо-
рошо знают, что именно такие ошибки часто являются причиной "за-
висания" C-программы при ее отладке.