Лабораторная работа №3 простейшие статические структуры. Дескриптор массива

Начальные определения

Под массивом в программировании понимается линейная структура данных фиксированного размера, элементы которой размещаются в оперативной памяти последовательно. Массив характеризуется своим именем, размерностью, граничными парами и типом элемента. Элемент массива называется слотом.

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

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

Адрес произвольного элемента массива определяется следующими характеристиками:

•  адресом первого элемента;

•  порядком размещения элементов в оперативной памяти;

•  размером памяти, занимаемой одним элементов.

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

Чаще всего применяется линеаризация по строкам (элементы размещаются в памяти в порядке следования строк) или по столбцам. Иногда, имея ввиду линеаризацию по строкам, говорят, что последний индекс изменяется быстрее, чем первый. Аналогично, при линеаризации по столбцам быстрее изменяется первый индекс.

Пример. Пусть задан трехмерный массив B[1..2,1..2,1..2]. При линеаризации его по строкам элементы в памяти будут располагаться в следующем порядке: B[1,1,1]; B[1,1,2]; B[1,2,1]; B[1,2,2]; B[2,1,1]; B[2,1,2]; B[2,2,1]; B[2,2,2]. При линеаризации по столбцам порядок будет таким: B[1,1,1]; B[2,1,1]; B[1,2,1]; B[2,2,1]; B[1,1,2]; B[2,1,2]; B[1,2,2]; B[2,2,2].

Вычисление адреса элемента

Рассмотрим частный случай n–мерного массива при n=1. Такой одномерный массив называется вектором. Пусть имеется вектор V[i..k] с длиной слота L, и задан индекс j искомого элемента.

Тогда имеем:

Адрес(V[j]) = Адрес(V[i]) + L*(j – i) =

= Адрес(V[i]) – L*i + L*j.

Заметим, что первые два слагаемые этой суммы не зависят от индекса (j) отыскиваемого слота и потому могут быть вычислены заранее. Нетрудно видеть, что эта постоянная величина в точности соответствует адресу нулевого слота (чтобы в этом убедиться, достаточно подставить в выражение адреса j–го элемента значение j=0). Правда, сам нулевой слот возможно и отсутствует в массиве, но если бы он был, то располагался бы именно по такому адресу.

Итак, окончательно получаем:

Адрес(V[j]) = Адрес(V[0]) + L*j

Рассмотрим случай, когда n=2. Пусть задан массив V[i₁..k₁,i₂..k₂], и пусть искомым является элемент V[j₁,j₂]. При линеаризации по строкам имеем:

Адрес(V[j₁,j₂])=Адрес(V[i₁,i₂])+ +L*((k₂–i₂+1)*(j₁–i₁)+(j₂–i₂)).

Раскрыв скобки и перегруппировав слагаемые, получим:

Адрес(V[j₁,j₂])= Адрес(V[i₁,i₂]) – L*(i₁*(k₂–i₂+1)+i₂)+ +L*(k₂–i₂+1)*j₁+L*j₂ = Адрес(V[0,0])+D₁*j₁+D₂*j₂,

где D₁, D₂ – так называемые индексные множители, соответственно равные: D₁=L*(k₂–i₂+1) и D₂=L; V[0,0] – нулевая компонента массива.

Целесообразность выделения постоянных слагаемых и множителей объясняется возможностью их предварительного вычисления и многократного в дальнейшем использования.

Таким образом, для эффективного вычисления адреса слота массива необходимо хранить некоторые заранее вычисленные значения.

Специальная информация, предназначенная для обеспечения корректной и быстрой работы с элементами структуры данных, называется дескриптором этой структуры.

Пусть задан произвольный n мерный массив со следующими граничными парами: V[i₁..k₁, i₂..k₂, ... , i_n..k_n] и пусть длина слота равна L. В этом случае формула доступа принимает вид:

Адрес(V[j₁,j₂,...,j_n]) = Адрес(V[0,0,...,0]) + D₁*j₁ + + D₂*j₂ + ... + D_n*j_n.

Значение индексных множителей зависит от выбранного способа линеаризации.

При отображении строками индексные множители задаются рекуррентной формулой:

D_n=L, D_m=(k_m+1–i_m+1+1)*D_m+1, при m=n–1,n–2,…, 1.

При отображении столбцами формула имеет вид:

D₁=L, D_m=(k_m–1 – i_m–1+1)*D_m–1 при m = 2, 3, ..., n.

Возможная структура дескриптора массива представлена на таблице 1.

Таблица 1. Пример дескриптора массива

имя массива
адрес нулевого слова
адрес первого (начального) слота массива
размерность массива (n)
i1	k2
i2	k2
. . .	. . .
in	kn
D1
. . .
Dn
тип элемента	длина слота (L)