C++完成矩陣原地轉置算法。本站提示廣大學習愛好者：（C++完成矩陣原地轉置算法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++完成矩陣原地轉置算法正文
本文實例描寫了C++完成矩陣原地轉置算法，是一個異常經典的算法，信任關於進修C++算法的同伙有很年夜的贊助。詳細以下：
1、成績描寫
微軟面試題：將一個MxN的矩陣存儲在一個一維數組中，編程完成矩陣的轉置。
請求：空間龐雜度為O(1)
2、思緒剖析
上面以一個4x2的矩陣A={1,2,3,4,5,6,7,8}停止剖析，轉置進程以下圖：
圖中右下角的白色數字表現在一維數組中的下標。矩陣的轉置其實就是數組中元素的挪動，詳細的挪動進程以下圖：
我們發明，這些挪動的元素的下標是一個個環，下標1的元素挪動到4，下標4的元素挪動到2，下標2的元素挪動到1。在編寫法式的時刻，我們須要處理兩個成績：第一個是若何剖斷環能否反復（已處置過）；第二個是若何盤算以後元素下標的先驅與後繼。
第一個成績：若何斷定環是反復已處置過的？由於我們遍歷全部數組時下標是從小到年夜的，所以假如是第一次遍歷該環，則第一個下標確定是這個環中最小的。假如一個環被處置過，那末總能找到一個它的後繼是小於它的。從上圖可以顯著看出來。
第二個成績：若何盤算以後元素下標的先驅與後繼？假定轉置前某個元素的數組下標為i，則它地點行列為（i/N, i%N），轉置後地點行列則為（i%N, i/N），可盤算轉置後數組下標為(i%N)*M+i/N，此為i的後繼。假定轉置後某個元素的數組下標為i，則它地點行列為（i/M, i%M），則轉置前地點行列為（i%M, i/M），可盤算此時下標為(i%M)*N+i/M，此為i的先驅。
3、代碼完成以下：
/*************************************************************************
> 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;
}
運轉成果以下圖所示：
