Специални видове матрици

Работата с матрици като с двумерни масиви не създава никакви проблеми. В същото време има редица матрици от специален вид, работата с които изисква специален подход. Това са матрици, в които повечето елементи имат еднакви стойности - обикновено равни на нула:

  • триъгълни матрици, чиито нулеви елементи са разположени над главния диагонал,
  • лентови матрици с ширина d>0, всички от чиито елементи aij, за които abs(i-j)>gt; d имат еднакви нулеви стойности,
  • разредени матрици с повечето елементи равни на 0.

За триъгълни и лентови матрици обикновено се използва последователно компресирано представяне. 0-ият елемент не се въвежда в матрицата, а всички останали елементи се подреждат в редица, под формата на вектор.

Пример

Нека е дадена триъгълна матрица от вида:

В паметта на компютъра представянето на матрицата ще бъде както следва:

По този начин се изискват n * (n + 1) / 2 клетки за съхраняване на елементи вместо n 2 . Индексът за достъп до елемента aij се изчислява по формулата:

Не е трудно да се посочи функция за четене на ij-тия елемент от матрицата:

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

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

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

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

Пример

Нека е дадена следната лентова матрица с d=1:

Представянето на матрицата като вектор ще бъде както следва:

Индексът за достъп до елемента aij се изчислява по формулата:

i * (2 * d + 1) + j - i \u003d i * 2 * d + j.

Разредените матрици могат да бъдат представени по различни начини. Нека изброим 2 от тях:

  • последователно компресирано представяне,
  • компресиран последователно свързан индекспроизводителност.

Във втория случай, ако размерът на матрицата е n x n, тогава тя е представена като n-списъци и всеки елемент е представен от тройка:

Въпроси за самоконтрол

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

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