Векторы. Логическая структура. Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа

ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени вектора и номеру требуемого элемента.

МАШИННОЕ ПРЕДСТАВЛЕНИЕ. АДРЕСАЦИЯ ЭЛЕМЕНТОВ СТРУКТУР. Элементы вектора размещаются в памяти в подряд расположенных ячейках памяти. Под элемент вектора выделяется количество байт памяти, определяемое базовым типом элемента этого вектора. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом. Размер памяти для хранения вектора определяется произведением длины слота на число элементов.

В языках программирования вектор представляется одномерным массивом с синтаксисом описания вида:

С: <тип_элементов> <Имя_массива>[N];

где N – количество элементов в массиве. Представление в памяти вектора будет такое, как показано на рис. 2.1.

@Имя	+0	+Sizeof(тип)			+(N-1)*Sizeof(тип)
	Имя [0]	Имя [1]	…	Имя [N-2]	Имя [N-1]

Рис. 2.1. Представление вектора в памяти

Здесь @ Имя - адрес вектора или, что то же самое, адрес первого элемента вектора, Sizeof(тип) - размер слота (количество байт памяти для записи одного элемента вектора),

(k)*Sizeof(тип) - относительный адрес элемента с номером k, или, что то же самое, смещение элемента с номером k. Заметьте, номерация элементов в массиме начинается с нуля.

Например: float m1[5];

представление данного вектора в памяти будет как на рис. 2.2.

Смещение элемента относит. m1 адреса (байт)	+0	+4	+8	+12	+16
Значения элем. массива	m1[0]	m1[1]	m1[2]	m1[3]	m1[4]

Рис. 2.2. Представление вектора m1 в памяти

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

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

ByteSise = (N) * Sizeof (тип)

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

ByteNumer = (i) * Sizeof (тип),

а адрес его: @ ByteNumber = @ имя + ByteNumber.

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

Например: short mas[6];

Базовый тип элемента вектора - SHORT требует 2 байта, поэтому на каждый элемент вектора выделяется по два байта. Тогда табл. 2.1 смещений элементов вектора относительно @Mas выглядит так:

Таблица 2.1

Номера элементов	№0	№1	№2	№3	№4	№5
Смещение, байт	+0	+2	+4	+6	+8	+10
Элемент массива	mas[0]	mas[1]	mas[2]	mas[3]	mas[4]	mas[5]

Этот вектор будет занимать в памяти: 6*2 = 12 байт.

Смещение к элементу вектора с номером 3: 3*2 = 6

Адрес элемента с номером 3: @ MAS + 6.

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

@Имя[i] = @Имя + i*Sizeof(тип) (2.1)

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

Программисты, привыкшие работать на C, часто вместо выражения вида: Имя[i] употребляют выражение вида: *(Имя+i).

Но, отсутствие жестких граничных значений индексов массива в языке С (нельзя массив задать, как <тип> <Имя>[n..k], где n, k – крайние индексы, как в языке PASCAL), делает невозможным контроль выхода за пределы массива. Программисты, работающие с C, хорошо знают, что именно такие ошибки часто являются причиной "зависания" C-программы при ее отладке. Таких минусов нету в языке PASCAL, там информация о границах и начале массива, сохраняется в его дискрипторе.

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