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 that you have read and understand our privacy policy and code of conduct.

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