Выполнить операцию транспонирования прямоугольной матрицы A - C (СИ)

Формулировка задачи:

Выполнить операцию транспонирования прямоугольной матрицы A(m,n),m<>n , не выделяя дополнительного массива для хранения результата. Матрицу представить в виде одномерного массива.

Решение задачи: «Выполнить операцию транспонирования прямоугольной матрицы A»

Листинг программы

#include <stdio.h>
 
void int_swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
void int_rotate(int* first, int* n_first, int* last)
{
    if (first == n_first) return;
    if (n_first == last) return;
 
    int* next = n_first;
    do {
        int_swap(first++, next++);
        if (first == n_first) n_first = next;
    } while (next != last);
 
    for (next = n_first; next != last; ) {
        int_swap(first++, next++);
        if (first == n_first) n_first = next;
        else if (next == last) next = n_first;
    }
}
 
void int_transpose(int* mat, int N, int M)
{
    int dst = 1;
    int src = M;
    int old_src = src;
    int src_inc = M;
 
    while (src < N*M && dst < src) {
        int_rotate(mat + dst, mat + src, mat + src + 1);
 
        if ((dst+1) % N != 0) {
            dst += 1;
            src += src_inc;
        } else {
            dst += 2;
            src = old_src;
            src_inc -= 1;
            src += N - 1;
            old_src = src;
        }
    }
}
 
#define N 5
#define M 3
 
int main(void)
{
    int mat[N][M];
    for (int n = 0; n < N; n++)
        for (int m = 0; m < M; m++)
            mat[n][m] = n*M + m;
 
    for (int n = 0; n < N; n++) {
        for (int m = 0; m < M; m++)
            printf("%x ", mat[n][m]);
        putchar('\n');
    }
    putchar('\n');
 
    int_transpose(&mat[0][0], N, M);
 
    for (int n = 0; n < M; n++) {
        for (int m = 0; m < N; m++)
            printf("%x ", *(&mat[0][0] + n*N + m));
        putchar('\n');
    }
    putchar('\n');
}

Объяснение кода листинга программы

В данном коде реализована функция для транспонирования прямоугольной матрицы. Список действий, которые выполняются в коде:

Сначала определены три функции:
- int_swap для обмена значениями двух указателей;
- int_rotate для поворота элементов матрицы относительно указателя;
- int_transpose для транспонирования матрицы.
В функции int_transpose создаются временные указатели dst и src, которые используются для перемещения по матрице. Изначально dst указывает на элемент, который должен стать первым элементом результирующей матрицы, а src указывает на последний элемент исходной матрицы.
В цикле while происходит поворот элементов матрицы до тех пор, пока не будет достигнут один из углов.
- Если dst становится больше N, то это означает, что строка полностью перевернута, поэтому dst и src сдвигаются на 1 вправо и вверх соответственно.
- Если dst становится четным числом (не считая 0), то это означает, что столбец полностью перевернут, поэтому dst и src сдвигаются на 2 вправо и вверх соответственно, а src_inc уменьшается на 1.
- Если src становится меньше N*M, то это означает, что матрица перевернута.
В основной функции main создается матрица mat размером N*M, заполняется случайными значениями и выводится на экран.
Затем вызывается функция int_transpose для транспонирования матрицы.
После этого выводятся на экран элементы транспонированной матрицы.