博客

矩阵的快速转置算法

数据压缩是提高传输、存储效率一种技术。教材第5章介绍了两种简单的压缩存储方法。本实验要求实现三元组顺序表表示下的矩阵快速转置算法

。

输入：

稀疏矩阵的行数、列数、非零元个数(三个数都大于0)

以行为主序输入稀疏矩阵三元组表

输出：

辅助数组num[ ]

辅助数组cpot[ ]

以行为主序输出对应的转置矩阵三元组表

代码

#include"iostream"  
  
using namespace std;  
  
//三元组表   
typedef struct{  
    int i,j,e;  
}SANYUAN;  
  
//稀疏矩阵   
typedef struct{  
    SANYUAN list[10001];  
    int row,col,nu; //行数，列数，非零元个数   
}JUZHEN;  
  
//辅助数组   
int num[1010]={0};  
int cpot[1010]={0};  
  
int main(){  
    //定义两个矩阵变量  
    JUZHEN A,B;  
      
    //输入三元组表  
    cin>>A.row>>A.col>>A.nu;  
    for(int i=1;i<=A.nu;i++){  
        cin>>A.list[i].i>>A.list[i].j>>A.list[i].e;  
    }  
    //转置  
    B.row=A.col;  
    B.col=A.row;  
    B.nu=A.nu;  
      
    if(B.nu){  
        //初始化num  
        for(int i=1;i<=A.col;++i){  
            num[i]=0;  
        }   
        //非零元++  
        for(int i=1;i<=B.nu;++i){  
            ++num[A.list[i].j];  
        }  
        //cpot  
        cpot[0]=1;  
        cpot[1]=1;  
          
        for(int col=2;col<=A.col;++col){  
            cpot[col]=cpot[col-1]+num[col-1];  
        }  
        //转置   
        for(int p=1;p<=A.nu;++p){  
            int col=A.list[p].j;  
            int q=cpot[col];  
            B.list[q].i=A.list[p].j;  
            B.list[q].j=A.list[p].i;  
            B.list[q].e=A.list[p].e;  
              
            ++cpot[col];   
        }  
          
    }   
    //输出辅助数组  
    cout<<"num:";  
    for(int i=1;i<=A.col;++i){  
        cout<<num[i]<<",";  
    }  
    cout<<endl<<"cpot:";  
    for(int i=0;i<A.col;++i){  
        cout<<cpot[i]<<",";  
    }  
    cout<<endl;  
      
    //输出转置后三元组表   
    for(int i=1;i<=B.nu;++i){  
        cout<<B.list[i].i<<","<<B.list[i].j<<","<<B.list[i].e<<endl;   
    }  
    return 0;  
}