П3.6. Транспонирование матрицы, содержащей n строк и n столбцов

Матрицапредставляет собой двумерный массив данных, в котором доступ к любому из элементов осуществляется по двум индексам — номеру столбца i и номеру строки j. Адрес элемента матрицы будем обозначать a _ji при отображении по строкам и – при отображении по столбцам. В памяти элементы матрицы хранятся в виде одномерного массива данных с линейной организацией. Матрица может размещаться в произвольной области памяти. Для определенности будем считать, что она размещается в младших адресах 256-байтной страницы, т. е. адрес ее первого элемента в странице равен нулю. Для получения адреса произвольного элемента матрицы его необходимо преобразовать в линейный адрес. При принятых ограничениях линейный адрес элемента строки определяется по формуле a _ji = i + n * j, а адрес элемента столбца — по формуле a _ij = j + n * i, где n — число элементов в строке (столбце), 0 ≤ i, j ≤ n.

Общим методом решения задачи транспонирования является перестановка элементов строк a _ji и столбцов a _ij, в результате которой строки и столбцы меняются местами.

Для практической реализации перестановок необходимо вычислить линейные адреса переставляемых элементов строк и столбцов и осуществить обмен содержимым ячеек памяти по вычисленным адресам. После обмена элементов первой строки и первого столбца исходной матрицы n -го порядка виртуально легко выделяется матрица (n – 1)-го порядка, в которой элементы первой строки аналогично заменяются элементами первого столбца. В результате выделяется матрица (n – 2)-го порядка. Преобразование выполняется до выделения матрицы 0-го порядка.

Описанный алгоритм реализуется в виде двух вложенных циклов: в первом цикле осуществляются перестановки элементов строки и столбца (инкремент i). Этот цикл является вложенным. Во втором (внешнем) цикле выполняется определение порядка преобразуемой матрицы (инкремент j).