练习9——稀疏矩阵

1、转置

1.1第一种想法

1.1.1思想：每次从原矩阵中复制一列到新的矩阵中。1）设矩阵列数为cols，对矩阵三元组扫描cols次；2）第k次扫描寻找所有列号为k的项：将其行号变列号、列号变行号，顺次存于转置矩阵三元组中。

1.1.2代码

void SparseMatrix::Transpose(SparseMatrix &b) {
    b.Rows=Rows;b.Cols=Cols;b.Terms=Terms;
    if(Terms==0)
        return ;
    int CurrentB=0;
    int i,k;
    for(k=0;k<Cols;k++){
        for(i=0;i<Terms;i++){
            if(smArray[i].col==k){
                b.smArray[CurrentB].row=k;
                b.smArray[CurrentB].col=smArray[i].row;
                b.smArray[CurrentB].value=smArray[i].value;
                CurrentB++;
            }
        }
    }
}

1.1.3评价：算法的时间代价为O(cols*terms)。如果非零元素变多时，算法的时间代价也会变大。

练习9——稀疏矩阵

1.2快速转置算法（推荐）

1.2.1思想：对原矩阵A扫描一遍，按A中每一元素的列号，确定在转置矩阵B中三元组中的位置，并装入它。

1.2.2代码：

void SparseMatrix::FasrTranspos(SparseMatrix &b) {
    int *rowSize=new int[Cols];//列元素数数组
    int *rowStart=new int[Cols];//转置位置数组
    b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;
    if(Terms>0){
        int i,j;
        for(i=0;i<Cols;i++){
            rowSize[i]=0;
        }
        for(i=0;i<Terms;i++){
            rowSize[smArray[i].col]++;//记录每列非零元素个数
        }
        rowStart[0]=0;
        for(i=1;i<Cols;i++){
            rowStart[i]=rowStart[i-1]+rowSize[i-1];//记录每个元素在三元组中的位置
        }
        for(i=0;i<Terms;i++){
            j=rowStart[smArray[i].col];
            b.smArray[j].row=smArray[i].col;
            b.smArray[j].col=smArray[i].row;
            b.smArray[j].value=smArray[i].value;
            rowStart[smArray[i].col]++;
        }
    }
    delete[] rowSize;
    delete[] rowStart;
}

练习9——稀疏矩阵

1.2.3评价：1)时间复杂度：O(2Cols+2Terms);2);当Terms<<Rows*Cols时，比一般转置算法；3)在空间复杂性上，该算法多用了两个辅助向量，是以少量空间换取了较快的执行速度。

附录（完整代码）：

#include <iostream>
using namespace std;
typedef int T;
struct Triple{
    int row,col;
    T value;
    void operator=(Triple &R){
        row=R.row;
        col=R.col;
        value=R.value;
    }
};
class SparseMatrix{
private:
    int Rows,Cols,Terms;
    Triple *smArray;
public:
    SparseMatrix(int maxSize=100);
    void Transpose(SparseMatrix &b);
    void FasrTranspos(SparseMatrix &b);
    friend ostream& operator << (ostream &out,SparseMatrix &M);
    friend istream& operator >> (istream &in,SparseMatrix &M);
};
SparseMatrix::SparseMatrix(int maxSize) {
    Terms=maxSize;
    smArray=new Triple[Terms];
    if(smArray==NULL){
        cerr<<"存储分配失败"<<endl;
        exit(1);
    }
    Rows=Cols=0;
}
//每次从原矩阵中复制一列到新的矩阵中。
// 1）设矩阵列数为cols，对矩阵三元组扫描cols次；
// 2）第k次扫描寻找所有列号为k的项：将其行号变列号、列号变行号，顺次存于转置矩阵三元组中。
void SparseMatrix::Transpose(SparseMatrix &b) {
    b.Rows=Rows;b.Cols=Cols;b.Terms=Terms;
    if(Terms==0)
        return ;
    int CurrentB=0;
    int i,k;
    for(k=0;k<Cols;k++){
        for(i=0;i<Terms;i++){
            if(smArray[i].col==k){
                b.smArray[CurrentB].row=k;
                b.smArray[CurrentB].col=smArray[i].row;
                b.smArray[CurrentB].value=smArray[i].value;
                CurrentB++;
            }
        }
    }
}
void SparseMatrix::FasrTranspos(SparseMatrix &b) {
    int *rowSize=new int[Cols];//列元素数数组
    int *rowStart=new int[Cols];//转置位置数组
    b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;
    if(Terms>0){
        int i,j;
        for(i=0;i<Cols;i++){
            rowSize[i]=0;
        }
        for(i=0;i<Terms;i++){
            rowSize[smArray[i].col]++;//记录每列非零元素个数
        }
        rowStart[0]=0;
        for(i=1;i<Cols;i++){
            rowStart[i]=rowStart[i-1]+rowSize[i-1];//记录每个元素在三元组中的位置
        }
        for(i=0;i<Terms;i++){
            j=rowStart[smArray[i].col];
            b.smArray[j].row=smArray[i].col;
            b.smArray[j].col=smArray[i].row;
            b.smArray[j].value=smArray[i].value;
            rowStart[smArray[i].col]++;
        }
    }
    delete[] rowSize;
    delete[] rowStart;
}
ostream & operator<<(ostream &out,SparseMatrix &M){
    for(int i=0;i<M.Terms;i++){
        out<<M.smArray[i].row<<" "<<M.smArray[i].col<<" "<<M.smArray[i].value<<endl;
    }
    return out;
}

istream &operator>>(istream &in, SparseMatrix &M) {
    in>>M.Rows>>M.Cols>>M.Terms;
    for(int i=0;i<M.Terms;i++){
        in>>M.smArray[i].row>>M.smArray[i].col>>M.smArray[i].value;
    }
    return in;
}

int main(){
    SparseMatrix s1,s2;
    cin>>s1;
    cout<<"输入为："<<endl;
    cout<<s1;
    s1.FasrTranspos(s2);
    cout<<"输出为："<<endl;
    cout<<s2;
}

练习9——稀疏矩阵

相关推荐