对称矩阵和稀疏矩阵的相关问题

关于概念性的问题这里就不多介绍了，直接说相关的算法了。

核心内容:

1.对称矩阵的压缩存储

2.稀疏矩阵的压缩存储

3.稀疏矩阵的转置

4.稀疏矩阵的加法

一：①对称矩阵的压缩存储②返回指定位置元素③还原对称矩阵（使用压缩储存的元素打印对称矩阵）

①压缩存储

因为对称矩阵的特性，我们在储存矩阵的时候可以不需要将数组中的所有元素都保存下来，而是只需要保存其中的上三角或者下三角中的元素就可以了，因为上下三角中的元素是一样的而且是对称的，这就是对称矩阵的压缩储存。

具体该怎么存呢？（这里存储下三角来举例）

1.首先我们将下三角中的内容应该存储在一个一维数组中，这个数组的大小应该是下三角元素的总个数（（1+5）*5/2），就可以得出。

2.然后就是用两个for循环（外层控制遍历行数，内层控制遍历元素的个数）遍历下三角的所有元素，并且储存到你开辟的数组中去。下面给出代码解析

核心代码：

{
		size_t index = 0;
		//储存下三角的元素
		for (size_t i = 0; i < _N; i++)//行
		{
			for (size_t j = 0; j < _N; j++)/
			{
				if (i >= j)//控制读取原始数据的行数
				{
					_arr[index++] = arr[i*_N + j];
				}
				else
				{
					break;
				}
			}
		}
	}

代码分析：

②还原对称矩阵

只需根据存储下三角的数组中的元素对称打印出来上三角的就好了

代码：

void Display()
	{
		for (size_t i = 0; i < _N; i++)
		{
			for (size_t j = 0; j < _N; j++)
			{
				if (i>=j )
				{
					cout << _arr[i*(i + 1) / 2 + j]<<" ";//打印下三角部分，不满足了在打印上三角部分
				}
				else
				{
					cout << _arr[j*(j + 1) / 2 + i]<<" ";//打印上三角，按照与下三角对称打印
				}
			}
			cout << endl;
		}
		cout << endl;
	}

代码分析：

③返回指定位置的元素这个只需要首先判断是上三角还是下三角 中的坐标，如果是上三角的坐标，只需要将（x,y）的 坐标交换就可以了，否则直接返回指定位置的下三角元素。

下面给出全部代码和测试结果

template<class T>
class SymmetricMatrix
{
private:
	T *_arr;
	size_t _N;
public:
	SymmetricMatrix(T *arr, size_t N)
		:_arr(new T[N*(N + 1) / 2])
		, _N(N)
	{
		size_t index = 0;
		//储存下三角的元素
		for (size_t i = 0; i < _N; i++)//行
		{
			for (size_t j = 0; j < _N; j++)
			{
				if (i >= j)//控制读取原始数据的行数
				{
					_arr[index++] = arr[i*_N + j];
				}
				else
				{
					break;
				}
			}
		}
	}
	T& Access(size_t i, size_t j)//获取指定位置元素
	{
		if (i > j)//表示就是上三角的元素
		{
			swap(i, j);//交换i和j的值
		}
		return _arr[i*(i+1)/2+j];//上三角的列就是下三角的行
	}
	void Display()
	{
		for (size_t i = 0; i < _N; i++)
		{
			for (size_t j = 0; j < _N; j++)
			{
				if (i>=j )
				{
					cout << _arr[i*(i + 1) / 2 + j]<<" ";//打印下三角部分，不满足了在打印上三角部分
				}
				else
				{
					cout << _arr[j*(j + 1) / 2 + i]<<" ";//打印上三角，按照与下三角对称打印
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	~SymmetricMatrix()
	{
		delete[] _arr;
		_arr = NULL;
	}
};
int main()
{
	int arr[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> tri((int*)arr, 5);//强转为一维数组，这样传过去的数组就可以当成以为数组来访问了
	cout << "(4,2)的元素是" << tri.Access(4, 2) << endl;
	tri.Display();
	system("pause");
	return 0;
}

其实对称矩阵的核心就是会用（首项加末项*项数）/2来计算指定的元素位置

二.稀疏矩阵

①稀疏矩阵的压缩存储和打印稀疏矩阵

因为稀疏矩阵中的有效个元素的分布是没有规律的，所以就建立一个结构体将每个有效元素的坐标和值存下来，这个结构体就称为三元组，然后把每个有效元素按照行优先的顺序依次存在自己的三元组中，然后把这些三元组放进vector中储存，在打印稀疏矩阵的时候遍历矩阵，如果数值等于vector中的三元组中的有效元素，则打印这个有效元素，然后vector向后偏移，否则打印无效值。

代码如下：

三元组结构体代码：

template<class T>
struct Triple//三元组
{
	size_t x,y;
	T data;
	Triple(size_t _x, size_t _y, T _data)
		:x(_x)
		, y(_y)
		, data(_data)
	{}
	Triple(){}
};

稀疏矩阵压缩储存储存算法代码：

template<class T>
class Trituple
{
private:
	vector<Triple<T>> _a;
	T _invalue;//无效元素的个数
	size_t _row;//行
	size_t _col;
public:
	Trituple(T *a, size_t row, size_t col, T invalue)
		:_row(row)
		, _col(col)
		, _invalue(invalue)
	{
		for (size_t i = 0; i < row; i++)
		{
			for (size_t j = 0; j < col; j++)
			{
				if ((a[i*col + j]) != _invalue)//不等于无效元素的时候王进存，因为将二维数组强转为1为数组了所以用i*col来遍历元素
				{
					Triple<T> tri(i, j, a[i*col + j]);//创建三元组
					_a.push_back(tri);//存进vector中
				}
			}
		}
	}

叙述矩阵的打印，正如上面我所说的，判断等于有效数就打印输出，不相等打印无效值

void Display()
	{
		size_t index = 0;
		for (size_t i = 0; i < _row; i++)
		{
			for (size_t j = 0; j < _col; j++)
			{
				if (index != _a.size()&& i == _a[index].x&&j == _a[index].y)//三元组中存储了下标所以只需要判断坐标是否相等
				{
					cout << _a[index++].data<<" ";//输出以后vector向后偏移判断下一个有效值
				}
				else
				{
					cout << _invalue << " ";//否则输出无效值
				}
			}
			cout << endl;
		}
	}

上面两个都很简单这里就不多说了，下面来看稀疏矩阵的逆置

1.普通的逆置算法

通过遍历原矩阵的三元组表得出逆置后元素存储的三元组表，所以可以根据原矩阵的每个元素的y坐标作为判断依据，y=0的就是逆置后的三元组表中的第0行的元素，y=1的就是第二行，根据行优先的顺序遍历最后得到的就是逆置后的三元组表

代码如下：

void Transpostion()
	{
		size_t n = _a.size();
		vector<Triple<T>> _tmp;//定义转置后的Vector
		size_t count = 0;
		for (size_t i = 0; i < _col; i++)
		{
			for (size_t j = 0; j < n; j++)
			{
				if (_a[j].y == i)//如果列下标符合，则将其压入vector，i表示列
				{
					_tmp.push_back(_a[j]);
					swap(_tmp[count].y, _tmp[count].x);//将压进去的元素的（x,y）互换
					count++;//为了交换而设计的，不然的话没有办法交换
				}
			}
		}
		for (size_t i = 0; i < n; i++)//方便打印而写的代码
		{
			_a[i] = _tmp[i];
		}
		swap(_col, _row);//整体矩阵的行列互换
	}

这种方法的效率太低了，因为要遍历列数次原来矩阵的三元组表。所以看第二种快速转置的方法

②快速转置（难点）

这种方法只需要我们遍历一遍原矩阵的三元组表，就可以得到转置后的三元组表。

准备需要两个数组，第一个数组用来存储原矩阵中每列有效元素的个数

                                   第二个数组储存原三元表中每列第一个有效元素在新三元表的位置

然后就开始遍历开始放了，这么一说是不是一脸蒙逼，先给出代码，看不懂在看代码分析

	void Transpostion2()
	{
		vector<Triple<int>> _tmp2;//用来存储逆置后的顺序
		//都是用来表示列的相关内容的
		 size_t n = _a.size();//原矩阵的三元组个数
		 _tmp2.resize(n);//开辟矩阵三元组的个数
		size_t num[5] = { 0 };//表示每列中的有效元素的个数
		size_t pos[5] = { 0 };//表示每列中第一个有效元素在_tmp2的位置
		//填补num,遍历有效元素就可以了
		for (size_t i = 0; i < n; i++)//因为是遍历远原来的vector所以用n
			num[_a[i].y]++;//能表示到哪个y坐标几次则表示那个y列有几个元素
		pos[0] = 0;//第一个列元素的位置在新表位置肯定是0，毋庸置疑
		for (size_t j = 1; j < 5; j++)//填补pos,每个位置对应一列
		{
			pos[j] =pos[j - 1] + num[j - 1];//第二列的首元素位置必然等于第一列第一个元素位置+元素个数
		}
		for (size_t k = 0; k < n; k++)//遍历一遍建成逆置后的tmp2
		{
			_tmp2[pos[_a[k].y]] = _a[k];//左边直接表示新表的指定的位置
			swap(_tmp2[pos[_a[k].y]].y, _tmp2[pos[_a[k].y]].x);
			pos[_a[k].y]++;//当前位置存了元素往后走一个储存位置，因为下一次走到这个列的话必定在其后面储存
		}
		for (size_t i = 0; i < n; i++)
		{
			_a = _tmp2;
		}
		swap(_col, _row);
	}

其实我觉得代码注释已经够详细了，下面三个图每个图解释了算法难点，结合代码加思考理解

给出没有注释的代码算法：

	void Transpostion2()
	{
		vector<Triple<int>> _tmp2;
		 size_t n = _a.size();
		 _tmp2.resize(n);
		size_t num[5] = { 0 };
		size_t pos[5] = { 0 };
		for (size_t i = 0; i < n; i++)
			num[_a[i].y]++;
		pos[0] = 0;
		for (size_t j = 1; j < 5; j++)
		{
			pos[j] =pos[j - 1] + num[j - 1];
		}
		for (size_t k = 0; k < n; k++)
		{
			_tmp2[pos[_a[k].y]] = _a[k];
			swap(_tmp2[pos[_a[k].y]].y, _tmp2[pos[_a[k].y]].x);
			pos[_a[k].y]++;
		}
		for (size_t i = 0; i < n; i++)
		{
			_a = _tmp2;
		}
		swap(_col, _row);
	}

③第三点就是稀疏矩阵的加法

分别计算两个矩阵的有效元素在 各自矩阵中的序列，然后遍历矩阵，如果序列相等则相加对应元素，否则把较小的插入新的三元表中，然后继续比较。。

算法如下：这个代码比较挫，你可以根据自己想法写

//稀疏矩阵的加法
	void operator+(Trituple<T> &tri2)//第二个要运算的矩阵
	{
		if (tri2._col != _col&&tri2._row != _row)//判断矩阵是否相同
		{
			exit(0);
		}
		vector<Triple<T>> tmp;
		size_t index1 = 0;
		size_t index2 = 0;
		size_t _aarr[6] = { 0 };//储存第一个的偏移量,注意这里可以去优化修改，我就不弄了
		size_t _tarr2[6] = { 0 };//储存第二个的偏移量
		for (size_t i = 0; i < _a.size(); i++)
		{
			_aarr[i] = ((_a[i].x * _col) + _a[i].y);
		}
		for (size_t j = 0; j < tri2._a.size(); j++)
		{
			_tarr2[j] = ((tri2._a[j].x *tri2._col) + tri2._a[j].y);
		}
		while (index1 < 6 && index2<6)//开始计算
		{
			while (_aarr[index1]>_tarr2[index2] && index1 < 6 && index2 < 6)
			{
				tmp.push_back(tri2._a[index2]);
				index2++;
			}
			while (_aarr[index1] < _tarr2[index2] && index1 < 6 && index2 < 6)
			{
				tmp.push_back(_a[index1]);
				index1++;
			}
			while (_aarr[index1] == _tarr2[index2] && index1 < 6 && index2 < 6)
			{
				_a[index1].data += tri2._a[index2].data;
				tmp.push_back(_a[index1]);
				index1++;
				index2++;
			}
			_a.resize(tmp.size());
			for (size_t i = 0; i < tmp.size(); i++)
			{
				_a[i] = tmp[i];
			}
		}
	}

好了以上就给出了稀疏矩阵的相关问题的算法下面给出完整的代码和测试结果：

#include<iostream>
#include<iomanip>
#include<vector>
using namespace std;
template<class T>
struct Triple//三元组
{
	size_t x,y;
	T data;
	Triple(size_t _x, size_t _y, T _data)
		:x(_x)
		, y(_y)
		, data(_data)
	{}
	Triple(){}
};
template<class T>
class Trituple
{
private:
	vector<Triple<T>> _a;
	T _invalue;//无效元素的个数
	size_t _row;//行
	size_t _col;
public:
	Trituple(T *a, size_t row, size_t col, T invalue)
		:_row(row)
		, _col(col)
		, _invalue(invalue)
	{
		//稀疏矩阵的压缩储存
		for (size_t i = 0; i < row; i++)
		{
			for (size_t j = 0; j < col; j++)
			{
				if ((a[i*col + j]) != _invalue)//不等于无效元素的时候王进存
				{
					Triple<T> tri(i, j, a[i*col + j]);
					_a.push_back(tri);
				}
			}
		}
	}
	//稀疏矩阵的打印
	void Display()
	{
		size_t index = 0;
		for (size_t i = 0; i < _row; i++)
		{
			for (size_t j = 0; j < _col; j++)
			{
				if (index != _a.size()&& i == _a[index].x&&j == _a[index].y)
				{
					cout <<setw(5)<< _a[index++].data;
				}
				else
				{
					cout <<setw(5)<< _invalue;
				}
			}
			cout << endl;
		}
	}
	//稀疏矩阵的逆置,效率太低
	void Transpostion()
	{
		size_t n = _a.size();
		vector<Triple<T>> _tmp;//定义转置后的Vector
		 size_t count = 0;
		for (size_t i = 0; i < _col; i++)
		{
			for (size_t j = 0; j < n; j++)
			{
				if (_a[j].y == i)//如果列下标符合，则将其压入vector
				{
					_tmp.push_back(_a[j]);
					swap(_tmp[count].y, _tmp[count].x);//将压进去的元素的（x,y）互换
					count++;//为了交换而设计的，不然的话没有办法交换
				}
			}
		}
		for (size_t i = 0; i < n; i++)//方便打印而写的代码
		{
			_a[i] = _tmp[i];
		}
		swap(_col, _row);//整体矩阵的行列互换
	}
	//快速逆置
	void Transpostion2()
	{
		vector<Triple<int>> _tmp2;
		 size_t n = _a.size();
		 _tmp2.resize(n);
		size_t num[5] = { 0 };
		size_t pos[5] = { 0 };
		for (size_t i = 0; i < n; i++)
			num[_a[i].y]++;
		pos[0] = 0;
		for (size_t j = 1; j < 5; j++)
		{
			pos[j] =pos[j - 1] + num[j - 1];
		}
		for (size_t k = 0; k < n; k++)
		{
			_tmp2[pos[_a[k].y]] = _a[k];
			swap(_tmp2[pos[_a[k].y]].y, _tmp2[pos[_a[k].y]].x);
			pos[_a[k].y]++;
		}
		for (size_t i = 0; i < n; i++)
		{
			_a = _tmp2;
		}
		swap(_col, _row);
	}
	//稀疏矩阵的加法
	void operator+(Trituple<T> &tri2)//第二个要运算的矩阵
	{
		if (tri2._col != _col&&tri2._row != _row)//判断矩阵是否相同
		{
			exit(0);
		}
		vector<Triple<T>> tmp;
		size_t index1 = 0;
		size_t index2 = 0;
		size_t _aarr[6] = { 0 };//储存第一个的偏移量,注意这里可以去优化修改，我就不弄了
		size_t _tarr2[6] = { 0 };//储存第二个的偏移量
		for (size_t i = 0; i < _a.size(); i++)
		{
			_aarr[i] = ((_a[i].x * _col) + _a[i].y);
		}
		for (size_t j = 0; j < tri2._a.size(); j++)
		{
			_tarr2[j] = ((tri2._a[j].x *tri2._col) + tri2._a[j].y);
		}
		while (index1 < 6 && index2<6)//开始计算
		{
			while (_aarr[index1]>_tarr2[index2] && index1 < 6 && index2 < 6)
			{
				tmp.push_back(tri2._a[index2]);
				index2++;
			}
			while (_aarr[index1] < _tarr2[index2] && index1 < 6 && index2 < 6)
			{
				tmp.push_back(_a[index1]);
				index1++;
			}
			while (_aarr[index1] == _tarr2[index2] && index1 < 6 && index2 < 6)
			{
				_a[index1].data += tri2._a[index2].data;
				tmp.push_back(_a[index1]);
				index1++;
				index2++;
			}
			_a.resize(tmp.size());
			for (size_t i = 0; i < tmp.size(); i++)
			{
				_a[i] = tmp[i];
			}
		}
	}
};
void test()
{
	int arr[4][5] =//矩阵1
	{
		{ 0, 0, 3, 0, 4 },
		{ 0, 0, 0, 0, 0 },
		{ 0, 1, 0, 3, 0 },
		{ 5, 0, 6, 0, 0 },
	};
	int arr2[4][5] =//矩阵2
	{
		{ 0, 2, 0, 0, 4 },
		{ 0, 0, 0, 0, 0 },
		{ 0, 1, 0, 3, 0 },
		{ 5, 0, 6, 0, 0 },
	};
	Trituple<int> trii((int*)arr, 4, 5, 0);//矩阵1
	Trituple<int> trii2((int*)arr2, 4, 5, 0);//矩阵2
	cout << "打印原矩阵如下" << endl;
	trii.Display();
	trii.Transpostion();//慢速转置
	cout << "慢速转置如下：" << endl;
	trii.Display();
	cout << "快速转置转置：" << endl;
	trii.Transpostion2();//快速转置
	trii.Display();
	cout << "将矩阵" << endl;;
	trii.Display();
	cout  << "和矩阵" <<endl;
	trii2.Display();
	cout << " 相加";
	cout << "结果如下:" << endl;
	trii + trii2;
	trii.Display();
}
int main()
{
	test();
	system("pause");
	return 0;
}