【数据结构】稀疏矩阵及其转置算法

稀疏矩阵

什么是稀疏矩阵？

假设在mxn的矩阵中，有t个元素不为零。令，称δ为矩阵的稀疏因子。通常认为δ≤0.05时称为稀疏矩阵。

显然，稀疏矩阵中为零的数据元素很多，当矩阵较大时采用正常的存储方式会使得对空间的占用较大，造成空间的浪费，因此要对矩阵进行压缩存储，即零元素不分配空间。

对稀疏矩阵的压缩存储，常采用三元组顺序表

#define MAXSIZE 12500
typedef struct{
    int i,j;   //该非零元的行下标和列下标
    ElemType e;
}Triple;
typedef struct{
    Triple data[MAXSIZE+1];//data[0]未用
    int mu,nu,tu;	//矩阵的行数、列数、非零元个数
}TSMatrix;

在这里，data域中表示非零元素的三元组是以行序为主序顺序排列的

稀疏矩阵的转置

对于mxn的矩阵，它的转置矩阵是一个nxm的矩阵，且T(i,j)=M(j,i),1≤i≤n，1≤j≤m

实现矩阵转置只需以下几步：

1. 将矩阵的行列值相互交换
2. 将每个三元组中的i和j相互调换
3. 重排三元组之间的次序

关键是如何实现第三步

给出矩阵M，求M的转置矩阵T

1.方法一：按M的行主列扫描M的三元组表，依次将对应列的元素转置存入T

void TransposeSMatrix(TSMatrix M, TSMatrix &T){
    T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
    if(T.tu){
        int q=1;
        for(int col=1;coi<=M.nu)
            for(int p=1;p<=M.tu;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++;//T向后++
                }
            }
    }
}

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

2.方法二：快速转置：提前找到每一个元素转置后的位置，一遍遍历，将每个元素存入对应位置

num[col]：表示第col列中非零元素个数

cpot[col]：表示第col列中第一个非零元素在转置后的位置

易知：

cpot[1]=1且

cpot[col]=cpot[col-1]+num[col-1] 2 ≤ col ≤ M.nu

void FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
    T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
    if(T.tu){
        for(col=1;col<M.nu;col++)
            num[col]=0;
        for(t=1;t<=M.tu;t++)
            num[M.data[t].j]++;//求每一列中非零元的个数
        copt[1]=1;
        //求第col列中第一个非零元在b.data的位置
        for(col=2;col<=M.nu;col++)
            cpot[col]=cpot[col-1]+num[col-1];
        //遍历一遍，转置
        for(p=1;p<=M.tu;p++){
            col=M.data[p].j;//确定第几列
            q=cpot[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;//转置
            ++copt[col];//该列位置++，使下一次找到该列元素时的位置向后移动一位
        }
    }
}

时间复杂度:O(nu+tu)