矩阵-----对称矩阵及其压缩存储&&稀疏矩阵

什么是对称矩阵（SymmetricMatrix）？

对称对称-------看

设一个N*N的方阵A，A中任意元素Aij，当且仅当Aij == Aji(0 <= i <= N-1 && 0 <= j <= N-1)，则矩阵A是对称矩阵。以矩阵的对角线为分隔，分为上三角和下三角。

压缩存就是矩阵存储时只需要存储上三角/下三角的数据，所以最多存储n(n+1)/2个数据。

对称矩阵和压缩存储的对应关系：下三角存储i>=j,  SymmetricMatrix[i][j] == Array[i*(i+1)/2+j]

那么，我们该如何存储呢？

按照一元数组的方法，存储下三角的元素即可。

template<class T>
class SymmetricMatrix
{
public:
	SymmetricMatrix(T* a, size_t size, size_t n)
		:_data(new T[n*(n + 1) / 2])    //开辟好数组一半大小的空间
		, _size(size)
		, _n(n)
	{
		size_t index = 0;
		for (size_t i = 0; i < _n; i++)
		{
			for (size_t j = 0; j < _n; j++)
			{
				if (i >= j)                    //下三角元素
				{
					_data[index++] = a[i*n + j];
				}
				else
				{
					break;
				}
			}
		}
	}
public:
	void Display()
	{
		size_t index = 0;
		for (size_t i = 0; i < _n; i++)
		{
			for (size_t j = 0; j < _n; j++)
			{
				if (i >= j)
				{
					cout << _data[i*(i + 1) / 2 + j]<<" ";
				}
				else   //上三角位置
				{
					cout << _data[j*(j + 1) / 2 + i]<<" ";  //交换行列坐标
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	//获取某行某列元素
	T& Access(size_t i, size_t j)
	{
		if (i < j)
		{
			swap(i, j);
		}
		return _data[i*(i + 1) / 2 + j];
	}
protected:
	T* _data;
	size_t _size;
	size_t _n;
};

什么又是稀疏矩阵呢？

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

首先构建三元组（这里的每一个三元组就是矩阵中的一个元素）

template<class T>
struct Triple
{
	T _value;
	size_t _col;
	size_t _row;
	Triple(const T& value = T(), size_t row = 0, size_t col = 0)
		:_value(value)
		, _row(row)
		,_col(col)
	{}
};

再存储有效值。

创建一个类，在构造函数中我们实现有效值的存储

SparseMatrix(T* a, size_t m, size_t n, const T& invalid)
		:_rowSize(m)
		, _colSize(n)
		, _invalid(invalid)
	{
		for (size_t i = 0; i < _rowSize; i++)
		{
			for (size_t j = 0; j < _colSize; j++)
			{
				if (a[i*n + j] != _invalid)
				{
					_a.push_back(Triple<T>(a[i*n + j], i, j));
				}
			}
		}
	}
	SparseMatrix()
		:_rowSize(0)
		, _colSize(0)
		, _invalid(0)
	{}

这里还有一个矩阵转置。何为矩阵转置呢？

*矩阵转置

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

SparseMatrix<T> Transport()
	{
		SparseMatrix<T> tmp;
		tmp._colSize = _rowSize;  //交换行列大小
		tmp._rowSize = _colSize;
		tmp._invalid = _invalid;
		
		
		for (size_t i = 0; i < _colSize; i++)    
		{
			size_t index = 0;
			while (index < _a.size())
			{
				if (_a[index]._col == i)    //按照列在存储的三元组中依次寻找.
				{                           //找到列为0，压入新的顺序表中，继续找.....
					Triple<T> t;
					t._col = _a[index]._row;
					t._row = _a[index]._col;
					t._value = _a[index]._value;
					tmp._a.push_back(t);
				}
				index++;
			}

		}
		return tmp;
	}

你们有没有发现普通转置的效率太低，时间复杂度太高？它的时间复杂度为O（列数*有效数据的行数),那我接下来就给大家介绍快速转置。

快速转置，只需要遍历一次存储的有效数据。这个怎么做到呢？

我们需要得出转置后每一行有效值的个数和每一行第一个有效值在压缩矩阵中的起始位置。

即

RowCounts = { 2 , 0 , 2 , 0 , 2 } ; 

RowStart = { 0 , 2 , 2 , 4 , 4 } ;

我们可以看出 RowStrat[0] 总是恒为 0，那很容易就可以发现

 RowStart[i] = RowStart[i - 1] + RowCounts[i - 1];

再看代码

SparseMatrix<T> FastTransport()
	{
		SparseMatrix<T> tmp;
		tmp._colSize = _rowSize;
		tmp._rowSize = _colSize;
		tmp._invalid = _invalid;
		tmp._a.resize(_a.size());

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

		//统计个数
		size_t index = 0;
		while (index < _a.size())
		{
			RowCounts[_a[index]._col]++;
			index++;
		}
		RowStart[0] = 0;
		for (size_t i = 1; i < _colSize; i++)
		{
			RowStart[i] = RowStart[i - 1] + RowCounts[i - 1];
		}

		//定位位置
		index = 0;
		while (index < _a.size())
		{
			int rowindex = _a[index]._col;
			int& start = RowStart[rowindex];
			Triple<T> t;
			t._col = _a[index]._row;
			t._row = _a[index]._col;
			t._value = _a[index]._value;
			tmp._a[start] = t;
			start++;
			index++;
		}
		delete[] RowCounts;
		delete[] RowStart;

		return tmp;
	}

接下来我们继续使用行优先的原则将压缩矩阵打印出来

void Display()
	{
		size_t index = 0;
		for (size_t i = 0; i < _rowSize; i++)
		{
			for (size_t j = 0; j < _colSize; j++)
			{
				if (index < _a.size()&&_a[index]._row == i&&_a[index]._col == j)
				{
					cout << _a[index]._value << " ";
					index++;
				}
				else
				{
					cout << _invalid << " ";
				}
			}
			cout << endl;
		}
		cout << endl;
	}

最后再补上我们类的成员变量

protected:
	vector<Triple<T>> _a;
	size_t _rowSize;
	size_t _colSize;
	T _invalid;

这就是我们的快速转置了。小伙伴们好好看哦。我会继续努力哒~