[转载]C++中稀疏矩阵的一种实现

2013100302.cpp

#include <iostream>
#include <iomanip>
using namespace std;
 
template<class T>
//三元组
struct Trituple
{
    int row;
    int col;
    T val;
};
//稀疏矩阵声明
template<class T>
class SparseMatrix
{
public:
    SparseMatrix(int maxt=100);
    ~SparseMatrix();
    bool TransposeTo(SparseMatrix &);
    bool AddTo(const SparseMatrix&);
    bool TransposeTo_Faster(SparseMatrix&);
    void Input();
    void Output();
private:
    Trituple<T>* data;
    int rows,cols,terms;
    int maxterms;
};
template<class T>
SparseMatrix<T>::SparseMatrix(int maxt)
{
    maxterms=maxt;
    data=new Trituple<T>[maxterms];
    terms=rows=cols=0;
}
template<class T>
SparseMatrix<T>::~SparseMatrix()
{
    if (data!=NULL)
    {
        delete[] data;
    }
}
//普通转置
template<class T>
bool SparseMatrix<T>::TransposeTo(SparseMatrix &B)
{
    if (terms>B.maxterms)
    {
        return false;
    }
    B.rows=cols;
    B.cols=rows;
    B.terms=terms;
    if (terms>0)
    {
        int p=0;
        for (int j=1;j<=cols;j++)
        {
            for (int k=0;k<terms;k++)
            {
                if (data[k].col==j)
                {
                    B.data[p].row=j;
                    B.data[p].col=data[k].row;
                    B.data[p].val=data[k].val;
                    p++;
                }
            }
        }
    }
    return true;
}
//快速转置
template<class T>
bool SparseMatrix<T>::TransposeTo_Faster(SparseMatrix& B)
{
    if (terms>B.maxterms)
    {
        return false;
    }
    B.rows=cols;
    B.cols=rows;
    B.terms=terms;
    if (terms>0)
    {
        int *num,*cpot;
        num=new int[cols];
        cpot=new int[cols];
        for (int j=0;j<cols;j++)
        {
            num[j]=0;
        }
        for (int k=0;k<terms;k++)
        {
            num[data[k].col-1]++;
        }
        //求出B中每一行的起始下标cpot[]
        cpot[0]=0;
        for (int j=1;j<cols;j++)
        {
            cpot[j]=cpot[j-1]+num[j-1];
        }
        //执行转置操作
        for (int p,k=0;k<terms;k++)
        {
            p=cpot[data[k].col-1]++;
            B.data[p].row=data[k].col;
            B.data[p].col=data[k].row;
            B.data[p].val=data[k].val;
        }
        delete[] num;
        delete[] cpot;
    }
    return true;
}
template<class T>
void SparseMatrix<T>::Input()
{
    cout<<"intput the matrix' row:";
    int row1;
    cin>>row1;
    cout<<"intput the matrix' col:";
    int col1;
    cin>>col1;
    cout<<"input "<<row1<<"*"<<col1<<" matrix"<<endl;
    int number;
    rows=row1;
    cols=col1;
    for (int i=0;i<rows;i++)
    {
        for (int j=0;j<cols;j++)
        {
            cin>>number;
            if (number!=0)
            {
                data[terms].row=i+1;
                data[terms].col=j+1;
                data[terms].val=number;
                terms++;
            }
        }
    }
}
template<class T>  //输出好看，但是违背了最初的原则
void SparseMatrix<T>::Output()
{
    T **tempArray=new T*[rows];
    for (int i1=0;i1<rows;i1++)
    {
        tempArray[i1]=new int[cols];
    }
    for (int j=0;j<rows;j++)
    {
        for (int k=0;k<cols;k++)
        {
            tempArray[j][k]=0;
        }
    }
    for (int i=0;i<terms;i++)
    {
        tempArray[data[i].row-1][data[i].col-1]=data[i].val;
    }
    for (int j=0;j<rows;j++)
    {
        for (int k=0;k<cols;k++)
        {
            cout<<setw(4)<<tempArray[j][k];
        }
        cout<<endl;
    }
    for (int l=0;l<rows;l++)
    {
        delete[] tempArray[l];
    }
    delete tempArray;
    cout<<endl;
}
template<class T>
bool SparseMatrix<T>::AddTo(const SparseMatrix& B)
{
    if (rows!=B.rows||cols!=B.cols)
    {
        return false;
    }
    bool flag=false;
    int tempTerms=terms;
    for (int i=0;i<B.terms;i++)
    {
        flag=false;
        for (int j=0;j<tempTerms;j++)
        {
            if (data[j].col==B.data[i].col&&data[j].row==B.data[i].row)
            {
                data[j].val+=B.data[i].val;
                flag=true;
            }
        }
        if (flag==false)
        {
            data[++terms-1].col=B.data[i].col;  //数组下标操作注意事项
            data[terms-1].row=B.data[i].row;
            data[terms-1].val=B.data[i].val;
        }
    }
    return true;
}
int main()
{
    cout<<"此程序演示稀疏矩阵的普通转置和快速转置操作"<<endl;
    SparseMatrix<int> sm(50);
    SparseMatrix<int> sm1(50);
    SparseMatrix<int> sm2(50);
    sm.Input();
    cout<<"sm is"<<endl;
    sm.Output();
    sm.TransposeTo(sm1);
    cout<<"Transposition of sm is "<<endl;
    sm1.Output();
    sm.TransposeTo_Faster(sm2);
    cout<<"Transposition of sm is "<<endl;
    sm2.Output();
    SparseMatrix<int> sm3;
    cout<<"input a new matrix"<<endl;
    sm3.Input();
    cout<<"sm3 is"<<endl;
    sm3.Output();
    if(sm.AddTo(sm3))
    {
        cout<<"after adding sm3 ,sm is"<<endl;
        sm.Output();
    }
    else
        cout<<"the two matrix can't add"<<endl;
    cout<<"Good job!"<<endl;
    system("pause");
    return 0;
}