ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых
местоположения элементов со значениями отличными от фонового, мо-
гут быть математически описаны, т. е. в их расположении есть ка-
кая-либо закономерность.
Элементы, значения которых являются фоновыми, называют нуле-
выми; элементы, значения которых отличны от фонового, - ненулевы-
ми. Но нужно помнить, что фоновое значение не всегда равно нулю.
Ненулевые значения хранятся, как правило, в одномерном мас-
сиве, а связь между местоположением в исходном, разреженном, мас-
сиве и в новом, одномерном, описывается математически с помощью
формулы, преобразующей индексы массива в индексы вектора.
На практике для работы с разреженным массивом разрабатывают-
ся функции:
а) для преобразования индексов массива в индекс вектора;
б) для получения значения элемента массива из ее упакованного
представления по двум индексам (строка, столбец);
в) для записи значения элемента массива в ее упакованное предс-
тавление по двум индексам.
При таком подходе обращение к элементам исходного массива
выполняется с помощью указанных функций. Например, пусть имеется
двумерная разреженная матрица, в которой все ненулевые элементы
расположены в шахматном порядке, начиная со второго элемента. Для
такой матрицы формула вычисления индекса элемента в линейном
представлении будет следующей : 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 │