C++實現(xiàn)矩陣原地轉(zhuǎn)置算法

更新時間：2014年08月14日 10:34:21 投稿：shichen2014

這篇文章主要介紹了C++實現(xiàn)矩陣原地轉(zhuǎn)置算法,非常經(jīng)典的算法,需要的朋友可以參考下

本文實例描述了C++實現(xiàn)矩陣原地轉(zhuǎn)置算法，是一個非常經(jīng)典的算法，相信對于學(xué)習(xí)C++算法的朋友有很大的幫助。具體如下：

一、問題描述

微軟面試題：將一個MxN的矩陣存儲在一個一維數(shù)組中，編程實現(xiàn)矩陣的轉(zhuǎn)置。

要求：空間復(fù)雜度為O(1)

二、思路分析

下面以一個4x2的矩陣A={1,2,3,4,5,6,7,8}進行分析，轉(zhuǎn)置過程如下圖：

圖中右下角的紅色數(shù)字表示在一維數(shù)組中的下標(biāo)。矩陣的轉(zhuǎn)置其實就是數(shù)組中元素的移動，具體的移動過程如下圖：

我們發(fā)現(xiàn)，這些移動的元素的下標(biāo)是一個個環(huán)，下標(biāo)1的元素移動到4，下標(biāo)4的元素移動到2，下標(biāo)2的元素移動到1。在編寫程序的時候，我們需要解決兩個問題：第一個是如何判定環(huán)是否重復(fù)（已處理過）；第二個是如何計算當(dāng)前元素下標(biāo)的前驅(qū)與后繼。

第一個問題：如何判斷環(huán)是重復(fù)已處理過的？因為我們遍歷整個數(shù)組時下標(biāo)是從小到大的，所以如果是第一次遍歷該環(huán)，則第一個下標(biāo)肯定是這個環(huán)中最小的。如果一個環(huán)被處理過，那么總能找到一個它的后繼是小于它的。從上圖可以明顯看出來。

第二個問題：如何計算當(dāng)前元素下標(biāo)的前驅(qū)與后繼？假設(shè)轉(zhuǎn)置前某個元素的數(shù)組下標(biāo)為i，則它所在行列為（i/N, i%N），轉(zhuǎn)置后所在行列則為（i%N, i/N），可計算轉(zhuǎn)置后數(shù)組下標(biāo)為(i%N)*M+i/N，此為i的后繼。假設(shè)轉(zhuǎn)置后某個元素的數(shù)組下標(biāo)為i，則它所在行列為（i/M, i%M），則轉(zhuǎn)置前所在行列為（i%M, i/M），可計算此時下標(biāo)為(i%M)*N+i/M，此為i的前驅(qū)。

三、代碼實現(xiàn)如下：

/************************************************************************* 
  > 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; 
} 
 
/* 處理以下標(biāo)i為起點的環(huán) */ 
void movedata(int *mtx, int i, int m, int n) 
{ 
  int temp = mtx[i]; // 暫存 
  int cur = i;    // 當(dāng)前下標(biāo) 
  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)  // 處理當(dāng)前環(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; 
}

運行結(jié)果如下圖所示：