压缩矩阵与稀疏矩阵（存储，快速转置）

1.压缩矩阵（对称矩阵）

template<class T>
class SymmetricMatrix
{
public:
    SymmetricMatrix(T * a,const size_t n)
        :_array(new T[n*(n + 1)/2])
        ,_n(n)
    {
        size_t index = 0;
        for(int i = 0;i < n;++i)
        {
            for(int j = 0;i < n;++j)
            {
                if(i >= j)
                {
                   _array[index++] = a[i*_n + j];
                }
                else
                {
                    break;
                }
            }
        }
    }
    void Print()
    {
        for(size_t i = 0;i < _n;++i)
        {
            for(size_t j = 0;j < _n;++j)
            {
                if(i >= j)
                {
                    cout<<_array[i*(i + 1)/2 + j]<<" ";
                }
                else
                {
                    cout<<_array[j*(j + 1)/2 + i]<<" ";
                }
            }
            cout<<endl;
        }
        cout<<endl;
    }
    ~SymmetricMatrix()
    {
        delete [] _array;
    }
private:
    T *_array;
    size_t _n;
};

void test()
{
    int arr[3][3] = { { 0, 1, 2 },{ 1, 0, 1 },{ 2, 1, 0 } };
    SymmetricMatrix<int> sm((int *)arr,3);

     sm.Print();
}

2.稀疏矩阵

#pragma once
#include <vector>

template<class T>
class Trituple
{
public:
    Trituple()
    {}
    Trituple(int row,int col,T& n)
        :_row(row)
        ,_col(col)
        ,_value(n)
    {}
    int _row;
    int _col;
    T _value;
};

template<class T>
class SparseMatrix//稀疏矩阵
{
public:
    SparseMatrix()
    {}
     SparseMatrix(T*a,const int m,const int n,T & invalid)
         :_rowSize(m)
         ,_colSize(n)
         ,_invalid(invalid)
     {
         size_t index = 0;
         for(size_t i = 0;i < _rowSize; ++i)
         {
             for(size_t j = 0;j < _colSize ; ++j)
             {
                if(a[i*_colSize+j] != _invalid)
                {
                    Trituple<T> t(i,j,a[i*_colSize+j]);
                    _array.push_back(t);
                }
             }
         }
     }
      void Print()
     {
          size_t index = 0;
         for(size_t i = 0;i < _rowSize; ++i)
         {
             for(size_t j = 0;j < _colSize ; ++j)
             {
                 if(index<_array.size() && i == _array[index]._row && j == _array[index]._col)
                 {
                      cout<<_array[index++]._value<<" ";
                 }
                 else
                 {
                      cout<<_invalid<<" ";
                 }
             }
              cout<<endl;
         }
        cout<<endl;
     }
     SparseMatrix<T> Transpose()
     {
        SparseMatrix<T> sm;
        sm._colSize = _rowSize;
        sm._rowSize = _colSize;
        sm._invalid = _invalid;
        for (int j = 0; j < _colSize; ++j)
        {
            int i = 0;
            while ( i < _array.size())
            {
                if(_array[i]._col == j)
                {
                    Trituple<T> t(_array[i]._col, _array[i]._row,_array[i]._value);
                    sm._array.push_back(t);
                }
                ++i;
            }

        }
        return sm;
     }
     SparseMatrix<T> FastTranspose()
     {
        SparseMatrix<T> sm;
        sm._colSize = _rowSize;
        sm._rowSize = _colSize;
        sm._invalid = _invalid;
        sm._array.resize(_array.size());

        int *RowCount = new int[_colSize];
        int *RowStart = new int[_colSize];
        memset(RowCount,0,sizeof(int)*_colSize);
        memset(RowStart,0,sizeof(int)*_colSize);

        int i = 0;
        while(i < _array.size())
        {
            ++RowCount[_array[i++]._col];
        }
        i = 1;
        while (i < _colSize) //O(n)
        {
            RowStart[i] = RowStart[i - 1] + RowCount[i - 1];
            ++i;
        }

        //执行快速转置
        int index = 0;
        while (index < _array.size()) //两次迭代 O(n)
        {

            Trituple<T> t(_array[index]._col, _array[index]._row,_array[index]._value);
            sm._array[RowStart[_array[index]._col]++] = t;
            ++index;
        }



        delete[] RowCount;
        delete[] RowStart;

        return sm;
     }

     ~SparseMatrix()
     {
         _array.clear();
     }
private:
    vector<Trituple<T>> _array;
    size_t _rowSize;
    size_t _colSize;
    T _invalid;
};
void test2()
{
 int arr[4][3] = { { 0, 1, 0},{ 0, 0, 0 },{ 2, 1, 0 },{3,3,2}};
 int i = 0;
 SparseMatrix sm((int *)arr,4,3,i);
			
			
				
			
			
				 sm.Print();
			
			
				
			
			
				 sm.Transpose().Print();
 sm.FastTranspose().Print();
			
			
				
			
			
				}

RowCount 转置后每一行有效值的个数，RowCount转置后每一行有效值在压缩矩阵开始的位置

此图关于RowCount是怎么存进去的，最开始全部memset成0了，然后遍历有效数组并把每个数加好就好了