Предположим, что у нас есть матрица размеров m * n, которая хранится в одномерном массиве. Как ее транспонировать?
3 ответа
Транспонировать прямоугольную матрицу, сохранённую в одномерном массиве, без создания дополнительных массивов можно с помощью следующего алгоритма.
Для примера рассмотрим прямоугольную матрицу размера 3 x 5
:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
В транспонированном виде она имеет вид:
1 6 11
2 7 12
3 8 13
4 9 14
5 10 15
Можно заметить, что последний столбец исходной матрицы - это последняя строка транспонированной матрицы, предпоследний столбец исходной матрицы - это предпоследняя строка транспонированной матрицы и т.д.
Таким образом, для транспонирования матрицы можно действовать по следующему алгоритму:
- Если количество столбцов матрицы равно 1, стоп;
- Перемещаем элементы последнего столбца текущей матрицы так, чтобы они следовали непосредственно за элементами всех остальных столбцов текущей матрицы. При этом порядок следования элементов последнего столбца по отношению друг к другу должен быть сохранён. Также, порядок следования элементов в текущей матрице "без последнего столбца" по отношению друг к другу должен быть сохранён.
- Считаем, что количество столбцов в матрице уменьшилось на 1.
- Переходим к п. 1.
Пример кода:
template <typename T>
void MatrixTranspose(T &matr, typename T::size_type r, typename T::size_type c)
{
//r - кол-во строк; c - кол-во столбцов;
if ( r <= 1 || c <= 1 )
return;
typedef typename T::size_type size_type;
typedef typename T::value_type value_type;
size_type ind, ind_last;
value_type buff;
//Позиция в массиве в которую будет перемещён текущий элемент
//текущего последнего столбца матрицы текущего размера.
ind_last = r * c - 2;
while ( c > 1 )
{
//Перебираем элементы последнего столбца в матрице
//текущего размера.
for ( size_type i = r - 2; i != size_type(-1); --i )
{
//Рассчитываем индекс элемента из последнего столбца,
//который собираемся переместить.
ind = i * c + (c - 1);
//Запоминаем элемент последнего столбца в буфере.
buff = matr.at(ind);
//Все элементы матрицы, начиная с позиции элемента,
//следующего за сохранённым в буфере и вплоть до
//элемента находящегося в той позиции, в которую собираемся
//поместить элемент, сохранённый в буфере, смещаем на
//одну позицию влево.
while ( ind < ind_last )
{
matr.at(ind) = matr.at(ind + 1);
++ind;
}
//Сохраняем элемент из буфера в его "правильную" позицию.
matr.at(ind_last) = buff;
--ind_last;
}
--ind_last;
//Уменьшаем кол-во столбцов в матрице, т.е. на следующем шаге
//будем перемещать новый "последний" столбец.
--c;
}
}
-
1Напрашивается использование
std::rotate
вместо очередного выписывания циклического сдвига вручную. Commented 9 дек. 2018 в 11:51 -
В чем глубокий смысл
typename T::size_type
вместо очевидного для количества строк и столбцовsize_t
?– avpCommented 9 дек. 2018 в 20:37
А в чем проблема?
Элемент a[i][j]
- это a[i*n+j]
, так что можно в цикле создавать новую транспонированную матрицу b
:
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
b[j*m+i] = a[i*n+j];
"По-моему, так" (с) Пух
-
Нужно это сделать без создания дополнительного массива, редактируя исходный Commented 3 дек. 2017 в 17:43
-
Для квадратной это просто, а вот для произвольной - что-то сходу не соображу...– HarryCommented 3 дек. 2017 в 18:06
-
фрагмент класса Matrix: ! - перегружен как транспонировать прямоугольную матрицу = перегружен
Matrix& Matrix::operator = ( const Matrix& a)
{
for (int count = 0; count < row; count++)
delete[] * (arr + count);
delete[]arr;
row = a.row;
col = a.col;
arr = new double*[row];
for (int count = 0; count < row; count++)
*(arr + count) = new double[col];
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
arr[i][j] = a.arr[i][j];
return *this;
}
Matrix& Matrix::operator ! ()
{
Matrix tmp(col, row);
for (int i = 0; i < tmp.row; i++)
for (int j = 0; j < tmp.col; j++)
{
tmp.arr[i][j] = arr[j][i];
}
*this = tmp;
return *this;
}
-
1Вопрос читать не пробовали перед тем как отвечать? Commented 9 дек. 2018 в 11:52
-