ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Специальные виды матрицРабота с матрицами как с двумерными массивами не представляет никаких проблем. Вместе с тем, имеется целый ряд матриц особого рода, работа с которыми требует особого подхода. Это матрицы, в которых большинство элементов имеют одинаковые значения, - обычно равные нулю: · треугольные матрицы, у которых 0-е элементы расположены над главной диагональю, · ленточные матрицы ширины d >0, у которых все элементы aij, для которых abs(i-j) > d имеют одинаковые 0-е значения, · зазреженные матрицы, у которых большинство элементов равны 0. Для треугольных и ленточных матриц обычно используется последовательное сжатое представление. 0-й элемент не заносится в матрицу, а все остальные элементы располагаются подряд, в виде вектора. Пример Пусть задана треугольная матрица вида: В памяти ЭВМ представление матрицы будет следующим:
Т.о., для хранения элементов требуется n * (n + 1) / 2 ячеек вместо n2. Индекс для доступа к aij–у элементу рассчитывается по формуле: (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:
Представление матрицы в виде вектора будет следующим:
Индекс для доступа к aij–у элементу рассчитывается по формуле: i * (2*d +1) + j – i = i * 2 * d + j.
Разреженные матрицы могут быть представлены различными способами. Укажем 2 из них: · последовательное сжатое представление, · последовательное-связанное индексное сжатое представление.
В первом случае элементы матрицы за исключением 0-х размещают в линейном списке. Каждый элемент представлен тройками вида <i, j, aij>. Поиск ij-го элемента выполняется на основе последовательного просмотра всех элементов списка и сравнения первых двух элементов на соответствие заданным индексам. Во втором случае, если размерность матрицы n x n, то ее представляют в виде n-списков и каждый элемент представлен тройкой: <индекс столбца, значение элемента, ссылка на следующий элемент той же строки>.
Вопросы для самоконтроля
int i, j; float a[N][M]; // N и M - константы float *p = a;?
Не нашли, что искали? Воспользуйтесь поиском:
|