矩阵相关

矩阵：是一个具有m行n列的二维数组。

上三角矩阵：只存储对角线及对角线（左上角到右下角）以上的元素。反之则称为下三角矩阵。

稀疏矩阵：非0元素远远小于0元素个数，而且这些元素没有规律

矩阵转置：把原矩阵的行，列对换，在原矩阵中[i][j]位置中的元素，交换到转置矩阵中[j][i]的位置上
SparseMatrix.h

#include<iostream>
#include<stdlib.h>
#include<cassert>
using namespace std;
const int DefaultSize = 100;
template<class T>

class Trituple{
public:
    int row,col;
    T val;//非0元素值
    Trituple<T> &operator=(Trituple<T>& x){
        row = x.row;
        col = x.col;
        val = x.val;
    }
};

template<class T>
class SparseMatrix{
    friend ostream& operator<<(ostream& out,SparseMatrix<T>& M){
        out << "Rows:" << M.Rows << endl;
        out << "Cols:" << M.Cols << endl;
        out << "Terms:" << M.Terms << endl;
        for(int i=0;i<M.Terms;++i){
            out << "M[" << M.smArray[i].row << ","
                << M.smArray[i].col << "]:" << M.smArray[i].val
                << endl;
        }
        return out;
    }
    friend istream& operator>>(istream& in,SparseMatrix<T>& M){
        cout << "Enter number of rows,columns,and terms" << endl;
        in >> M.Rows >> M.Cols >> M.Terms;
        if(M.Terms>M.maxTerms){
            cerr << "Number of terms overflow!" << endl;
            exit(1);
        }
        for(int i=0;i<M.Terms;++i){
            cout << "Enter rows,columns and value of term:" << i+1 << endl;
            in >> M.smArray[i].row >> M.smArray[i].col >> M.smArray[i].val;
        }
        return in;
    }
public:
    SparseMatrix(int maxSz=DefaultSize);
    SparseMatrix(SparseMatrix<T>& x);
    ~SparseMatrix(){delete[] smArray;}
    SparseMatrix<T>& operator=(SparseMatrix<T>& x);
    SparseMatrix<T> Transpose();
    SparseMatrix<T> Add(SparseMatrix<T>& b);
    SparseMatrix<T> Multiply(SparseMatrix<T>& b);
private:
    int Rows,Cols,Terms;//非0元素个数
    Trituple<T> *smArray;
    int maxTerms;
};

template<typename T>
SparseMatrix<T>::SparseMatrix(int maxSz):maxTerms(maxSz)
{
    if(maxSz<1){
        cerr << "invalid size" << endl;
        exit(1);
    }
    smArray = new Trituple<T>[maxSz];
    assert(smArray!=NULL);
    Rows = Cols = Terms = 0;
}

template<typename T>
SparseMatrix<T>::SparseMatrix(SparseMatrix<T> &x)
{
    Rows = x.Rows;
    Cols = x.Cols;
    Terms = x.Terms;
    maxTerms = x.maxTerms;
    smArray = new Trituple<T>[maxTerms];
    assert(smArray!=NULL);
    for(int i=0;i<maxTerms;++i){
        smArray[i] = x.smArray[i];
    }
}

/*
  返回一个新的矩阵，它是原矩阵的转置
  */
template<typename T>
SparseMatrix<T> SparseMatrix<T>::Transpose()
{
    SparseMatrix b(maxTerms);//转置矩阵的三元组表
    b.Rows = Cols;
    b.Cols = Rows;
    b.Terms = Terms;
    if(Terms>0)
    {
        int currentB = 0;
        for(int i=0;i<Cols;++i)//按列优先顺序依次存放
        {
            for(int t=0;t<Terms;++t)
            {
                if(smArray[t].col==i)
                {
                    b.smArray[currentB].col = smArray[t].row;
                    b.smArray[currentB].row = smArray[t].col;
                    b.smArray[currentB].val = smArray[t].val;
                    currentB++;
                }
            }
        }
    }
}

/*
  前提条件是：两矩阵的大小相同，行数和列数分别对应相等
  */
template<typename T>
SparseMatrix<T> SparseMatrix<T>::Add(SparseMatrix<T> &b)
{
    SparseMatrix<T> result(maxTerms);
    if(Rows!=b.Rows||Cols!=b.Cols){
        cerr << "can not add" << endl;
        return result;
    }
    int termA = Terms,termB = b.Terms,indexA,indexB;
    int i=0,j=0,k=0;
    //O(Terms+b.Terms)比直接两个for循环O(Terms*b.Terms)要好
    while(i<termA||j<termB){
        //计算位置
        indexA = Cols*smArray[i].row+smArray[i].col;
        indexB = Cols*b.smArray[i].row+b.smArray[i].col;
        if(indexA>indexB){
            result.smArray[k]=b.smArray[j];
            j++;
        }
        if(indexA<indexB){
            result.smArray[k]=smArray[i];
            i++;
        }
        if(indexA==indexB){
            result.smArray[k].col = smArray[i].col;
            result.smArray[k].row = smArray[i].row;
            result.smArray[k].val = smArray[i].val+b.smArray[j].val;
            i++;
            j++;
        }
        k++;
    }
    while(i<termA){
        result.smArray[k] = smArray[i];
        i++;
        k++;
    }
    while(j<termB){
        result.smArray[k] = b.smArray[j];
        j++;
        k++;
    }
    result.Terms = k;
    return result;
}

/*
  前提条件是：A的列数=B的行数
  */
template<typename T>
SparseMatrix<T> SparseMatrix<T>::Multiply(SparseMatrix<T> &b)
{
    SparseMatrix<T> result(Rows*b.Cols);
    if(Cols!=b.Rows){
        cerr << "can not multiply" << endl;
        return result;
    }
    if(Terms==maxTerms||b.Terms==maxTerms){
        cerr << "One additional space is a or b needed" << endl;
        return result;
    }
    int *rowSize = new int[b.Rows];
    int *rowStart = new int[b.Rows+1];
    T *temp = new T[b.Cols];
    int i,Current,lastInResult,RowA,ColA,ColB;
    for(i=0;i<b.Rows;i++)
        rowSize[i] = 0;
    for(i=0;i<b.Terms;i++)
        rowSize[b.smArray[i].row]++;
    rowStart[0]=0;
    for(i=1;i<=b.Rows;i++)
        rowStart[i] = rowStart[i-1]+rowSize[i-1];
    Current = 0;
    lastInResult = -1;
    while(Current<Terms){
        RowA = smArray[Current].row;
        for(i=0;i<b.Cols;i++)
            temp[i]=0;
        while(Current<Terms&&smArray[Current].row==RowA){
            ColA = smArray[Current].col;
            for(i=rowStart[ColA];i<rowStart[ColA+1];i++){
                ColB = b.smArray[i].col;
                temp[ColB] += smArray[Current].val*b.smArray[i].val;
            }
            Current++;
        }
    }
    for(i=0;i<b.Cols;i++){
        if(temp[i]!=0){
            lastInResult++;
            result.smArray[lastInResult].row = RowA;
            result.smArray[lastInResult].col = i;
            result.smArray[lastInResult].val = temp[i];
        }
    }
    result.Rows = Rows;
    result.Cols = Cols;
    result.Terms = lastInResult+1;
    delete[] rowSize;
    delete[] rowStart;
    delete[] temp;
    return result;
}