4. Массивы: их функциональная спецификация, логическое описание и физическое представление. Особенности представления разреженных массивов

 

Массивы

 

            Для известного типа Т и двух целых b и B (b £ B) определим тип МАССИВТ,b,B одномерных массивов с элементами типа Т и границами [b...B].

 

Функциональная спецификация

            Пусть Ib,B – тип, определяемый перечислением как множество  индексов: Ib,B = (b, b+1, …, B-1, B). Тогда определим МАССИВТ,b,B, исходя из типов Ib,B и Т, с помощью следующих операций:

создание:       создание_массива – создает массив типа Т с границами b и B, причем значения  элементов массива пока не определены;

доступ:           значение_элемента – по индексу i извлекается элемент m i;

модификация:

                        изменение_элемента – по индексу i массив M преобразуется в массив M*, где M = {m1, …, mi-1, mi, mi+1, …, mn}, M*= {m1, …, mi-1, m*i, mi+1, …, mn}.

            Важным моментом для массивов является понятие прямого доступа: каждый элемент полностью определяется заданием имени массива и индекса; чтобы до него добраться, нет необходимости в серии операций  над другими элементами, как в случае линейных списков.

            Для многомерных массивов необходимо указать границы всех их измерений:, где bk £ ik £ Bk для 1£  k £  n.

 

Логическое описание

      На логическом уровне массивы можно определить рекурсивно по числу измерений: одномерным массивом типа Т с границами (b, B) называется соединение (B-b+1) элементарных данных типа Т; N-мерным массивом (или массивом n измерений) типа Т с границами (b1, B1), (b2, B2), … , (bn, Bn) (n ³ 2) называется соединение (B1-b1+1) массивов типа Т размерности (n-1) с границами (b2, B2), … , (bn, Bn).

 

Физическое представление

            Под массив выделяется сплошная область памяти. Если массив одномерный и каждый его элемент занимает p слов, то адрес i-го элемента можно найти по формуле: ai = ab+(i-b)p, где ab – это адрес первого элемента.

            Для массивов двух и более измерений нет единого способа расположения его элементов в памяти ЭВМ. Так, например, транслятор ФОРТРАНа размещает массив по столбцам, транслятор ПЛ/1 – по строкам, а в АЛГОЛ­_W способ размещения вообще не уточняется стандартом.

            Для больших массивов сплошное представление иногда оказывается настолько неприемлемым, что массив приходится “разбивать на части” и каждую такую часть хранить по разным адресам в памяти ЭВМ. Например, двумерный массив можно хранить по строкам, причем адреса начала каждой строки находятся в специальном массиве указателей:

·     ®(mb1, b2), (mb1, b2+1),..., (mb1,B2)

·     ®(mb1+1, b2), (mb1+1, b2+1),..., (mb1+1, B2)

·                    ...

·     ®(mB1, b2), (mB1, b2+1),..., (mB1,B2).

            Безусловно, такой способ представления массивов отрицательно сказывается на эффективности программ, так как требует двойного доступа к памяти при каждом обращении к элементу двумерного массива; его обобщение на n  измерений требует  n доступов на элемент.

 

 

Представление разреженных массивов

            Массив, у которого  большинство элементов имеют одно и то же значение, называется разреженным.

            Пример 4.1. Пусть элементы матрицы M10´10 имеют следующие значения:

a12=17, a64=-8, a66=-2, a75=81, остальные элементы этой матрицы – нули. 

Тогда двумерный массив M[1:10, 1:10] – разреженный.

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

            Пусть для определенности массив М – двумерный с границами [1:m,1:n], и большая часть его элементов одинаковы и равны v. Решение представления такого массива  является компромиссом между обычным представлением массивов и представлением списков.

            Каждый элемент матрицы M [i, j] можно характеризовать триплетом [i, j, M [i, j]].  Имеет смысл рассматривать только  те триплеты, которые соответствуют отличным от v элементам М, и размещать их в списке. Элементы в списке триплетов размещают в соответствии с условиями конкретной задачи, либо в произвольном порядке, либо упорядоченными по некоторому критерию, например, по возрастанию сначала первого, а потом второго индекса. Кроме того, необходимо хранить в памяти ЭВМ значение по умолчанию v и границы m и n.