矩阵的压缩储存(C++)

主要思想:
1.利用数学公式进行下标转换,把原本高维的数组下标转换成一维

本题以对称矩阵为例

下标转换公式如下:

矩阵的压缩储存(C++)
来源是:(上一行的所有元素总和(本题中即为等差数列求和))+(这一行前面的所有元素)

注意
1.这里都是以0开头,数组中的 [0] 也要储存元素,所以公式中会出现结果为0

2.本题思想和下三角矩阵的一样,只不过是下三角矩阵要多开一个数组空间储存它上三角的值( 下三角矩阵中,上三角的值都相等),同时要更改一下 i < j 的情况。上三角矩阵就是反过来的等差数列求和.
矩阵的压缩储存(C++)
3.对角矩阵,带状矩阵同理,也是找数学公式,
百度百科链接: 带状矩阵.

我采用的方法是用二维数组输入,如果想直接用一维数组接受输入也可以,注意下标就好了

#include<bits/stdc++.h>
using namespace std;
class symmetric_matrix
{
	int* ma;
	int size;
	int row_num;
public:
	symmetric_matrix()
	{
		size = 0;
		ma = new int[size];
		row_num = 0;//初始化
	}
	symmetric_matrix(int** a, int row)
	{
		int i, j;
		size = row * (row + 1) / 2;
		row_num = row;
		ma = new int[size];
		for (i = 0; i < row; i++)
		{
			for (j = 0; j < row; j++)
			{
				if (i >= j)
					ma[(i * (i + 1)) / 2 + j] = a[i][j];
				else
				{
					ma[(j * (j + 1)) / 2 + i] = a[i][j];
				}
			}
		}
	}
	void print()
	{
		int i, j;
		for (i = 0; i < row_num; i++)
		{
			for (j = 0; j < row_num; j++)
			{
				if (i >= j)
					cout << ma[(i * (i + 1)) / 2 + j] << " ";
				else
				{
					cout << ma[(j * (j + 1)) / 2 + i] << " ";
				}
				if (j == row_num - 1)
					cout << endl;
			}
		}
	}
	symmetric_matrix addmatrix(symmetric_matrix a)
	{
		symmetric_matrix b;
		b.size = size;
		b.row_num = row_num;
		delete b.ma;//释放无参构造函数开辟的空间
		b.ma = new int[size];//重新声明一个变量来储存相加后的矩阵
		int i, j;
		for (i = 0; i < size; i++)
		{

			b.ma[i] = a.ma[i] + ma[i];

		}
		return b;
	}
	symmetric_matrix submatrix(symmetric_matrix a)
	{
		symmetric_matrix b;
		b.size = size;
		b.row_num = row_num;
		delete b.ma;
		b.ma = new int[size];
		int i, j;
		for (i = 0; i < size; i++)
		{

			b.ma[i] = a.ma[i] - ma[i];

		}
		return b;
	}
//由于对称矩阵相乘不一定得到对称矩阵,所以不用考虑相乘
};
int main()
{
	int** a, b;
	cin >> b;
	int i, j;
	a = new int* [b];
	for (i = 0; i < b; i++)
	{
		a[i] = new int[b];
	}
	for (i = 0; i < b; i++)
	{
		for (j = 0; j < b; j++)
		{
			cin >> a[i][j];
		}
	}
	symmetric_matrix p(a,b);
	p.print();

	cin >> b;
	a = new int* [b];
	for (i = 0; i < b; i++)
	{
		a[i] = new int[b];
	}
	for (i = 0; i < b; i++)
	{
		for (j = 0; j < b; j++)
		{
			cin >> a[i][j];
		}
	}
	symmetric_matrix p1(a, b);



	(p.addmatrix(p1)).print();
	

	(p.submatrix(p1)).print();
	
	

}
/*1 2 3
  2 5 4
  3 4 6*/

参考:数据结构(c++版)(第二版)清华大学出版社 陈宝平等主编

上一篇:洛谷 P3017 [USACO11MAR]Brownie Slicing G(二分,前缀和)


下一篇:【计算和控制流】30、上机练习:创建并调用函数