矩阵转置 O（1）

矩阵转置
链接为：https://www.acwing.com/problem/content/3595/

使用了辅助空间的：

#include <iostream>
using namespace std;
const int N=110;

int a[N][N];
int b[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>a[i][j];
    
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    b[j][i]=a[i][j];
    
     for(int i=1;i<=n;i++)
     {
    for(int j=1;j<=n;j++)
    cout<<b[i][j]<<" ";   
    cout<<endl;
     }
   
    return 0;
    
    
    
}

如果要使用没有辅助空间的，就在原地进行转置的代码如下：
（采用交换的方式，就是按“\”主对角线进行一个反转即可）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;

int a[N][N];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			swap(a[j][i], a[i][j]);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}
	return 0;
}

还有一个实现，觉得很不错：
附上地址：http://www.jb51.net/article/53715.htm

/************************************************************************* 
  > File Name: matrix_transpose.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
/* 后继 */ 
int getNext(int i, int m, int n) 
{ 
  return (i%n)*m + i/n; 
} 
 
/* 前驱 */ 
int getPre(int i, int m, int n) 
{ 
  return (i%m)*n + i/m; 
} 
 
/* 处理以下标i为起点的环 */ 
void movedata(int *mtx, int i, int m, int n) 
{ 
  int temp = mtx[i]; // 暂存 
  int cur = i;    // 当前下标 
  int pre = getPre(cur, m, n); 
  while(pre != i) 
  { 
    mtx[cur] = mtx[pre]; 
    cur = pre; 
    pre = getPre(cur, m, n); 
  } 
  mtx[cur] = temp; 
} 
 
/* 转置，即循环处理所有环 */ 
void transpose(int *mtx, int m, int n) 
{ 
  for(int i=0; i<m*n; ++i) 
  { 
    int next = getNext(i, m, n); 
    while(next > i) // 若存在后继小于i说明重复 
      next = getNext(next, m, n); 
    if(next == i)  // 处理当前环  
      movedata(mtx, i, m, n); 
  } 
} 
 
/* 输出矩阵 */ 
void print(int *mtx, int m, int n) 
{ 
  for(int i=0; i<m*n; ++i) 
  { 
    if((i+1)%n == 0) 
      cout << mtx[i] << "\n"; 
    else 
      cout << mtx[i] << " "; 
  } 
} 
 
/* 测试 */ 
int main() 
{ 
  int matrix[4*2] = {1,2,3,4,5,6,7,8}; 
  cout << "Before matrix transposition:" << endl; 
  print(matrix, 4, 2); 
  transpose(matrix, 4, 2); 
  cout << "After matrix transposition:" << endl; 
  print(matrix, 2, 4); 
  return 0; 
}