【压缩矩阵的转置】

1.稀疏矩阵的压缩存储，至少需要存储以下信息：
矩阵中各非 0 元素的值，以及所在矩阵中的行标和列标；
矩阵的总行数和总列数；

例如，将图 2a) 三元组表存储的矩阵进行转置的过程为：
1.新建一个三元组表（用于存储转置矩阵），并将原矩阵的行数和列数互换赋值给新三元组；
2.遍历三元组表，找到表中 j 列最小值 1 所在的三元组 (3,1,6)，然后将其行标和列标互换后添加到一个新的三元组表中，如图 3 所示：

#include<stdio.h>
#include<malloc.h>
typedef int elem;
//定义三元组的结构
typedef struct Triple {
    int i;
    int j;
    elem e;
}Triple,*TriplePtr;
//定义压缩矩阵
typedef struct CompressedMatrix {
    int rows,columns,numElements;
    Triple* elements;
}CompressedMatrix,*CompressedMatrixPtr;
// 矩阵的初始化
CompressedMatrixPtr initCompressedMatrix(int paraRows, int paraColumns,int paraElements, int** paraData){
    int i;
    CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(CompressedMatrixPtr));
    resultPtr->rows = paraRows; //矩阵的行
    resultPtr->columns = paraColumns; //矩阵的列
    resultPtr->numElements = paraElements; //记录矩阵里的非0数据
    resultPtr->elements = (TriplePtr)malloc(paraElements*sizeof(TriplePtr));

    for(i = 0;i< paraElements;i++){//记录矩阵里所有非0数据的x，y和值
        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\r\n",paraPtr->elements[i].i,paraPtr->elements[i],j,paraPtr->elements[i].e);
    }

}
// 压缩矩阵的转置
CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr){

    int i,tempColumn,tempPosition;
    int *tempColumnCounts = (int*)malloc(paraPtr->columns*sizeof(int));
    int *tempOffsets = (int*)malloc(paraPtr->columns*sizeof(int));
    for(i = 0;i<paraPtr->columns;i++){
        tempColumnCounts[i] = 0;
    }
    CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(CompressedMatrixPtr));
    resultPtr->rows = paraPtr->columns;
    resultPtr->columns = paraPtr->rows;
    resultPtr->numElements = paraPtr->numElements;

    resultPtr->elements = (TriplePtr)malloc(sizeof(TriplePtr));

    for(i = 0;i<paraPtr->numElements;i++){
        tempColumnCounts[paraPtr->elements[i].j]++;
    }
    tempOffsets[0] = 0;
    for(i = 0;i<paraPtr->columns;i++){
        tempOffsets[i] = tempOffsets[i-1]+tempColumnCounts[i-1];
        printf("tempOffsets[%d] = %d\r\n",i,tempOffsets[i]);
    }
	//矩阵转置
    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 = 6;
    int** tempMatrix1 = (int**)malloc(tempElements*sizeof(int*));
    for(i = 0; i < tempElements; i ++){
		tempMatrix1[i] = (int*)malloc(3 * sizeof(int));
	}
 
	int tempMatrix2[6][3] = {{0, 1, 2}, {1, 0, 3}, {1, 2, 5}, {2, 0, 1}, {3, 0, 7}, {3, 2, 1}};
	for(i = 0; i < tempElements; i ++){
		for(j = 0; j < 3; j ++) {
			tempMatrix1[i][j] = tempMatrix2[i][j];
		}
	}
	
	tempPtr1 = initCompressedMatrix(4, 3, 6, tempMatrix1);
 
	printf("After initialization.\r\n");
	printCompressedMatrix(tempPtr1);
 
	tempPtr2 = transposeCompressedMatrix(tempPtr1);
	printf("After transpose.\r\n");
	printCompressedMatrix(tempPtr2);
}
 
 
int main(){
	compressedMatrixTest();
 
	return 1;

}

主要还是要理解上面所讲的压缩矩阵转置的过程，理解之后才能在写代码的时候思路更清晰