稀疏矩阵转置算法

三元组

一般来说，对于稀疏矩阵，我们使用三元组来存储。也就是将矩阵的所有非零元素用三元组顺序表的形式表示。每个三元组包括的信息有：

i非零元素的行下标，三元组的行标。j非零元素的列下标，三元组的列标。v元素值。
mu矩阵的行数，三元组的最大行标。nu矩阵的列数，三元组的最大列标。tu矩阵非零元素的总个数，三元组的总行数。

三元组顺序表的定义：

# define MAXSIZE 12500 			// 最大的非零元素个数
typedef struct{
    int i,j;					// 分别表示非零元素的行下标和列下标
    ElemType v;					// 元素值
}Triple;
typedef struct{
    Triple data[MAXSIZE + 1]; 	// 所有的非零元素， data[0]未用，data表示三元组
    int mu, nu, tu;				// 矩阵的行数、列数和总共的非零元素个数
}TSMatrix;

转置

转置需要经历以下三个步骤：

1. 将矩阵的行列值相互交换；
2. 将每个三元组中的 i 和 j 相互调换；
3. 重排三元组之间的次序便可实现矩阵的转置。

普通转置

算法思想：

1. 行列数先互换，将M的元素数赋值给T的元素数。
2. 按三元组的方式扫描：每个列标需要扫描所有的三元组，如果原矩阵的三元组列标等于设置递增的列标，则为扫描到一条，将原三元组的列值赋值给转置后三元组的行值，原三元组的行值赋值给转置后三元组的列值，原三元组的元素值赋值给转置后三元组的元素值。

Status TransposeSMatrix(TSMatrix M, TSMatrix &T){
	//采用三元组表存储表示，求稀疏矩阵M的转置矩阵T，算法时间复杂度为O(nu * tu)
	T.mu = M.nu;	T.nu = M.mu;	T.tu = M.tu;
	if(T.tu){
		q = 1;
		for(col=1; col<=M.nu; col++)//n是列数 
			for(p=1; p<=M.tu; p++)
				if(M.data[p].j == col){
					T.data[q].i = M.data[p].j;
					T.data[q].j = M.data[p].i;
					T.data[q].v = M.data[p].v;
					q++;
				}
	}
}

快速转置

算法思想：

要想扫描一次 M 就能得到 T，必须每次扫描到一个三元组就直接将其放到转置三元组中相应的位置上。num 和cpot，分别用于存储矩阵 M 中每一列的非零元素个数和矩阵 M 中每一列第一个非零元素在 T 中的存储位置。有如下公式成立：

cpot[1] = 1
cpot[col] = cpot[col - 1] + num[col - 1], 2 <= col <= M.nu

1. 行列数先互换，将M的元素数赋值给T的元素数。
2. 计算每列非零元的个数：先将num数组初始化为0，然后扫描一遍三元组，将三元组列标对应的num数组作加一处理，这样就能得到M中的每一列含有非零元个数。
3. 求第col列中第一个非零元在转置后三元组中的序号：从第二列开始，每列的copt等于前一列的copt加上前一列的num。第一列的 cpot[1] = 1。
4. 遍历一遍三元组，取出原矩阵三元组的列标和在转置后三元组中的位置，将原三元组的列值赋值给转置后三元组的行值，将原三元组的行值赋值给转置后三元组的列值，将原三元组的元素值赋值给转置后三元组的元素值。每次赋值完以后要将对应列的copt值加1。

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
	//采用三元组表存储表示，求稀疏矩阵M的转置矩阵T，算法时间复杂度为O(nu + tu)
	T.mu = M.nu;	T.nu = M.mu;	T.tu = M.tu;
	if(T.tu){
		for(col=1; col<= M.nu; col++)
			num[col] = 0;
		for(t=1; t<=M.tu; t++)
			num[M.data[t].j]++;	//求M中每一列含非零元个数 
		cpot[1] = 1;
		//求第col列中第一个非零元在b.data中的序号 
		for(col=2; col<=M.nu; col++)
			cpot[col] = cpot[col-1] + num[col-1];
		for(p=1; p<=M.tu; p++){
			col = M.data[p].j; //col是原矩阵三元组的列标
			q = cpot[col]; //q是在转置后三元组第一个非零元的位置
			T.data[q].i = M.data[p].j;
			T.data[q].j = M.data[p].i;
			T.data[q].v = M.data[p].v;
			cpot[col]++;
		}
	}
}