稀疏矩陣的壓縮存儲和轉置

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