對稱矩陣及稀疏矩陣的壓縮

對稱矩陣

    設一個N*N的方陣A，A中的任意元素A[i][j]，當且僅當A[i][j]=A[j][i],則矩陣A是對稱矩陣，以對角線分隔，分為上三角和下三角

    壓縮矩陣存儲對稱矩陣時只需要存儲其上三角或者下三角的數據，即最多存儲n(n+1)/2個數據,對應關于為：i>j,symmetricMatrix[i][j]=A[i*(i+1)/2+j]

  代碼實現：

template<class T>
class SymmetricMatrix
{
public:
	SymmetricMatrix(T*a,size_t num)
		:_a(new T[num*(num+1)/2])//開辟一塊壓縮矩陣的空間，n*（n+1）/2
		,_size(num*(num+1)/2)
		,_n(num)	
	{
		for (size_t i = 0; i < _n; i++)
		{
			for (size_t j = 0; j <= i; j++)
			{
				
				_a[i*(i+1)/2+j] = a[i*num + j];//把矩陣中的元素存入壓縮矩陣中
				
			}
		}
	}
	~SymmetricMatrix()
	{
		if (_a)
		{
			delete[]_a;
			/*
			_a=NULL;
			_size=0;
			_n=0;
			*/
		}
	}
	void Display()
	{
		for (size_t i = 0; i < _n; i++)
		{
			for (size_t j = 0; j < _n; j++)
			{
			/*
			當i>=j打印下矩陣，當i<j，交換i,j打印上矩陣
			*/
			
				if (i < j)
					Access(i, j);
				cout << _a[i*(i + 1) / 2 + j] << " ";
				
				if(i< j)
				    Access(i, j);
			/*
			if(i>=j)
			cout<<_a[i*(i + 1) / 2 + j] << " ";
			else
			cout<<_a[j*(j + 1) / 2 + i] << " ";
			*/
			}
			cout << endl;
		}
		cout << endl;
	}
protected:
	void Access(size_t i, size_t j)
	{
		if (i < j)
		{
			swap(i, j);
		}
	}
private:
	T* _a;//數組
	size_t _size;//壓縮矩陣大小
	size_t _n;//矩陣為N*N
};

void test()
{

	int a[][4] =
	{
		0, 1, 2, 3,
		1, 0, 5, 6,
		2, 5, 0, 8,
		3, 6, 8, 0
	};
	size_t lenth = sizeof(a)/sizeof(a[0]);
	SymmetricMatrix<int> Array((int*)a,lenth);
	Array.Display();
}
int main()
{
	test();
}

稀疏矩陣

    M*N的矩陣，矩陣中有效值的個數遠遠小于無效值的個數，這些數據的分布，沒有規律    

    壓縮存儲只需要存儲極少的有效數據，用三元組{row，col，value}存儲，三元組按原矩陣中的位置，以行優先級先后順序依次存放。

#include<iostream>
#include<vector>

using namespace std;

template<class T>
struct Triple//三元組
{
	T _value;//值
	size_t _row;//行
	size_t _col;//列

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

template<class T>
class SparseMatrix
{
public:
	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*_colSize + j] != _invalid)
				{
					_a.push_back(Triple<T>(a[i*_colSize + j],i,j));
					/*
					壓縮矩陣，循環找到矩陣中不為_invalid的元素，存儲到順序表中
					*/
				}
			}
		}
	}
	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;
	}
	
private:
	vector<Triple<T>> _a;
	size_t _rowSize;
	size_t _colSize;
	T _invalid;
};
void test()
{
	int a[][5] =
	{
		1, 0, 3, 0, 5,
		0, 0, 0, 0, 0,
		0, 0, 0, 0, 0,
		2, 0, 4, 0, 6,
		0, 0, 0, 0, 0,
		0, 0, 0, 0, 0
	};
	SparseMatrix<int> Array((int*)a,6,5,0);
	Array.Display();

}
int main()
{
	test();
}