Построение матриц

Преобразование матрицы

Выделим некоторые подтипы таких задач.

Перестановка двух строк, номера n1 и n2 которых заданы, выполняется следующим образом. Составим функцию для перестановки двух целых чисел:

void RR(int &x, int &y)

{ int t; t=x; x=y; y=t;}

В другой функции или в main выполняем поэлементную перестановку каждой пары элементов:

for (int j=0; j<m; j++)

RR(A[n1][ j], A[n2][j]);

В качестве упражнения с помощью той же функции выполните перестановку m1 – го и m2 – го столбцов, если m1 и m2 заданы.

Удаление k – й строки, где k известно, выполняется так:

for (int i=k; i<n-1; i++)

for (int j=0; j<m; j++)

A[i][j]=A[i+1][j];

Здесь на место k –й строки помещаем каждый элемент (k+1) –й строки, на место (k+1) –й — (к+2) –ю строку и так далее. Наконец, на место (n-2)–й копируем (n-1)–ю строку. Таким образом, все строки, начиная с (к+1)–й, “поднимаем на одну вверх”. При этом объём зарезервированной памяти для матрицы не изменяется. По-прежнему в памяти находится n строк, то есть физически ни одну строку из памяти мы не удаляли. Но после удаления одной строки количество обрабатываемых строк на одну уменьшается. Последняя строка в обработке уже не должна участвовать.

Для вставки одной строки после к -й на первом этапе необходимо все строки с (n-1)–й до (к+1) в обратном порядке “опустить вниз”:

for (int i=n-2; i>=k+1; i - -)

for (int j=0; j<m; j++)

A[i+1][j]=A[i][j];

Затем на место освободившейся (k+1)–й строки надо поместить вставляемую строку, например, одномерный массив B такой же размерности m, что и строка матрицы:

for (int j=0; j<m; j++)

A[k+1][j]=B[j];

При объявлении матрицы необходимо учесть, что после вставки количество строк увеличится. Поэтому если по условию вставляется одна строка, то объявляем так: int A[n+1][m]. Если после каждой строки с некоторым условием (например, в строке больше половины нулей) надо вставить новую строку, то матрицу надо объявить так: int A[2*n][m]. В этом случае резервируется максимальный объём памяти в предположении, что после каждой строки надо вставлять новую. Реально такой вариант будет маловероятным и память будет использоваться неэффективно.

Похожая проблема с памятью имеет место и при удалении строк. Более того, если перестановку, удаление или вставку строк надо выполнять несколько раз, то для больших матриц может возникнуть проблема и с временем выполнения программы. Поэтому

на практике такое преобразование эффективнее выполнять с помощью динамических матриц или списков (2–й семестр).

Выделим некоторые подтипы таких задач.

Элементы новой матрицы зависят от своих же индексов.

Элементы матрицы используют одно число.

Построение матрицы на одном или нескольких одномерных или двухмерных массивах.