3

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

3 ответа 3

4

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

Для примера рассмотрим прямоугольную матрицу размера 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, стоп;
  2. Перемещаем элементы последнего столбца текущей матрицы так, чтобы они следовали непосредственно за элементами всех остальных столбцов текущей матрицы. При этом порядок следования элементов последнего столбца по отношению друг к другу должен быть сохранён. Также, порядок следования элементов в текущей матрице "без последнего столбца" по отношению друг к другу должен быть сохранён.
  3. Считаем, что количество столбцов в матрице уменьшилось на 1.
  4. Переходим к п. 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;
    }
}
2
  • 1
    Напрашивается использование std::rotate вместо очередного выписывания циклического сдвига вручную. 9 дек 2018 в 11:51
  • В чем глубокий смысл typename T::size_type вместо очевидного для количества строк и столбцов size_t?
    – avp
    9 дек 2018 в 20:37
1

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

Элемент 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
  • Нужно это сделать без создания дополнительного массива, редактируя исходный 3 дек 2017 в 17:43
  • Для квадратной это просто, а вот для произвольной - что-то сходу не соображу...
    – Harry
    3 дек 2017 в 18:06
  • Для квадратной – да, довольно тривиально 3 дек 2017 в 18:07
-1

фрагмент класса 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;
}
2
  • 1
    Вопрос читать не пробовали перед тем как отвечать? 9 дек 2018 в 11:52
  • Извините, отсутствие знаков пунктуации не даёт понять смысл вашего ответа однозначно. Пожалуйста, поправте.
    – 0xdb
    9 дек 2018 в 12:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.