对称矩阵、稀疏矩阵及矩阵的逆置与加法

                                                      矩阵之对称矩阵、稀疏矩阵逆置与加法

一、对称矩阵及压缩存储

由于对称矩阵对角线上下相同，因此我们可以采取压缩存储。

我们先了解一下压缩存储，对称矩阵存储时只需要存储上三角或下三角的数据，所以最多存储n*(n+1)/2个数据。

我们就知道了我们需要空间的大小。

代码如下：

#include<iostream>
using namespace std;
#include<vector>

//对称矩阵
template<class T,size_t N=5>
class SymmetricMatrix
{
public:
	SymmetricMatrix(T(&arr)[N][N])
		:_N(N)
	{
		int index = 0;
		_arr.resize((1 + N)*N >> 1);
		for (size_t i = 0; i < _N; i++)
		{
			for (size_t j = 0; j <= i; j++)
			{
				_arr[index++] = arr[i][j];
			}
		}
	}
	T& Acess(int row, int col)
	{
		if (row < col)
			swap(row, col);
		return _arr[row*(row + 1) / 2 + col];
	}
	void Print()
	{
		for (size_t i = 0; i < N; i++)
		{
			for (size_t j = 0; j < N; j++)
			{
				cout << Acess(i, j) << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
private:
	vector<T> _arr;
	size_t _N;
};

int main()
{
	int a[5][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> s(a);
	cout << s.Acess(2, 3) << endl;
	cout << s.Acess(3, 2) << endl;

	s.Acess(3, 2);
	s.Print();

	system("pause");
	return 0;
}

测试结果如下：

二、稀疏矩阵

1、稀疏矩阵的压缩存储和还原

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

所以可以采用只存储非零元素（有效值）的方法来进行压缩存储。在进行压缩存储的时侯还要存储非零元素在矩阵中的位置。所以我们要使用

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

三元组如下：

template<class T>
struct Trituple
{
	size_t _row;
	size_t _col;
	T _value;

	Trituple(int row,int col,int data)
		:_row(row)
		, _col(col)
		, _value(data)
	{}
};

我们需要一个容器存储每个节点的内容，代码如下：

template<class T,int M,int N>
class SparseMatrix
{
public:
	SparseMatrix(int row,int col,T inValid)                  
		:_row(row)
		, _col(col)
		, _inValid(inValid)
	{}
	SparseMatrix(T arr[M][N], T inValid)                 //存储稀疏矩阵
		:_row(M)
		, _col(N)
		, _inValid(inValid)
	{
		for (size_t i = 0; i < _row; i++)
		{
			for (size_t j = 0; j < _col; j++)
			{
				if (arr[i][j] != inValid)
				{
					Trituple<T> t(i, j, arr[i][j]);
					_v.push_back(t);
				}
			}
		}
	}
	//打印压缩矩阵
	void display()
	{
		for (size_t i = 0; i < _v.size(); i++)
		{
			cout << _v[i]._value << " ";
		}
	}
	//打印
	void Print()
	{
		size_t index = 0;
		for (size_t i = 0; i < _row; i++)
		{
			for (size_t j = 0; j < _col; j++)
			{
				if (index < _v.size())
				{
					if (_v[index]._row == i&&_v[index]._col == j)
					{
						cout << _v[index++]._value << " ";
					}
					else
					{
						cout << _inValid << " ";
					}
				}
				else
					cout << _inValid << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
	//重载输出运算符
	friend ostream& operator<<(ostream& cout, SparseMatrix<T, M, N>& Matrix)
	{
		size_t index = 0;
		for (size_t i = 0; i < Matrix._row; i++)
		{
			for (size_t j = 0; j < Matrix._col; j++)
			{
				if (index < Matrix._v.size())
				{
					if (Matrix._v[index]._row == i&&Matrix._v[index]._col == j)
					{
						cout << Matrix._v[index++]._value << " ";
					}
					else
					{
						cout << Matrix._inValid << " ";
					}
				}
				else
					cout << Matrix._inValid << " ";
			}
			cout << endl;
		}
		return cout;
	}
private:
	vector<Trituple<T>> _v;        //保存有效节点
	size_t _row;
	size_t _col;
	T _inValid;                   //无效值
};

为了测试方便我加了一个display()函数，是为了检测压缩存储是否正确，打印函数和输出运算符重载都是输出稀疏矩阵。

测试：

int main()
{
	int array[5][5] = {
	{ 0, 0, 1, 0, 2 },
	{ 1, 0, 0, 0, 8 },
	{ 0, 0, 0, 1, 3 },
	{ 1, 0, 0, 0, 0 },
	{ 0, 0, 0, 3, 0 } };

	SparseMatrix<int,5,5> sm(array, 0);
	sm.display();

	sm.Print();
	cout << sm << endl;
	system("pause");
	return 0;
}

结果以下，有效元素以及整个稀疏矩阵。

三、矩阵的逆置

以上面稀疏矩阵为例，逆置就是将array[i][j]和array[j][i]的值交换。若我们直接将有效节点中的行列交换，输出的话，能得到我们想要的结果吗？

函数如下：

//矩阵逆置
	void ReverseMatrix()
	{
		for (size_t index = 0; index < _v.size();index++)
		{
			swap(_v[index]._row, _v[index]._col);
		}
		swap(_row, _col);
	}

运行结果：

并没有成功，为什么呢？

因为首次存储时是按照行优先的存储顺序，若交换完依然按照行优先顺序进行输出，则不能全部输出。

我们可以将交换后的有效元素按照行的大小排序，再输出，如下（冒泡排序）：

//矩阵逆置
	void ReverseMatrix()
	{
		for (size_t index = 0; index < _v.size();index++)
		{
			swap(_v[index]._row, _v[index]._col);
		}
		swap(_row, _col);

		for (size_t i = 0; i < _v.size(); i++)
		{
			for (size_t j = 0; j < _v.size() - i - 1; j++)
			{
				if (_v[j]._row>_v[j + 1]._row)
					swap(_v[j], _v[j + 1]);
			}
		}
	}

运行结果：

四、矩阵的加法

两个矩阵相加，即行列相对应的数相加。因此两个矩阵必须行和列分别相等。

因为我们只存储了有效元素，我们可以通过算出各个元素在原矩阵的偏移量，遍历两个矩阵，偏移量相等时相加；第一个矩阵元素偏移量小时，证明第二个矩阵没有对应元素。反之亦然。

代码如下：

SparseMatrix& operator+(SparseMatrix& Matrix)
	{
		//行列分别相等
		if (_row != Matrix._row || _col != Matrix._col)
		{
			cout << "两个矩阵不能相加" << endl;
			exit(EXIT_FAILURE);
		}

		SparseMatrix* ret = new SparseMatrix(_row, _col, _inValid);
		size_t leftIndex = 0, rightIndex = 0;
		size_t addL = 0, addR = 0;
		while (leftIndex < _v.size() && rightIndex < Matrix._v.size())
		{
			//在原矩阵中的偏移量
			addL = _v[leftIndex]._row*_col + _v[leftIndex]._col;
			addR = Matrix._v[rightIndex]._row*_col + Matrix._v[rightIndex]._col;
			if (addL < addR)
			{
				ret->_v.push_back(_v[leftIndex]);
				leftIndex++;
			}
			else if (addL > addR)
			{
				ret->_v.push_back(Matrix._v[rightIndex]);
				rightIndex++;
			}
			else
			{
				Trituple<T> t(_v[leftIndex]._row, _v[leftIndex]._col,
					_v[leftIndex]._value + Matrix._v[rightIndex]._value);
				ret->_v.push_back(t);
				leftIndex++;
				rightIndex++;
			}
		}
		while (leftIndex < _v.size())   //第二个已经无有效元素
		{
			ret->_v.push_back(_v[leftIndex]);
			leftIndex++;
		}
		while (rightIndex < _v.size())   //第一个已经无有效元素
		{
			ret->_v.push_back(Matrix._v[rightIndex]);
			rightIndex++;
		}
		return *ret;
	}

测试结果如下：