稀疏矩阵及其逆置矩阵

稀疏矩阵及其逆置矩阵：在矩阵中，若数值为0的元素数目远远多于非0元素的数目时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。

M*N的矩阵，矩阵中有效值得个数远小于无效值的个数，且这些数据的分布没有规律。

【稀疏矩阵压缩存储】 压缩存储值存储极少数的有效数据。使用{row，col，value}三元组(Trituple)存储 每一个有效数据，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。

矩阵逆置
将原矩阵的行、列对换，也就是将[i][j]和[j][i]位置上的数据对换。

快速逆置

源代码如下：

#include
#include
#include 
using namespace std;

//实现稀疏矩阵的压缩存储、转置以及快速逆置、两个稀疏矩阵相加
template
class SparseMatrix
{
    template
    struct Trituple  //封装三元组
    {
        Trituple(int row = 0, int col = 0, const T& value= T())
            : _row(row)
            , _col(col)
            , _value(value)
        {}

        size_t _row;
        size_t _col;
        T _value;
    };

public:
    // 
    SparseMatrix(T* array, size_t row, size_t col, const T& invalid)
        :_row(row)
        ,_col(col)
        ,_invalid(invalid)
    {
        for(size_t i=0; i<_row; i++)
        {
            for(size_t j=0; j<_col; j++)
            {
                if(array[i*_col + j] != invalid)
                {
                    _sm.push_back(Trituple(i, j, array[i*_col  +j]));
                }
            }
        }
    }
    SparseMatrix()
    {}

    // 访问矩阵中的元素
    T& Access(int row, int col)
    {
        vector>::iterator it = _sm.begin();

        while(it != _sm.end())
        {
            if(it->_row == row && it->_col == col)
            {
                return it->_value;
            }
            ++it;
        }

        return _invalid;  //找不到存储的值就返回无效值
    }

    template
    friend ostream& operator<<(ostream& _cout, const SparseMatrix& sm)
    {
        size_t index = 0;
        for(size_t i=0; i Transport()
    {
        SparseMatrix temp;
        temp._row = _col;
        temp._col = _row;
        temp._invalid = _invalid;

        for(size_t i=0; i<_col; ++i)
        {
            size_t index =0 ;
            while(index<_sm.size())
            {
                Trituple &t = _sm[index];
                if(t._col == i)
                {
                    temp._sm.push_back(Trituple(t._col, t._row, t._value));  
                }
                index++;
            }
        }
        return temp;
    }

    // 稀疏矩阵的快速转置
    SparseMatrix FastTransport()
    {
        SparseMatrix temp;
        temp._col = _row;
        temp._row = _col;
        temp._invalid = _invalid;
        temp._sm.resize(_sm.size());

        //统计原矩阵中每一列有效个数
        int *pCount = new int[_col];
        memset(pCount, 0, _col*sizeof(int));

        vector>::iterator it = _sm.begin();
        while(it != _sm.end())
        {
            pCount[it->_col]++;
            ++it;
        }

        //原矩阵中每一列有效数据在新矩阵中的起始位置
        int *pAddr = new int[_col];
        memset(pAddr, 0, _col*sizeof(int));
        for(size_t i=1; i<_col; ++i)
        {
            pAddr[i] = pAddr[i-1] + pCount[i-1];
        }

        //放置元素
        it = _sm.begin();
        while(it != _sm.end())
        {
            temp._sm[pAddr[it->_col]] = Trituple(it->_col, it->_row, it->_value);
            pAddr[it->_col]++;
            ++it;
        }

        delete[] pCount;
        delete[] pAddr;

        return temp;
    }

    // 两个矩阵相加
    SparseMatrix operator+(const SparseMatrix& sp)
    {
        assert(_row == sp._row);
        assert(_col == sp._col);

        SparseMatrix sum;
        sum._row = _row;
        sum._col = _col;
        sum._invalid = _invalid;

        int idxL = 0;
        int idxR = 0;
        int leftAddr = 0;
        int rightAddr = 0;

        while(idxL < _sm.size() && idxR < sp._sm.size())
        {
            leftAddr = _sm[idxL]._row*_col + _sm[idxL]._col;
            rightAddr = sp._sm[idxR]._row*_col + sp._sm[idxR]._col;

            if(leftAddr < rightAddr)
            {
                sum._sm.push_back(_sm[idxL++]);
                continue;
            }
            else if(leftAddr > rightAddr)
            {
                sum._sm.push_back(sp._sm[idxR++]);
                continue;
            }
            else
            {
                T value = _sm[idxL]._value + sp._sm[idxR]._value;
                if(value != _invalid)
                {
                    sum._sm.push_back(Trituple(_sm[idxL]._row, _sm[idxL]._col, value));
                    idxL++;
                    idxR++;
                }
            }
        }
        if(!_sm.empty())
        {
            while(idxL < _sm.size())
            {
                sum._sm.push_back(_sm[idxL++]);
            }
            while(idxR < sp._sm.size())
            {
                sum._sm.push_back(sp._sm[idxR++]);
            }
        }
        return sum;
    }

private:
    vector> _sm;
    size_t _row;  //行数
    size_t _col;  //列数
    T _invalid;   //无效值
};

void FunTest()
{
    int array1 [6][5] = {
        {1, 0, 3, 0, 5},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0},
        {1, 0, 3, 0, 5},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0}};

    int array2 [6][5] = {
            {1, 0, 3, 0, 5},
            {0, 2, 0, 0, 0},
            {0, 0, 0, 0, 0},
            {1, 0, 3, 0, 5},
            {0, 0, 8, 0, 0},
            {0, 0, 0, 0, 1}};

    SparseMatrix sm((int*)array1, 6, 5, 0);
    SparseMatrix sm4((int*)array2, 6, 5, 0);
    /*cout< sm1;
    SparseMatrix sm2;
    sm1 = sm.Transport();
    sm1.PrintMatrix();

    sm2 = sm.FastTransport();
    sm2.PrintMatrix();*/

    sm4.PrintMatrix();
    cout< sm3;
    sm3 = sm+sm4;
    sm3.PrintMatrix();
}

int main()
{
    FunTest();

    system("pause");
    return 0;
}