Массивы с математическим описанием местоположения нефоновых элементов.

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

Элементы, значения которых являются фоновыми, называют нулевыми; элементы, значения которых отличны от фонового, - ненулевыми. Но нужно помнить, что фоновое значение не всегда равно нулю.

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

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

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

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

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

При таком подходе обращение к элементам исходного массива выполняется с помощью указанных функций. Например, пусть имеется двумерная разреженная матрица, в которой все ненулевые элементы расположены в шахматном порядке, начиная со второго элемента. Для такой матрицы формула вычисления индекса элемента в линейном представлении будет следующей : 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 модуля. Доступ к содержимому матрицы извне возможен только через входные точки PutTab, 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.