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

#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();
}

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();
}