我正在研究 wiki 文章中描述的方法的实现，用于方阵的就地缓存不经意转置。
https://en.wikipedia.org/wiki/In-place_matrix_transposition
该算法基本上递归地将矩阵分成四个，然后转置沿对角线的象限并交换其上方和下方的象限。实际的转置/交换仅在矩阵大小为 2*2 或更低时发生，否则将再次拆分。
我把它分成三个功能：
这将启动给定大小 N 的过程：
void SmartTranspose(int A[row][col]) {
Transpose(A, 0, 0, N, N);
}
然后：
void Transpose(int A[row][col], int x, int y, int w, int h) {
int Temp;
if ((w - x) * (h - y) <= 4){
for (int row1 = x ; row1 < w -1 ; row1++)
for (int col1 = y + 1 ; col1 < h ; col1++) {
Temp = A[row1][col1];
printf("transp: %d %d\n", A[row1][col1], A[col1] [row1]);
A[row1][col1] = A[col1][row1];
A[col1][row1] = Temp;
}
}
else {
int halfh = h / 2;
int halfw = w / 2;
Transpose(A, x, y, halfw , halfh);
Transpose(A, x + halfw, y + halfh, w , h);
TransposeSwap(A, x + halfw, y, w, halfh, x, y + halfh, halfw , h);
}
}
最后：
void TransposeSwap(int A[row][col], int x, int y, int w, int h,int x1, int y1, int w1, int h1) {
int Temp; int row2 = x1; int col2 = y1;
if ((w - x) * (h - y) <= 4 && (w1 - x1) * (h1 - y1) <= 4) {
for(row1 = x; row1 < w; row1++)
for(col1 = y; col1 < h; col1++)
{
Temp = A[row1][col1] ;
A[row1][col1] = A[col1][row1];
A[col1][row1] = Temp;
}
}
else {
printf("RECURSE");
int halfh = h / 2;
int halfw = w / 2;
int halfh1 = h1 / 2;
int halfw1 = w1 / 2;
TransposeSwap(A, x, y, halfw, halfh, x1, y1, halfw1, halfh1);
TransposeSwap(A, x + halfw, y, w, h - halfh, x1, y1 + halfh1, halfw1, h1);
TransposeSwap(A, x , y + halfh, halfw, h, x1 + halfw1, y1, w1, halfh1);
TransposeSwap(A, x + halfw, y + halfh, w, h, x1 + halfw1, y1 + halfh1, w1, h1);
}
}
但是，这行不通，我正在努力看看我的逻辑在哪里出错了。
编辑：输出示例
Original matrix:
1948037971 40713922 986050715 74181839 943010147 1060710730
18590233 268906808 1966315840 1325423973 398061279 2047858287
513589654 1727398080 2016821685 277200601 1611383116 2000671901
228038281 1863845528 106517081 1934721636 745170263 1736525254
224427632 687572994 1249224754 1497415191 537022734 1443375385
1054092341 337577057 1484089307 2040143056 411758897 279615807
Transposed matrix:
1948037971 18590233 513589654 74181839 943010147 1060710730
40713922 268906808 1727398080 1325423973 398061279 2047858287
986050715 1966315840 2016821685 277200601 1611383116 2000671901
228038281 1863845528 106517081 1934721636 745170263 1736525254
224427632 687572994 1249224754 1497415191 537022734 1443375385
1054092341 337577057 1484089307 2040143056 411758897 279615807
正确的输出应该是转置矩阵。
编辑：主要功能和声明：
int row = 40000 , col = 40000;
static int A[40000][40000];
static int N[100] = {0};
void SmartTranspose(int A[row][col]);
void Transpose(int A[row][col], int x, int y, int w, int h);
void InitializeMatrix(int X[row][col]);
void PrintMatrix(int X[row][col]);
double pow(double x, double y);
int matrix = 0;
void TransposeSwap(int A[row][col], int x, int y, int w, int h,int x1, int y1, int w1, int h1);
int main(){
srand(time(NULL));
double sizes = 0;
int count = 0;
for(sizes = 20; sizes < 30; sizes++)
{
N[count] = floor(pow(2, (sizes/9)));
printf("N %d\n", N[count]);
count++; }
for (matrix = 0; matrix <= count -1 ; matrix++){
InitializeMatrix(A);
printf("N %d\n",N[matrix]);
printf("\nOriginal matrix: \n");
SmartTranspose(A);
printf("E\n");
printf("\nTransposed matrix: \n");
PrintMatrix(A);
}
return 0;
}
完整代码的链接：https ://jpst.it/QaBq