原址转置算法

发表于 | 分类于

原址转置算法使用环境：指针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;
}