对称矩阵及稀疏矩阵浅谈

1.对称矩阵

特点：
关于对角线对称，Aij == Aji。
下面实现：
①对称矩阵的压缩存储
②对称矩阵的访问
③对称矩阵的还原

实现代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
//对称矩阵的压缩存储
template<class T>
class SymmetricMatrix
{
public:
    SymmetricMatrix(T* array, size_t N)
        :_N(N)
        ,_a(NULL)
    {
        _a = new T[(N * (N + 1))>> 1];
        for (size_t i = 0; i < N; ++i)
        {
            for (size_t j = 0; j < N; ++j)
            {
                if (i >= j)//表明是下三角数据时
                {
                    _a[(i * (i + 1))>>1 + j] = array[i * N + j];
                }
                else
                {
                    break;
                }
            }
        }
    }

    T& Access(size_t x, size_t y)
    {
        if (x < y)//如果访问上三角元素
        {
            swap(x, y);
        }
        return _a[(x * (x + 1)) >> 1 + y];
    }

    void DisPlay()
    {
        for (size_t i = 0; i < _N; ++i)
        {
            for (size_t j = 0; j < _N; ++j)
            {
                if (i >= j)//访问下三角元素
                {
                    cout<<Access(i, j)<<" ";
                }
                else
                {
                    cout << Access(j, i) << " ";
                }
            }
            cout << endl;
        }
        cout << endl;
    }

    ~SymmetricMatrix()
    {
        if (_a)
        {
            delete[] _a;
            _a = NULL;
        }
    }

private:
    T* _a;
    size_t _N;
};

测试代码如下：

void Test()
{
    int a[5][5] =
    {
        { 0, 1, 2, 3, 4 },
        { 1, 0, 1, 2, 3 },
        { 2, 1, 0, 1, 2 },
        { 3, 2, 1, 0, 1 },
        { 4, 3, 2, 1, 0 },
    };
    SymmetricMatrix<int> sm((int*)a, 5);
    cout << sm.Access(0, 3) << endl;
    cout << sm.Access(3, 0) << endl;
    sm.DisPlay();
}

int main()
{
    Test();
    return 0;
}

2.稀疏矩阵：

(1)稀疏矩阵的压缩存储：

所谓稀疏矩阵的压缩存储，其实就是将稀疏矩阵中的有效元素保存起来，但由于稀疏矩阵中有效元素的分布没有规律可寻，所以需要使用一个三元组来保存其位置（row、col）以及有效值。—>三元组最好使用结构体来存储。

因为不知道矩阵中究竟有多少个有效元素（即就是不知需要多少个结构体），那么就可以使用vector（动态增长型）来保存有效元素。

//三元组--->存储有效元素的位置及值
    template<class T>
    struct Trituple
    {
        Trituple(size_t row, size_t col, const T& data)
        :_row(row)
        , _col(col)
        , _data(data)
        {}

        size_t _row;
        size_t _col;
        T _data;
    };

//稀疏矩阵的压缩存储
    SparseMatrix(T* array, int row, int col,const T& invalid)
        :_row(row)
        , _col(col)
        ,_invalid(invalid)
    {
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                if (array[i * col + j] != invalid)
                {
                    _sm.push_back(Trituple<T>(i, j, array[i * col + j]));
                }
            }
        }
    }

(2)稀疏矩阵的转置：

稀疏矩阵的转置过程如下：

实现代码如下：

   // 稀疏矩阵的转置
   //时间复杂度：(稀疏矩阵的列*稀疏矩阵中有效元素的个数)
    SparseMatrix<T> Transprot()
    {
        SparseMatrix<T> sm;
        sm._row = _col;
        sm._col = _row;

        for (size_t index = 0; index < _col; ++index)
        {
            vector<Trituple<T> >::iterator it = _sm.begin();
            while (it != _sm.end())
            {
                if ( it->_col == index)
                {
                    sm._sm.push_back(Trituple<T>(it->_col, it->_row, it->_data));
                }
                it++;
            }
        }
        return sm;
    }

3.稀疏矩阵的快速转置：

稀疏矩阵的转置的时间复杂度：(稀疏矩阵的列N*稀疏矩阵中有效元素的个数)—-》时间复杂度较大，所以引出了快速转置

稀疏矩阵的快速转置的时间复杂度（2*有效元素的个数 + 稀疏矩阵的列）

快速转置的思想如下：

代码实现：

//快速转置
SparseMatrix<T,N,M> FastTransport(const size_t m,const size_t n)
    {
    SparseMatrix < T, N, M> sm;//转置后的压缩矩阵
        sm._row = _col;
        sm._col = _row;
        sm._v.resize(_v.size());//为了保证后面可以直接访问vector中的数据（调用operator[]）
        //保存转置前的每列有效元素的个数,即就是转置后每行有效元素的个数
        int rows[N] = {0};
        size_t index = 0;
        while (index < _v.size())
        {
            rows[_v[index]._col]++;
            index++;
        }
        //保存转置后的每行第一个有效元素在转置后的三元组数组中的下标
        int starts[N] = { 0 };
        for (size_t i = 1; i < _col; ++i)
        {
            starts[i] = starts[i - 1] + rows[i - 1];
        }

        for (size_t i = 0; i < _v.size(); ++i)
        {
            int row = _v[i]._col;//转置前列的下标即是转置后行的下标
            Triple<T> t;
            t._value = _v[i]._value;
            t._col = _v[i]._row;
            t._row = _v[i]._col;
            sm._v[starts[row]] = t;
            starts[row]++;//每次需要更新starts数组中的数据
        }
        return sm;
    }

全部代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<vector>

//三元组
template<class T>
struct Triple
{
    Triple()
    {}
    Triple(T& data, size_t row, size_t col)
        :_value(data)
        , _row(row)
        , _col(col)
    {}
    T _value;
    size_t _row;
    size_t _col;
};

template<class T,size_t M,size_t N>
class SparseMatrix
{
public:
    SparseMatrix()
    {}

    //稀疏矩阵的压缩存储
    SparseMatrix(T* array, const T& invalid)
        :_invalid(invalid)
        , _row(M)
        , _col(N)
    {
        for (size_t i = 0; i < _row; ++i)
        {
            for (size_t j = 0; j < _col; ++j)
            {
                if (array[i * N + j] != invalid)
                {
                    Triple<T> t;
                    t._value = array[i * N + j];
                    t._row = i;
                    t._col = j;
                    _v.push_back(t);
                }
            }
        }
    }

    //稀疏矩阵的还原
    void Display()
    {
        int index = 0;
        for (size_t i = 0; i < _row; ++i)
        {
            for (size_t j = 0; j < _col; ++j)
            {
                if (index < _v.size() && _v[index]._row == i && _v[index]._col == j)
                {
                    cout << _v[index]._value << " ";
                    index++;
                }
                else
                {
                    cout << _invalid << " ";
                }
            }
            cout << endl;
        }
        cout << endl;
    }

    //稀疏矩阵的转置
    SparseMatrix<T,N,M> Transport()
    {
        SparseMatrix<T,N,M> _sm;//转置后的
        _sm._invalid = _invalid;
        _sm._row = _col;
        _sm._col = _row;
        //按列查找（转置前的列优先即就是转置后的行优先）
        for (size_t i = 0; i < _col; ++i)
        {
            size_t index = 0;
            while (index < _v.size())
            {
                if (_v[index]._col == i)
                {
                    Triple<T> t;
                    t._value = _v[index]._value;
                    t._row = _v[index]._col;
                    t._col = _v[index]._row;
                    _sm._v.push_back(t);
                }
                index++;
            }
        }
        return _sm;
    }

    template<class T, size_t N, size_t M>
    friend class SparseMatrix;

//快速转置
SparseMatrix<T,N,M> FastTransport(const size_t m,const size_t n)
    {
    SparseMatrix < T, N, M> _sm;//转置后的压缩矩阵
        _sm._row = _col;
        _sm._col = _row;
        _sm._v.resize(_v.size());//为了保证后面可以直接访问vector中的数据（使用operator[]）
        //保存转置前的每列有效元素的个数,即就是转置后每行有效元素的个数
        int rows[N] = {0};
        size_t index = 0;
        while (index < _v.size())
        {
            rows[_v[index]._col]++;
            index++;
        }
        //保存转置后的每行第一个有效元素在转置后的三元组数组中的下标
        int starts[N] = { 0 };
        for (size_t i = 1; i < _col; ++i)
        {
            starts[i] = starts[i - 1] + rows[i - 1];
        }

        for (size_t i = 0; i < _v.size(); ++i)
        {
            int row = _v[i]._col;//转置前列的下标即是转置后行的下标
            Triple<T> t;
            t._value = _v[i]._value;
            t._col = _v[i]._row;
            t._row = _v[i]._col;
            _sm._v[starts[row]] = t;
            starts[row]++;//每次需要更新starts数组中的数据
        }
        return _sm;
    }

private:
    vector<Triple<T> >  _v;
    T _invalid;
    size_t _row;
    size_t _col;
};

测试代码如下：

void Test()
{
    int array[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 },
    };
    SparseMatrix<int,6,5> sm((int*)array, 0);
    sm.Display();
    SparseMatrix<int,5,6> sm2 = sm.FastTransport(5,6);
    sm2.Display();
}

int main()
{
    Test();
    return 0;
}

由于能力有限，又是刚开始学习数据结构，难免会有思考的不正确或是不完善的地方，欢迎大家批评指正。。。