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