МАССИВЫ С МАТЕМАТИЧЕСКИМ ОПИСАНИЕМ МЕСТОПОЛОЖЕНИЯ НЕФОНОВЫХ

ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых

местоположения элементов со значениями отличными от фонового, мо-

гут быть математически описаны, т. е. в их расположении есть ка-

кая-либо закономерность.

Элементы, значения которых являются фоновыми, называют нуле-

выми; элементы, значения которых отличны от фонового, - ненулевы-

ми. Но нужно помнить, что фоновое значение не всегда равно нулю.

Ненулевые значения хранятся, как правило, в одномерном мас-

сиве, а связь между местоположением в исходном, разреженном, мас-

сиве и в новом, одномерном, описывается математически с помощью

формулы, преобразующей индексы массива в индексы вектора.

На практике для работы с разреженным массивом разрабатывают-

ся функции:

а) для преобразования индексов массива в индекс вектора;

б) для получения значения элемента массива из ее упакованного

представления по двум индексам (строка, столбец);

в) для записи значения элемента массива в ее упакованное предс-

тавление по двум индексам.

При таком подходе обращение к элементам исходного массива

выполняется с помощью указанных функций. Например, пусть имеется

двумерная разреженная матрица, в которой все ненулевые элементы

расположены в шахматном порядке, начиная со второго элемента. Для

такой матрицы формула вычисления индекса элемента в линейном

представлении будет следующей : L=((y-1)*XM+x)/2),

где L - индекс в линейном представлении;

x, y - соответственно строка и столбец в двумерном представлении;

XM - количество элементов в строке исходной матрицы.

В программном примере 3.1 приведен модуль, обеспечивающий

работу с такой матрицей (предполагается, что размер матрицы XM

заранее известен).

{===== Программный пример 3.1 =====}

Unit ComprMatr;

Interface

Function PutTab(y,x,value : integer) : boolean;

Function GetTab(x,y: integer) : integer;

Implementation

Const XM=...;

Var arrp: array[1..XM*XM div 2] of integer;

Function NewIndex(y, x : integer) : integer;

var i: integer;

begin NewIndex:=((y-1)*XM+x) div 2); end;

Function PutTab(y,x,value : integer) : boolean;

begin

if NOT ((x mod 2<>0) and (y mod 2<>0)) or

NOT ((x mod 2=0) and (y mod 2=0)) then begin

arrp[NewIndex(y,x)]:=value; PutTab:=true; end

else PutTab:=false;

end;

Function GetTab(x,y: integer) : integer;

begin

if ((x mod 2<>0) and (y mod 2<>0)) or

((x mod 2=0) and (y mod 2=0)) then GetTab:=0

else GetTab:=arrp[NewIndex(y,x)];

end;

end.

Сжатое представление матрицы хранится в векторе arrp.

Функция NewIndex выполняет пересчет индексов по вышеприве-

денной формуле и возвращает индекс элемента в векторе arrp.

Функция PutTab выполняет сохранение в сжатом представлении

одного элемента с индексами x, y и значением value. Сохранение

выполняется только в том случае, если индексы x, y адресуют не

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

возвращает true, иначе - false.

Для доступа к элементу по индексам двумерной матрицы исполь-

зуется функция GetTab, которая по индексам x, y возвращает выб-

ранное значение. Если индексы адресуют заведомо нулевой элемент

матрицы, функция возвращает 0.

Обратите внимание на то, что массив arrp, а также функция

NewIndex не описаны в секции IMPLEMENTATION модуля. Доступ к со-

держимому матрицы извне возможен только через входные точки Put-

Tab, GetTab с заданием двух индексов.

В программном примере 3.2 та же задача решается несколько

иным способом: для матрицы создается дескриптор - массив desc,

который заполняется при инициализации матрицы таким образом, что

i-ый элемент массива desc содержит индекс первого элемента i-ой

строки матрицы в ее линейном представлении. Процедура инициализа-

ции InitTab включена в число входных точек модуля и должна вызы-

ваться перед началом работы с матрицей. Но доступ к каждому эле-

менту матрицы (функция NewIndex) упрощается и выполняется быст-

рее: по номеру строки y из дескриптора сразу выбирается индекс

начала строки и к нему прибавляется смещение элемента из столбца

x. Процедуры PutTab и GetTab - такие же, как и в примере 3.1 поэ-

тому здесь не приводятся.

{===== Программный пример 3.2 =====}

Unit ComprMatr;

Interface

Function PutTab(y,x,value : integer) : boolean;

Function GetTab(x,y: integer) : integer;

Procedure InitTab;

Implementation

Const XM=...;

Var arrp: array[1..XM*XM div 2] of integer;

desc: array[1..XM] of integer;

Procedure InitTab;

var i : integer;

begin

desc[1]:=0; for i:=1 to XM do desc[i]:=desc[i-1]+XM;

end;

Function NewIndex(y, x : integer) : integer;

var i: integer;

begin NewIndex:=desc[y]+x div 2; end;

end.

РАЗРЕЖЕННЫЕ МАССИВЫ СО СЛУЧАЙНЫМ РАСПОЛОЖЕНИЕМ ЭЛЕМЕНТОВ. К

данному типу массивов относятся массивы, у которых местоположения

элементов со значениями отличными от фонового, не могут быть ма-

тематически описаны, т. е. в их расположении нет какой-либо зако-

номерности.

│ 0 0 6 0 9 0 0 │ Пусть есть матрица А размерности 5*7,

│ 2 0 0 7 8 0 4 │ в которой из 35 элементов только 10 от-

│10 0 0 0 0 0 0 │ личны от нуля.

│ 0 0 12 0 0 0 0 │

│ 0 0 0 3 0 0 5 │