数据结构——稀疏矩阵三元组表示法+算法详解

（1）、目的：对于在实际问题中出现的大型的稀疏矩阵，若用常规分配方法在计算机中储存，将会产生大量的内存浪费，而且在访问和操作的时候也会造成大量时间上的浪费，为了解决这一问题，从而善生了多种解决方案。

（2）、由于其自身的稀疏特性，通过压缩可以大大节省稀疏矩阵的内存代价。具体操作是：将非零元素所在的行、列以及它的值构成一个三元组（i,j,v），然后再按某种规律存储这些三元组，这种方法可以节约存储空间。

具体如下图：

#define SMAX 1000
typedef struct
{
    int i,j;     //储存非零元素的行和列信息
    ElementType e; //非零元素的值
} Triple;       //定义三元组类型
typedef struct
{
    int mu,nu,tu; //矩阵的行、列和非零元素的个数
    Triple data[SMAX]; //三元组表
} TSMatrix；

注意：为更可靠描述，通常再加一个“总体”信息：即总行数、总列数、非零元素总个数。

用常规的二维数组表示时的算法：

for (col=1; col<=nu; ++col)
{
    for (row=1; row<=mu; ++row)
    {
        T[col][row] = M[row][col];
    }
}

其时间复杂度为: O(mu×nu)

用三元组表示如何实现呢？

解决思路：只要做到
将矩阵行、列维数互换
将每个三元组中的i和j相互调换
重排三元组次序，使mb中元素以N的行(M的列) 为主序

方法一：按列序转置

即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序。

void TransposeTSMatrix(TSMatrix  A,  TSMatrix  * B)
{
    /*求矩阵A的转置矩阵B，矩阵用三元组表表示*/
    int  p,q, k ;
    B->mu= A.nu ;
    B->nu= A.mu ;
    B->tu= A.tu ;
    if(B->tu)///整个矩阵非零元素的个数不为0
    {
        q=1;
        for(k=1; k<=A.nu; k++)///遍历A矩阵的列数
        {
            for(p=1; p<=A.tu; p++)///遍历矩阵A的三元组
            {
                if(A.data[p].j==k)///矩阵的列与三元组的列对应
                {
                    B->data[q].i=A.data[p].j;
                    B->data[q].j=A.data[p].i;
                    B->data[q].e=A.data[p].e;
                    q++;
                }
            }
        }
    }
}

时间复杂度：O（nu*tu)

方法二：快速转置

即按ma中三元组次序转置，转置结果放入b中恰当位置
此法关键是要预先确定M中每一列第一个非零元在mb中位置，
为确定这些位置，转置前应先求得M的每一列中非零元个数

实现：设两个数组

num[col]：表示矩阵M中第col列中非零元个数
cpot[col]：指示M中第col列第一个非零元在mb中位置

其中：

cpot[1]=1;

cpot[col]=cpot[col-1]+num[col-1]; (2<=col <=ma[0].j)

FastTransposeTSMatrix (TSMatrix  A,  TSMatrix  * B)
{
    /*基于矩阵的三元组表示，采用快速转置法，求矩阵A的转置矩阵B */
    int col,t,p,q;
    int num[MAXSIZE+1];///A每一列中非零元素的个数
    int cpot[MAXSIZE+1];///A每一列中第一个非零元素在B中的位置
    B->tu= A.tu ;
    B->nu= A.mu ;
    B->mu= A.nu ;
    if(B->tu)
    {
        for(col=1; col<=A.nu; col++)///初始化
        {
            num[col]=0;
        }
        for(t=1; t<=A.tu; t++)
        {
            num[A.data[t].j]++; /*计算每一列的非零元素的个数*/
        }
        cpot[1]=1;
        for(col=2; col<=A.nu; col++)
        {
            /*求col列中第一个非零元素在B->data[ ]中的正确位置*/
            cpot[col]= cpot[col-1]+num[col-1];
        }
        for(p=1; p<=A.tu; p++)///遍历三元组A
        {
            col=A.data[p].j;///col记录当前所处的列
            q=cpot[col];///q代表每一列第一个非零元素
            B->data[q].i=A.data[p].j;
            B->data[q].j=A.data[p].i;
            B->data[q].e=A.data[p].e;
            cpot[col]++;
            ///将A中每一列的第一个元素定位确定后，若这一列之后还有的元素那位置必然在第一个元素对应三元组位置的后面
        } 
    } 
}