c++ - 理解旋转 N x N 矩阵的逻辑

Question

您好，我已经开始解决 C++ 问题了。其中之一是将 N x N 矩阵顺时针旋转 90 度。

下面是代码链接，我指的是。我从来没有解决过 C++ 中的矩阵问题。

http://www.geeksforgeeks.org/turn-an-image-by-90-degree/

#include <stdio.h>
#include <stdlib.h>
 
void displayMatrix(unsigned int const *p, unsigned int row, unsigned int col);
void rotate(unsigned int *pS, unsigned int *pD, unsigned int row, unsigned int col);
 
int main()
{
    // declarations
    unsigned int image[][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};
    unsigned int *pSource;
    unsigned int *pDestination;
    unsigned int m, n;
 
    // setting initial values and memory allocation
    m = 3, n = 4, pSource = (unsigned int *)image;
    pDestination = (unsigned int *)malloc(sizeof(int)*m*n);
 
    // process each buffer
    displayMatrix(pSource, m, n);
 
    rotate(pSource, pDestination, m, n);
 
    displayMatrix(pDestination, n, m);
 
    free(pDestination);
 
    getchar();
    return 0;
}
 
void displayMatrix(unsigned int const *p, unsigned int r, unsigned int c)
{
    unsigned int row, col;
    printf("\n\n");
 
    for(row = 0; row < r; row++)
    {
        for(col = 0; col < c; col++)
        {
            printf("%d\t", *(p + row * c + col)); // what is this??? couldnt understand this logic?
        }
        printf("\n");
    }
 
    printf("\n\n");
}
 
void rotate(unsigned int *pS, unsigned int *pD, unsigned int row, unsigned int col)
{
    unsigned int r, c;
    for(r = 0; r < row; r++)
    {
        for(c = 0; c < col; c++)
        {
            *(pD + c * row + (row - r - 1)) = *(pS + r * col + c); // not understanding this logic as well.
        }
    }
}

谁能解释一下这个逻辑。我无法解决我在代码本身中提到的上述问题中的几个地方。

另外请让我知道详细的时间和空间复杂度。提前致谢。

Answer 1

代码依赖于连续存储的二维数组并将其视为一维数组。

线

*(pD + c * row + (row - r - 1)) = *(pS + r * col + c);

相当于

pD[c][row-r-1] = pS[r][c];