稀疏矩阵C++语言实现

#include 

using namespace std;

template

//三元组

struct Trituple

{

    int row;

    int col;

    T val;

};

//稀疏矩阵声明

template

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* data;

    int rows,cols,terms;

    int maxterms;

};

template

SparseMatrix::SparseMatrix(int maxt)

{

    maxterms=maxt;

    data=new Trituple[maxterms];

    terms=rows=cols=0;

}

template

SparseMatrix::~SparseMatrix()

{

    if (data!=NULL)

    {

        delete[] data;

    }

}

//普通转置

template

bool SparseMatrix::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            {

                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

bool SparseMatrix::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        {

            num[j]=0;

        }

        for (int k=0;k        {

            num[data[k].col-1]++;

        }

        //求出B中每一行的起始下标cpot[]

        cpot[0]=0;

        for (int j=1;j        {

            cpot[j]=cpot[j-1]+num[j-1];

        }

        //执行转置操作

        for (int p,k=0;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

void SparseMatrix::Input()

{

    cout<<"intput the matrix' row:";

    int row1;

    cin>>row1;

    cout<<"intput the matrix' col:";

    int col1;

    cin>>col1;

    cout<<"input "<    int number;

    rows=row1;

    cols=col1;

    for (int i=0;i    {

        for (int j=0;j        {

            cin>>number;

            if (number!=0)

            {

                data[terms].row=i+1;

                data[terms].col=j+1;

                data[terms].val=number;

                terms++;

            }

        }

    }

}

template  //输出好看，但是违背了最初的原则

void SparseMatrix::Output()

{

    T **tempArray=new T*[rows];

    for (int i1=0;i1    {

        tempArray[i1]=new int[cols];

    }

    for (int j=0;j    {

        for (int k=0;k        {

            tempArray[j][k]=0;

        }

    }

    for (int i=0;i    {

        tempArray[data[i].row-1][data[i].col-1]=data[i].val;

    }

    for (int j=0;j    {

        for (int k=0;k        {

            cout<        }

        cout<    }

    for (int l=0;l    {

        delete[] tempArray[l];

    }

    delete tempArray;

    cout<}

template

bool SparseMatrix::AddTo(const SparseMatrix& B)

{

    if (rows!=B.rows||cols!=B.cols)

    {

        return false;

    }

    bool flag=false;

    int tempTerms=terms;

    for (int i=0;i    {

        flag=false;

        for (int j=0;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<<"此程序演示稀疏矩阵的普通转置和快速转置操作"<    SparseMatrix sm(50);

    SparseMatrix sm1(50);

    SparseMatrix sm2(50);

    sm.Input();

    cout<<"sm is"<    sm.Output();

    sm.TransposeTo(sm1);

    cout<<"Transposition of sm is "<    sm1.Output();

    sm.TransposeTo_Faster(sm2);

    cout<<"Transposition of sm is "<    sm2.Output();

    SparseMatrix sm3;

    cout<<"input a new matrix"<    sm3.Input();

    cout<<"sm3 is"<    sm3.Output();

    if(sm.AddTo(sm3))

    {

        cout<<"after adding sm3 ,sm is"<        sm.Output();

    }

    else

        cout<<"the two matrix can't add"<    cout<<"Good job!"<    system("pause");

    return 0;

}