稀疏矩陣轉置中的快速轉置

稀疏矩陣轉置中的快速轉置就是記錄目标矩陣每一行的開始位置，在對原始矩陣的每個元素進行轉置時，隻需根據元素的所在列和目标矩陣對應行的開始位置，就可确定目标元素的位置，進而進行原始元素和目标元素相應值得交換，具體c語言代碼如下：

#include<iostream>

#define MAXSIZE 12500

typedef struct {
	int i, j;
	int e;
}Triple;//三維元素
typedef struct{
	Triple data[MAXSIZE + 1];
	int mu, nu, tu;  //行、列、總數
}TSMatrix;//稀疏矩陣

//快速轉置
int FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
   //求稀疏矩陣M的轉置矩陣T
	T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
    //初始化M各列非零元素數目num，T矩陣各行開始位置cpot
	int num[10] = { 0 }, cpot[10] = { 0 };  
	if (T.tu){
		for (int col = 1; col <= M.mu; col++) num[col] = 0;
		for (int t = 1; t <= M.nu; t++) ++num[M.data[t].j];  //求M各列非零元素數目num
		cpot[1] = 1;  //T矩陣第一行開始位置為1
		//T矩陣各行開始位置等于上行開始位置加上上行非零元素數目；T矩陣的col行非零元素數目等于M矩 //陣col列非零元素數目
		for (int col = 2; col <= T.nu; col++) cpot[col] = cpot[col - 1] + num[col - 1];  
		for (int p = 1; p < M.tu; p++){
			int col = M.data[p].j;  //将M矩陣元素的列轉換為T矩陣的行
			int q = cpot[col];      //定位T矩陣第col行未指派元素的開始位置
			T.data[q].i = M.data[p].j;
			T.data[q].j = M.data[p].i;
			T.data[q].e = M.data[p].e;
			cpot[col]++;   //T矩陣第col行未指派元素的開始位置前移
		}//for
	}//if
	return 1;
}