压缩矩阵的转置C语言

压缩矩阵就是将存在数据的坐标及数据保留下来，为0的地方就不记录。所以每个完整存储数据的空间又包括三个小空间（行坐标，列坐标，数据）。由许多个存储行坐标，列坐标，数据的空间便构成了压缩矩阵。在转置过程中先扫描一边压缩矩阵，记录好每个列坐标相等的个数（用于计算转置过后所在起始行数，具体请结合图示理解）。再次扫描开始转置，如图中扫描到的第一个数据中的 j = 0,0对应的起始行数是第一行，交换行坐标，列坐标进行填充，起始行数+1；因为该行已存储了数据。继续扫描到 j = 2,2对应第3行，交换行坐标，列坐标进行填充，起始行数+1。以此类推。具体理解请结合图示与代码

代码

#include 
#include 

typedef int elem;
 
//用于存储矩阵压缩后单个数据 
typedef struct Triple{
	int i;
	int j;
	elem e;
}*TriplePtr; 

//用于存储压缩矩阵的全部数据 
typedef struct CompressedMatrix{
	int rows,columns; 
	int numElements;//矩阵压缩后的数据个数 
	TriplePtr elements;
}*CompressedMatrixPtr;

//压缩矩阵的初始化 
CompressedMatrixPtr initCompressedMatrix(int paraRows,int paraColumns,int paraElements,int**paraData){
	//分配矩阵压缩后所需空间 
	CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(struct CompressedMatrix));
	resultPtr->rows = paraRows;
	resultPtr->columns = paraColumns;
	resultPtr->numElements = paraElements;
	resultPtr->elements = (TriplePtr)malloc(sizeof(struct Triple)*paraElements);
	
	//存储压缩后的数据 
	for(int i = 0;i < paraElements;i++){
		resultPtr->elements[i].i=paraData[i][0];
		resultPtr->elements[i].j=paraData[i][1];
		resultPtr->elements[i].e=paraData[i][2];
	} 
	return resultPtr;
}

void printCompressedMatrix(CompressedMatrixPtr paraPtr){
	int i;
	for(i = 0; i < paraPtr->numElements;i++){
		printf("(%d,%d):%d\n",paraPtr->elements[i].i,paraPtr->elements[i].j,paraPtr->elements[i].e);
	}
}

CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr){
	int i,tempColumn,tempPosition;
	
	//分配新的空间用于存储转置后的矩阵 
	CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(CompressedMatrix));
	resultPtr->rows = paraPtr->columns;
	resultPtr->columns = paraPtr->rows;
	resultPtr->numElements = paraPtr->numElements;
	resultPtr->elements = (TriplePtr)malloc(sizeof(Triple)*paraPtr->numElements);
	
	//得到各个列坐标相等的总个数 
	int *tempColumnCounts = (int*)malloc(sizeof(int)*paraPtr->columns);
	int *tempOffsets = (int*)malloc(sizeof(int)*paraPtr->columns);
	for(i = 0;i < paraPtr->columns;i++){
		tempColumnCounts[i] = 0;//先初始化为0 
	}
	//扫描压缩矩阵 
	for(i = 0;i < paraPtr->numElements;i++){
		tempColumnCounts[paraPtr->elements[i].j]++;//记录每个列坐标相等的个数 
	}
	tempOffsets[0]=0;
	//计算相同大小列坐标转置后所在起始的行数 
	for(i = 1;i < paraPtr->columns;i++){
		tempOffsets[i] =  tempOffsets[i-1]+tempColumnCounts[i-1];
	}
	//转置（再次扫描填充） 
	for(i = 0;i < paraPtr->numElements;i++){
		tempColumn = paraPtr->elements[i].j;
		tempPosition = tempOffsets[tempColumn];
		resultPtr->elements[tempPosition].i = paraPtr->elements[i].j;
		resultPtr->elements[tempPosition].j = paraPtr->elements[i].i;
		resultPtr->elements[tempPosition].e = paraPtr->elements[i].e;

		tempOffsets[tempColumn]++;
	}
	
	return resultPtr;
}

void compressedMatrixTest(){
	CompressedMatrixPtr tempPtr1,tempPtr2;
	
	int i,j,tempElements;
	tempElements = 4;
	
	int**tempMatrix1 = (int**)malloc(sizeof(int*)*tempElements);
	for(i = 0;i < tempElements;i++){
		tempMatrix1[i]  = (int*)malloc(sizeof(int)*3);
	}
	int tempMatrix2[4][3]={{0,0,2},{0,2,3},{2,0,5},{2,1,6}};
	
	for(i = 0;i < tempElements;i++){
		for(j = 0;j < 3;j++){
			tempMatrix1[i][j] = tempMatrix2[i][j];
		}
	}
	
	tempPtr1 = initCompressedMatrix(2,3,4,tempMatrix1);
	printf("转置之前: \n");
	printCompressedMatrix(tempPtr1);
	
	tempPtr2 = transposeCompressedMatrix(tempPtr1);
	printf("转置过后：\n");
	printCompressedMatrix(tempPtr2);
	
}

int main(){
	compressedMatrixTest();
	return 1;
}

 压缩矩阵转置大大节省了时间，但稍难理解，不过用心就一定会攻破的。