Транспонирование прямоугольной матрицы

#cpp #матрицы

Предположим, что у нас есть матрица размеров m * n, которая хранится в одномерном
массиве. Как ее транспонировать?
    

Ответы

Ответ 1

Транспонировать прямоугольную матрицу, сохранённую в одномерном массиве, без создания
дополнительных массивов можно с помощью следующего алгоритма.

Для примера рассмотрим прямоугольную матрицу размера 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 
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;
    }
}


Ответ 2

А в чем проблема?

Элемент 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];


"По-моему, так" (с) Пух


Ответ 3

фрагмент класса 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;
}