稀疏矩阵的压缩存储及转置，快速转置法，C++代码实现

/*稀疏矩阵的压缩存储及转置*/

#include <iostream>
using namespace std;

/*三元组顺序表的类型定义*/
#define itemSize 100

typedef struct
{
    int row,col;
    int item;
}thNode;

typedef struct
{
    thNode * data;//data[0]不用
    int m,n,t;//分别表示行数、列数和非零元素个数
}thMatrix;


/*初始化三元组表*/
void initMatrix_Th(thMatrix &M)
{
    M.data=new thNode[itemSize+1];
    M.m=0;
    M.n=0;
    M.t=0;
}

/*转置三元组表*/

//一般方法，算法时间复杂度较高
void  transMatrix_1(thMatrix M,thMatrix &T)
{
    initMatrix_Th(T);
    T.m=M.n;
    T.n=M.m;
    T.t=M.t;

    if(T.t)
    {
        int p=1;//用来指M中的元素
        int q=1;//用来指T中的元素
        int col;//用来遍历列中的元素

        for(col=1;col<=M.n;col++)
        {
            for(p;p<=M.t;p++)
            {
                if(M.data[p].col==col)
                {
                    T.data[q].row=M.data[p].col;
                    T.data[q].col=M.data[p].row;
                    T.data[q].item=M.data[p].item;
                    q++;
                }
            }
        }
    }
}

//改进的方法——快速转置
void transMatrix_2(thMatrix M,thMatrix &T)
{
    initMatrix_Th(T);
    T.m=M.n;
    T.n=M.m;
    T.t=M.t;

    int i,j,p,q;
    int num[100];
    int cpot[100];
    if(T.t)
    {
        for(i=1;i<=M.n;i++)
            num[i]=0;//M中每一列的非零元素个数初始化为0
        for(i=1;i<=M.t;i++)
            ++num[M.data[i].col];//M中每一列的非零元素个数存储到一个数组中
        cpot[1]=1;
        for(i=2;i<=M.n;i++)
            cpot[i]=cpot[i-1]+num[i-1];//每一列第一个非零元素的位置
        for(p=1;p<=M.t;p++)
        {
            j=M.data[p].col;
            q=cpot[j];//确定第j列第一个非零元素的位置

            T.data[q].row=M.data[p].col;
            T.data[q].col=M.data[p].row;
            T.data[q].item=M.data[p].item;
            ++cpot[j];//指向下一个位置
        }
    }
}


/*创建一个三元组表*/

//按行优先存储
void creatMatrix(thMatrix &M,int n)
{
    initMatrix_Th(M);

    int i;
    cin>>M.m>>M.n;
    for(i=1;i<=n;i++)
    {
        cin>>M.data[i].row>>M.data[i].col>>M.data[i].item;
    }
    M.t=n;
}

/*输出一个三元组表*/
void outputMatrix(thMatrix M)
{
    int i;
    cout<<M.m<<" "<<M.n<<endl;
    cout<<M.t<<endl;
    for(i=1;i<=M.t;i++)
    {
        cout<<M.data[i].row<<" "<<M.data[i].col<<" "<<M.data[i].item<<endl;
    }
}

void main()
{
    thMatrix M;
    thMatrix T;

    creatMatrix(M,8);
    //outputMatrix(M);
    transMatrix_2(M,T);
    outputMatrix(T);
}