C++实现矩阵原地转置算法

本文实例描述了C++实现矩阵原地转置算法，是一个非常经典的算法，相信对于学习C++算法的朋友有很大的帮助。具体如下：

一、问题描述

微软面试题：将一个MxN的矩阵存储在一个一维数组中，编程实现矩阵的转置。

要求：空间复杂度为O(1)

二、思路分析

下面以一个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的前驱。

三、代码实现如下：

/*************************************************************************
>FileName:matrix_transpose.cpp
>Author:SongLee
************************************************************************/
#include<iostream>
usingnamespacestd;

/*后继*/
intgetNext(inti,intm,intn)
{
return(i%n)*m+i/n;
}

/*前驱*/
intgetPre(inti,intm,intn)
{
return(i%m)*n+i/m;
}

/*处理以下标i为起点的环*/
voidmovedata(int*mtx,inti,intm,intn)
{
inttemp=mtx[i];//暂存
intcur=i;//当前下标
intpre=getPre(cur,m,n);
while(pre!=i)
{
mtx[cur]=mtx[pre];
cur=pre;
pre=getPre(cur,m,n);
}
mtx[cur]=temp;
}

/*转置，即循环处理所有环*/
voidtranspose(int*mtx,intm,intn)
{
for(inti=0;i<m*n;++i)
{
intnext=getNext(i,m,n);
while(next>i)//若存在后继小于i说明重复
next=getNext(next,m,n);
if(next==i)//处理当前环
movedata(mtx,i,m,n);
}
}

/*输出矩阵*/
voidprint(int*mtx,intm,intn)
{
for(inti=0;i<m*n;++i)
{
if((i+1)%n==0)
cout<<mtx[i]<<"\n";
else
cout<<mtx[i]<<"";
}
}

/*测试*/
intmain()
{
intmatrix[4*2]={1,2,3,4,5,6,7,8};
cout<<"Beforematrixtransposition:"<<endl;
print(matrix,4,2);
transpose(matrix,4,2);
cout<<"Aftermatrixtransposition:"<<endl;
print(matrix,2,4);
return0;
}

运行结果如下图所示：