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

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

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

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

一、問(wèn)題描述

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

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

二、思路分析

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

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

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

第一個(gè)問(wèn)題：如何判斷環(huán)是重復(fù)已處理過(guò)的？因?yàn)槲覀儽闅v整個(gè)數(shù)組時(shí)下標(biāo)是從小到大的，所以如果是第一次遍歷該環(huán)，則第一個(gè)下標(biāo)肯定是這個(gè)環(huán)中最小的。如果一個(gè)環(huán)被處理過(guò)，那么總能找到一個(gè)它的后繼是小于它的。從上圖可以明顯看出來(lái)。

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

三、代碼實(shí)現(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為起點(diǎn)的環(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說(shuō)明重復(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] << " "; 
  } 
} 
 
/* 測(cè)試 */ 
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; 
}

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