原址转置算法使用环境：指针type* 指向的一维数据，指定矩阵宽度W，高度H。转置前的数据高度H，宽度W，转置之后的数据高度为W宽度为H。
以int* a=[1,2,3,4,5,6,7,8,9,10,11,12]为例，3行4列排放为
[ 1 2 3 4] [ 5 6 7 8] [ 9 10 11 12]
转置之后的数据为： [ 1 5 9] [ 2 6 10] [ 3 7 11] [ 4 8 12] 转置后的*a=[1,5,9,2,6,10,3,7,11,4,8,12]
序号 1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 5 9 2 6 10 3 7 11 4 8 12
元素2的位置上被5占据了，5原来的位置被6占据了，6的位置被10占据了，10的位置被4占据了，4的位置被2占据了，也就是形成了2->5->6->10->4->2的环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <vector>
using namespace std;
void trans_inplace(int *a, int h, int w){
vector<int> tt;
int num = 0;
for (int i = 1; i != h*w - 1; ++i){
tt.clear();
tt.push_back(i);
bool flag = true;//用来判断是不是重复转置
int k = ( i % w ) * h + i / w;
while (k != i){
if (k<i){
flag = false;
break;
}
tt.push_back(k);
k = (k%w)*h + k / w;
}
if (flag){
int temp = a[tt[tt.size()-1]];
for (int j = tt.size() - 1; j > 0; --j){
a[tt[j]] = a[tt[j - 1]];
}
a[i] = temp;
num += tt.size();
if (num == h*w - 2)//首尾不需要转置
break;
}
}
}
void print_matrix(int *a, int n, int m){
for (int i = 0; i != n; ++i){
cout<<"[ ";
for (int j = 0; j != m; ++j){
cout << a[j + i*m]<<" ";
}
cout << "]" << endl;
}
}
int main()
{
int a[12] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
print_matrix(a, 3, 4);//转置前
trans_inplace(a, 3, 4);
print_matrix(a, 4, 3);//转置后
getchar();
return 0;
}
|
近期评论