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

Перестановка двух строк, номера 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–й семестр).

Упражнения.

1. Переставить строки, в которых находится наибольший и наименьший элементы матрицы.

Указание. На первом этапе необходимо найти номера строк (n1 и n2), в которых находятся эти элементы. И если n1 != n2, то переставляем эти строки так, как показано выше.

2. Из матрицы удалить все нулевые строки, т. е. строки, состоящие из одних нулей.

Указание. Приведенный выше алгоритм удаления необходимо повторить в цикле по номеру строки k. Если k–я строка содержит только нули, то удаляем её так, как показано выше.