稀疏矩阵的压缩存储和转置

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

2、稀疏矩阵的压缩存储：压缩存储值存储极少数的有效数据。  

    由于非零元素分布没有任何规律，所以在进行压缩存储的时侯需要存储无效值的同时还要存储有效元素在矩阵中的位置，即有效元素所在的行号和列号，也就是在存储某个元素比如aij的值的同时，还需要存储该元素所在的行号i和它的列号j，这样就构成了一个三元组(i,j,aij)的线性表。

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

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

具体实现如下：

#include<iostream>
using namespace std;
#include<assert.h>
#include<vector>//vector是一个能够存放任意类型的动态数组，能够增加和压缩数据，也认为是容器
template<class T>
struct Triple//三元组结构体
{
	int _row;
	int _col;
	T _value;//非法值/无效值
	Triple()
		:_row(0)
		, _col(0)
		, _value(0)
	{}
	Triple(int row, int col, T& value)
		:_row(row)
		, _col(col)
		, _value(value)
	{}
};
template<class T>
class SparseMatrix
{
public:
	SparseMatrix();
	SparseMatrix(T* array, int n, int m, const T& invalid);
	~SparseMatrix();
	void Display();
	SparseMatrix<T> Transpose();//转置
	SparseMatrix<T> FastTranspose();//快速转置
private:
	vector<Triple<T>> _array;
	size_t _rows;
	size_t _cols;
	T _invalid;
};
template<class T>
SparseMatrix<T>::SparseMatrix()
:_rows(0)
, _cols(0)
, _invalid(0)
{}
template<class T>
SparseMatrix<T>::~SparseMatrix()
{}
template<class T>
SparseMatrix<T>::SparseMatrix(T* array, int m, int n, const T& invalid)
:_rows(m)
, _cols(n)
, _invalid(invalid)
{//由于数组定义必须知道列数，则以行优先级存放稀疏矩阵,压缩存储值存储极少数的有效数据
	assert(array);
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (array[n*i + j] != invalid)
			{
				_array.push_back(Triple<T>(i, j, array[n*i + j]));//vector中push_back插入数据
			}
		}
	}
}
template<class T>
void SparseMatrix<T>::Display()
{
	//使用下标访问元素
	size_t indx = 0;
	for (size_t i = 0; i < _rows; i++)
	{
		for (size_t j = 0; j < _cols; j++)
		{//如果_array[indx]的行列等于i和j，且indx在范围内就打印其有效值，否则打印无效值0
			if (indx < _array.size() && _array[indx]._row == i && _array[indx]._col == j)
			{
				cout << _array[indx]._value << " ";
				indx++;
			}
			else
			{
				cout << _invalid << " ";
			}
		}
		cout << endl;
	}
	cout << endl;
	////使用迭代器访问所有有效元素
	//vector<Triple<T>>::iterator it;
	//for (it = _array.begin(); it != _array.end(); it++)
	//{
	//	cout << "row:" << (*it)._row << " col:" << (*it)._col << endl;
	//	cout << "_value:" << (*it)._value << endl;
	//}
	//cout << endl;
}
template<class T>
//时间复杂度为：O(_cols*有效数据个数)，空间复杂度：O(1)
SparseMatrix<T> SparseMatrix<T>::Transpose()//转置
{//原矩阵中元素以行优先存储，转置后的矩阵是以原矩阵的列优先存储的
	size_t indx;
	SparseMatrix<T> tmp;//新建一个稀疏矩阵存放交换后的行列和有效数据
	tmp._invalid = _invalid;
	tmp._rows = _cols;
	tmp._cols = _rows;
	tmp._array.reserve(_array.size());//reserve()扩容到size
	for (size_t i = 0; i < _cols; i++)//以列进行查找，进行行列交换
	{
		indx = 0;//将列数为i的有效元素进行行列交换
		while (indx < _array.size())
		{
			if (i == _array[indx]._col)
			{
				//Triple<T> point;
				//point._row = _array[indx]._col;
				//point._col = _array[indx]._row;
				//point._value = _array[indx]._value;
				//tmp._array.push_back(point);
				tmp._array.push_back(Triple<T>(i, _array[indx]._row, _array[indx]._value));
			}
			indx++;
		}
	}
	return tmp;
}
template<class T>
//时间复杂度为：O(_cols+有效数据个数)，空间复杂度：O(_cols)
SparseMatrix<T> SparseMatrix<T>::FastTranspose()//快速转置
{
	SparseMatrix<T> tmp;//新建一个稀疏矩阵存放交换后的行列和有效数据
	tmp._invalid = _invalid;
	tmp._rows = _cols;
	tmp._cols = _rows;
	tmp._array.resize(_array.size());//reserve()只扩容到，但不一定能用此空间，resize()开辟size个空间
	//rowCounts统计转置后的矩阵每一行的数据个数(原矩阵的每列的)
	//rowStarts统计转置后的矩阵每一行在压缩矩阵中存储的开始位置
	int* rowCounts = new int[_cols];
	int* rowStarts = new int[_cols];
	memset(rowCounts, 0, sizeof(int)*_cols);//memset()按字节初始化为某值（0）
	memset(rowStarts, 0, sizeof(int)*_cols);
	size_t indx = 0;
	while (indx < _array.size())
	{
		rowCounts[_array[indx]._col]++;//利用下标统计每列数据个数，2 0 2 0 2 
		indx++;
	}
	rowStarts[0] = 0;//记录开始位置
	for (size_t i = 1; i < _cols; i++)
	{//转置的矩阵每一行在压缩矩阵中存储的开始位置，0 2 2 4 4
		rowStarts[i] = rowCounts[i - 1] + rowStarts[i - 1];
	}
	indx = 0;
	while (indx < _array.size())//快速定位
	{//rowStarts存放转置后每一行的开始位置，rowStart不断更新同行数据位置,转置后同一行数据的位置不断++，故用&
		int& rowStart = rowStarts[_array[indx]._col];
		tmp._array[rowStart++] = Triple<T>(_array[indx]._col, _array[indx]._row, _array[indx]._value);
		indx++;
	}
	return tmp;
}

测试用例如下：

void Test2()
{
	int a[][5] = {
		{ 5, 0, 3, 0, 1 },
		{ 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0 },
		{ 6, 0, 4, 0, 2 },
		{ 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0 },
	};
	SparseMatrix<int> s1((int*)a, 6, 5, 0);
	s1.Display();
	SparseMatrix<int> s2;
	s2 = s1.Transpose();
	s2.Display();
	SparseMatrix<int> s3;
	s3 = s1.FastTranspose();
	s3.Display();
}

对称矩阵及对称矩阵的压缩存储

设一个N*M的方阵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()
		:_a(NULL)
		, _size(0)
	{}
	SymmetricMatrix(T* a, const size_t size)
		:_a(new T[size*(size+1)/2])
		, _size(size*(size+1)/2)
	{
		assert(a);
		//size_t indx = 0;
		for (size_t i = 0; i < size; i++)
		{
			for (size_t j = 0; j < size; j++)
			{
				if (i >= j)//if (i >= j && indx < _size)
				{
					//方法一：_a[indx] = a[i*size + j];indx++;
					//方法二：运用下三角矩阵的对称矩阵和压缩存储的对应关系：
					//下三角存储i>=j,  SymmetricMatrix[i][j] == Array[i*(i+1)/2+j]
					_a[i*(i + 1) / 2 + j] = a[i*size + j];
				}
			}
		}
	}
	void Display()
	{
		if (_a)
		{
			for (size_t indx = 0; indx < _size; indx++)
			{
				cout << _a[indx] << " ";
			}
			cout << "\nsize = " << _size << endl;
		}
	}
	~SymmetricMatrix()
	{
		if (_a)
		{
			delete[] _a;
		}
	}
private:
	T* _a;
	size_t _size;
};
void Test1()
{
	int a[][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> s1((int*)a, 5);
	s1.Display();
}