稀疏矩阵的压缩存储，至少需要存储以下信息：

图 1 稀疏矩阵示意图

例如，图 1 是一个稀疏矩阵，若对其进行压缩存储，矩阵中各非 0 元素的存储状态如图 2 所示：

图 2 稀疏矩阵的压缩存储示意图

图 2 的数组中，存储的是三元组（即由 3 部分数据组成的集合），组中数据分别表示（行标，列标，元素值）。

注意，这里矩阵的行标和列标都从 1 开始。

矩阵转置算法：

矩阵转置的实现过程需完成以下 3 步：

矩阵转置的实现思路是：不断遍历存储矩阵的三元组表，每次都取出表中 j 列最小的那一个三元组数据，互换行标和列标的值，并按次序存储到一个新三元组表中。

例如，将图 2a) 三元组表存储的矩阵进行转置的过程为：

新建一个三元组表（用于存储转置矩阵），并将原矩阵的行数和列数互换赋值给新三元组；

遍历三元组表，找到表中 j 列最小值 1 所在的三元组 (3,1,6)，然后将其行标和列标互换后添加到一个新的三元组表中，如图 3 所示：

                                                      图 3 矩阵转置的第一个过程  

继续遍历三元组表，找到表中 j 列次小值为 2 的三元组，分别为 (1,2,1)、(2,2,3) 和 (3,2,5)，根据找到它们的先后次序将各自的行标和列标互换后添加到新三元组表中，如图 4 所示：

                                                       图 4 矩阵转置的第二个过程

快速转置算法：

我们知道，稀疏矩阵的转置需要经历以下 3 步：

稀疏矩阵快速转置算法和普通算法的区别仅在于第 3 步，快速转置能够做到遍历一次三元组表即可完成第 3 步的工作。

                                                              图 1 稀疏矩阵和对应的三元组表

如图 1 所示，此为转置之前的矩阵和对应的三元组表。稀疏矩阵的快速转置是这样的，在普通算法的基础上增设两个数组（假设分别为 array 和 copt）：

                                                       图 2 每一列非 0 元素的个数

                                                         图 3 copt 数组示意图

图 3 中的 copt 数组表示，原稀疏矩阵中第 2 列首个非 0 元素存放到新三元组表的位置为 2。

注意，cpot[col] = cpot[col-1] + array[col-1] 的意思是，后一列首个非 0 元素存放的位置等于前一列首个非 0 元素的存放位置加上该列非 0 元素的个数。由此可以看出，copt 数组才是最终想要的，而 array 数组的设立只是为了帮助我们得到 copt 数组。

这样在实现第 3 步时，根据每个三元组中 j 的数值，可以借助 cpot 数组直接得到此三元组新的存放位置。

代码实现：

C 语言中，三元组需要用结构体实现，如下所示：

//三元组结构体

#define ElemType int

typedef struct {

    int i,j;//行标i，列标j

       ElemType e;//元素值

}Triple;

由于稀疏矩阵中非 0 元素有多个，因此需要建立 triple 数组存储各个元素的三元组。除此之外，考虑到还要存储矩阵的总行数和总列数，因此可以采用以下结构表示整个稀疏矩阵：

#define MAXSIZE 100

//矩阵的结构表示

typedef struct {

      Triple data[MAXSIZE];   //存储该矩阵中所有非0元素的三元组

        int mu;   //矩阵的行数         int nu;   //矩阵的列数         int tu;   //记录矩阵中所有的非0元素的个数

}SMatrix;

可以看到，TSMatrix 是一个结构体，其包含一个三元组数组，以及用于存储矩阵总行数、总列数和非 0 元素个数的变量。 假设采用 TSMatrix 结构体存储图 1 中的稀疏矩阵，其 C 语言实现代码应该为：

SparseMatrix.h

#define ElemType int #define MAXSIZE 100

//三元组结构体定义

typedef struct Triple {     int i;     int j;     ElemType e; }Triple;

//稀疏矩阵结构体定义

typedef struct SMatrix {     Triple data[MAXSIZE];      int mu;     int nu;     int tu; }SMatrix;

/// void CreateMatrix(SMatrix *M); void PrintMatrix(SMatrix *M); void CopyMatrix(SMatrix *M, SMatrix *T); void AddMatrix(SMatrix *M, SMatrix *N, SMatrix *T); //M N void SubMatrix(SMatrix *M, SMatrix *N, SMatrix *T); void MulMatrix(SMatrix *M, SMatrix *N, SMatrix *T); //M (m,n) N(x,y) void TransposeMatrix(SMatrix *M, SMatrix *T); void FastTransposeMatrix(SMatrix *M, SMatrix *T);

 SparseMatrix.c

#include"SparseMatrix.h"

void CreateMatrix(SMatrix *M) {     FILE *fp = fopen("Matrix.txt","r");     if(fp == NULL)         exit(1);

    fscanf(fp,"%d %d",&M->mu, &M->nu);

    int value;     int k = 0;     for(int i=0; imu; ++i)     {         for(int j=0; jnu; ++j)         {             fscanf(fp,"%d",&value);             if(value != 0)             {                 M->data[k].e = value;                 M->data[k].i = i;                 M->data[k].j = j;                 k++;             }         }     }     M->tu = k; //矩阵非零元素个数     fclose(fp); }

void PrintMatrix(SMatrix *M) {     printf("row=%d, col=%d\n",M->mu,M->nu);     for(int i=0; itu; ++i)     {         printf("(%d, %d, %d)\n",M->data[i].i,M->data[i].j,M->data[i].e);     } }

//矩阵拷贝 void CopyMatrix(SMatrix *M, SMatrix *T) {     T->mu = M->mu;     T->nu = M->nu;     T->tu = M->tu;

    for(int i=0; itu; i++)     {         T->data[i].i = M->data[i].i;         T->data[i].j = M->data[i].j;         T->data[i].e = M->data[i].e;     } }

//矩阵转置 //不断遍历存储矩阵的三元组表，每次都取出表中 j 列最小的那一个三元组，互换行标和列标的值，并按次序存储到一个新三元组表中。 void TransposeMatrix(SMatrix *M, SMatrix *T) {     T->mu = M->nu;     T->nu = M->mu;     T->tu = M->tu;

    int q = 0;     if(M->tu != 0)     {         //转置后行列互换，为了保证三元组中顺序还是按照行序为主序存放的，         //按照三元组中的列下标M->data[p].j从小打到大的顺序重新重排三元组的次序         for(int col=0; colnu; ++col)         {             for(int p=0; ptu; ++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].e = M->data[p].e;                     q++;                 }             }         }     } }

//快速矩阵重置算法 void FastTransposeMatrix(SMatrix *M, SMatrix *T) {     T->mu = M->nu; //矩阵T的行数     T->nu = M->mu; //矩阵T的列数     T->tu = M->tu; //矩阵T的飞零元个数

    int *num = (int *)malloc(sizeof(int) * M->nu);     assert(num != NULL);     int *cpot = (int*)malloc(sizeof(int) * M->nu);     assert(cpot != NULL);

    if(T->tu != 0)     {         for(int col=0; colnu; ++col)         {             num[col] = 0;         }         for(int t=0; ttu; ++t)         {             num[M->data[t].j]++;         }         //cpot数组用于计算稀疏矩阵每列第一个非0元素在新三元组表中的位置         //默认第一列首个非0元素寸法感到新三元组表的位置0         cpot[0] = 0;         for(col=1; colnu; ++col)         {             cpot[col] = cpot[col-1] + num[col-1];         }

        int q = 0;         /*这里是依次遍历矩阵M的三元组表，找到每个元素对应矩阵的哪一列，再通过cpot[col]找到每列的第一个非零元素，本质还是按照每列的次序去重排三元组表*/         for(int p=0; ptu; ++p)         {             col = M->data[p].j;             q = cpot[col];             /*取出cpot数组中cpot[col]的值，注意，这里很重要：因为在顺序表中，所有的行元素的大小已经是依次排好的，            所以我们遍历到的这个三元组时，当其与其后面的拥有相同列元素的三元组进行比较的时候，它一定是最小的，            所以应该放在前面时，所以我们取完这个值之后，将cpot[col]的值+1，即可在下面的遍历中搜索到与之邻近的            值，正好下标已经+1，直接添加上去即可*/             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]++;         }     }     free(num);     free(cpot); }

main.c

 #include"SparseMatrix.h"

void main() {     SMatrix sm, sm1;     memset(&sm, 0, sizeof(sm));     CreateMatrix(&sm);     PrintMatrix(&sm);

    //TransposeMatrix(&sm, &sm1);     //CopyMatrix(&sm, &sm1);     FastTransposeMatrix(&sm, &sm1);     PrintMatrix(&sm1); }