/************************************************************************* 
  > 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; 
}