Специальные виды матриц. Пример

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

· треугольные матрицы, у которых 0-е элементы расположены над главной диагональю,

· ленточные матрицы ширины d >0, у которых все элементы a_ij, для которых abs(i-j) > d имеют одинаковые 0-е значения,

· зазреженные матрицы, у которых большинство элементов равны 0.

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

Пример

Пусть задана треугольная матрица вида:

В памяти ЭВМ представление матрицы будет следующим:

Т.о., для хранения элементов требуется n * (n + 1) / 2 ячеек вместо n². Индекс для доступа к a_ij–у элементу рассчитывается по формуле:

(i + 1) * i / 2 + j.

Не составляет труда специфицировать функцию для чтения ij-го элемента матрицы:

double getEl(double *p, int n, int i, int j, int *k)

{

if((i > n)||(j > n))

{

*k = -1; // выход за пределы изменения индексов

return 0.0;

}

if(j > i)

{

*k = 0; // признак корректного результата

return 0.0;

}

*k = 0; // признак корректного результата

return p[(i+1)*i/2+j];

}

Пример

Пусть задана следующая ленточная матрица с d=1:

Представление матрицы в виде вектора будет следующим:

Индекс для доступа к a_ij–у элементу рассчитывается по формуле:

i * (2*d +1) + j – i = i * 2 * d + j.

Разреженные матрицы могут быть представлены различными способами. Укажем 2 из них:

· последовательное сжатое представление,

· последовательное-связанное индексное сжатое представление.

В первом случае элементы матрицы за исключением 0-х размещают в линейном списке. Каждый элемент представлен тройками вида <i, j, a_ij>. Поиск ij-го элемента выполняется на основе последовательного просмотра всех элементов списка и сравнения первых двух элементов на соответствие заданным индексам.

Во втором случае, если размерность матрицы n x n, то ее представляют в виде n-списков и каждый элемент представлен тройкой:

<индекс столбца, значение элемента, ссылка на следующий элемент той же строки>.

Вопросы для самоконтроля

• Как указать компилятору, что указатель p типа void * ссылается в текущей точке программы на данные типа unsigned long?
• Что выполняют операции * и &?
• Какие операции применимы к указателям?
• Можно ли к указателям применить операции автоинкремента и автодекремента?
• Чем отличаются декларации char *p[10] и char (*p)[10]?
• В каком виде можно представить треугольные, ленточные и разреженные матрицы?
• Как записать в выражении обращение к элементу массива a[i][j], с помощью указателя p, если имеем в программе следующие декларации:

int i, j;

float a[N][M]; // N и M - константы

float *p = a; ?