稀疏矩阵的压缩存储

稀疏矩阵的压缩存储:

实现稀疏矩阵压缩存储,并实现矩阵转置和求和。

输入矩阵时,首先需要输入非零元素的个数,然后分别输入矩阵的 行号,列号和值。

输完2个矩阵后,自动进行计算第一个矩阵的转置以及两个矩阵的和。

例如:输入如下:

100 90 5 //矩阵的行数为100,列数为90,共5个非零元素。
1 10 100 //a(1,10)=100
50 60 200//a(50,60)=200
50 80 100//a(50,80)=100
60 60 200//a(60,60)=200
99 89 10//a(99,89)=10
100 90 4 //矩阵b的行数为100,列数为90,共4个非零元素。
1 1 10 //b(1,1)=10
50 60 -200//b(50,60)=-200
50 80 100 //b(50,80)=100
70 70 10 //b(70,70)=10

代码如下:

#include <iostream>

using namespace std;
#include <stdlib.h>
struct Trituple{//三元组类Trituple
    int row,col,value;
};
class SparseMatrix{//稀疏矩阵的类声明
    friend ostream& operator << (ostream& out,SparseMatrix &M);//友元函数,输出流操作符重载
    friend istream& operator >> (istream& in,SparseMatrix &M);//友元函数,输入流操作符重载
private:
    int Rows,Cols,Terms;
    int maxTerms;
    Trituple *smArray;
public:
    SparseMatrix(int maxSz=100);//构造函数
    SparseMatrix(SparseMatrix &x);//拷贝构造函数
    ~SparseMatrix(){delete [] smArray;}//析构函数
    void Transpose();//转置运算
    void Add(SparseMatrix &b,SparseMatrix &c);//矩阵相加

};
SparseMatrix::SparseMatrix(int maxSz)
{
    maxTerms=maxSz;
    if(maxSz<1)
    {
        cerr<<"矩阵初始化错误!"<<endl;
        exit(1);
    }
    smArray=new Trituple[maxSz];
    if(smArray==NULL)
    {
        cerr<<"存储分配错!"<<endl;
        exit(1);
    }
    Rows=Cols=Terms=0;
};
SparseMatrix::SparseMatrix(SparseMatrix &x)
{
    Rows=x.Rows;
    Cols=x.Cols;
    Terms=x.Terms;
    maxTerms=x.maxTerms;
    smArray=new Trituple[maxTerms];
    if(smArray==NULL)
    {
        cerr<<"存储分配错!"<<endl;
        exit(1);
    }
    for(int i=0;i<maxTerms;i++)
    {
        smArray[i]=x.smArray[i];
    }
}
ostream &operator<<(ostream& out,SparseMatrix& M)
{
    for(int i=0;i<M.Terms;i++)
    {
        out<<M.smArray[i].row<<" "<     }
    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;
}
void SparseMatrix::Transpose()
{
    int temp;
    for(int i=0;i<Terms;i++)
    {
        temp=smArray[i].row;
        smArray[i].row=smArray[i].col;
        smArray[i].col=temp;
    }
    for(int i=0;i<Terms-1;i++)
    {
        for(int j=i+1;j<Terms;j++)
        {
            if(smArray[i].row>smArray[j].row||(smArray[i].row==smArray[j].row&&smArray[i].col>smArray[j].col))
            {
                Trituple temp;
                temp=smArray[i];
                smArray[i]=smArray[j];
                smArray[j]=temp;
            }
        }
    }
}
void SparseMatrix::Add(SparseMatrix& b,SparseMatrix& c)
{
    if(Rows==b.Rows&&Cols==b.Cols)
    {
        int i=0,j=0,k=0;
        while(i<Terms&&j<b.Terms)
        {
            if(smArray[i].row==b.smArray[j].row)
            {
                if(smArray[i].col                 {
                    c.smArray[k].row=smArray[i].row;
                    c.smArray[k].col=smArray[i].col;
                    c.smArray[k].value=smArray[i].value;
                    k++;
                    i++;
                }
                else if(smArray[i].col>b.smArray[j].col)
                {
                    c.smArray[k].row=b.smArray[j].row;
                    c.smArray[k].col=b.smArray[j].col;
                    c.smArray[k].value=b.smArray[j].value;
                    k++;
                    j++;
                }
                else{
                    int t;
                    t=smArray[i].value+b.smArray[j].value;
                    if(t!=0)
                    {
                        c.smArray[k].row=smArray[i].row;
                        c.smArray[k].col=smArray[i].col;
                        c.smArray[k].value=smArray[i].value+b.smArray[j].value;
                        k++;
                    }
                    i++;j++;
                }
            }
            else if(smArray[i].row             {
                c.smArray[k].row=smArray[i].row;
                c.smArray[k].col=smArray[i].col;
                c.smArray[k].value=smArray[i].value;
                k++;
                i++;
            }
            else
            {
                c.smArray[k].row=b.smArray[j].row;
                c.smArray[k].col=b.smArray[j].col;
                c.smArray[k].value=b.smArray[j].value;
                k++;
                j++;
            }
        }
        while(i<Terms)
        {
            c.smArray[k].row=smArray[i].row;
            c.smArray[k].col=smArray[i].col;
            c.smArray[k].value=smArray[i].value;
            k++;
            i++;
        }
        while(j<b.Terms)
        {
            c.smArray[k].row=b.smArray[j].row;
            c.smArray[k].col=b.smArray[j].col;
            c.smArray[k].value=b.smArray[j].value;
            k++;
            j++;
        }
        c.Terms=k;
    }
};
int main()
{
    SparseMatrix a,b,c;
    cin>>a;
    cin>>b;
    a.Add(b,c);
    a.Transpose();
    cout<<"The transformed matrix  is:"<<endl;
    cout<<a;
    cout<<"The added matrix is:"<<endl;
    cout<<c;
    return 0;
}


You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注