/************************************************************************* 
  > 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; 
} 
 
/* 前驅(qū) */ 
int getPre(int i, int m, int n) 
{ 
  return (i%m)*n + i/m; 
} 
 
/* 處理以下標i為起點的環(huán) */ 
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; 
} 
 
/* 轉(zhuǎn)置，即循環(huán)處理所有環(huán) */ 
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說明重復(fù) 
      next = getNext(next, m, n); 
    if(next == i)  // 處理當前環(huán)  
      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; 
}