Векторы

Вектор (одномерный массив) – структура данных с фиксированным числом однотипных элементов. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.

Элементы вектора размещаются в памяти в расположенных подряд (смежных) ячейках. Под элемент вектора выделяется количество байт памяти, определяемое базовым типом элемента вектора. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом. Размер памяти для хранения вектора определяется произведением длины слота на число элементов. В языках программирования вектор представляется одномерным массивом:

< имя >: array [n..k] of < тип >;

где n-номер первого элемента, k-номер последнего элемента.

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

Табл. 4.1. Представление вектора в памяти.

Смещение	+0	+SizeOf(тип)	…	+(k-n)*SizeOf(тип)
Идентификатор	Имя [n]	Имя [n+1]	…	Имя [k]

В таблице приняты следующие обозначения:

@Имя - адрес вектора (адрес первого элемента вектора);

SizeOf(тип) - размер слота (количество байтов памяти для записи одного элемента вектора);

(k-n)×SizeOf(тип) - относительный адрес элемента с номером k (смещение элемента с номером k).

Пусть объявлен следующий вектор:

var v: array [-2..2] of real;

Представление вектора в памяти показано в табл. 4.2.

Табл. 4.2. Представление вектора v в памяти.

Смещение	+0	+6	+12	+18	+24
Идентификатор	v[-2]	v[-1]	v[0]	v[1]	v[2]

В языках, где память под массив выделяется на этапе компиляции (C, PASCAL, FORTRAN), при описании типа вектора граничные значения индексов должны быть определены. В языках, где память может распределяться динамически (ALGOL, PL/1), значения индексов могут быть заданы во время выполнения программы.

Количество байт непрерывной области памяти, одновременно занятых вектором равно:

ByteSize = (k-n+1)·SizeOf(тип)

Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение i-ого элемента вектора равно:

ByteNumer = (i-n)·SizeOf(тип)

а его адрес:

@ByteNumber = @имя + ByteNumber

где @имя - адрес первого элемента вектора.

Например:

var v: array [5..10] of Word

Базовый тип элемента вектора Word, поэтому на каждый элемент выделяется по два байта. Смещения элементов относительно @v показано в табл. 4.3.

Табл. 4.3. Представление вектора v.

Смещение	+0	+2	+4	+6	+8	+10
Идентификатор	v[5]	v[6]	v[7]	v[8]	v[9]	v[10]

Данный вектор будет занимать в памяти: (10-5+1)·2 = 12 байт.
Смещение к элементу вектора с номером 8: (8-5) ·2 = 6.
Адрес элемента с номером 8: @v + 6.

При доступе к вектору задается имя вектора и номер элемента вектора. Адрес i-го элемента может быть вычислен:

@Имя[i] = @Имя+i·SizeOf(тип)-n·SizeOf(тип) (4.1)

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

@Имя[i] = A0+i·SizeOf(тип) (4.2)

где A0 = @Имя-n·SizeOf(тип)

Число хранимых параметров может быть сокращено до двух, а число операций – до одного умножения и одного сложения, т.к. значение A0 может быть вычислено на этапе компиляции и сохранено вместе с SizeOf(тип) в дескрипторе вектора.

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

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

В языке C, например, дескриптор вектора отсутствует, точнее, не сохраняется на этапе выполнения. Индексация массивов в C обязательно начинается с нуля. Компилятор каждое обращение к элементу массива заменяет на последовательность команд, реализуя частный случай формулы (4.1) при n = 0.

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