特殊矩阵的压缩存储-创新互联

本片博客讨论的特殊矩阵包括两部分：

 （1）元素分布有特殊规律的矩阵，寻找规律对应的公式实现压缩存储。如：对称矩阵。

 （2）非零元素很少的稀疏矩阵，可采用只存储非零元素的方式实现压缩存储。

首先呢，先来讨论下对称矩阵。

所谓对称矩阵呢，就是行和列相同，上矩阵和下矩阵对称。还是看图吧，一目了然。

  看此矩阵，若要将其存储，会浪费空间。就对称这一特征来说，可只存储其上矩阵或者下矩阵。就以存储下矩阵为例。

在此程序中需要注意:

  (1)若矩阵为N*N，则需要为其开辟N*（N+1）/2大的数组。

  (2)矩阵i行j列的元素对应数组的下标为i*(i+1)/2+j的元素。

  即：SymmetricMatrix[i][j] ==> Array[i*(i+1)/2+j]。

代码实现：

template 
class SymmetricMatrix
{
public: //声明
	SymmetricMatrix(T* a,size_t size);
	~SymmetricMatrix();
	T& Access(size_t i,size_t j);
	void Display();
protected:
	T* _a;//数组
	size_t _size;//压缩矩阵的下标
	size_t _n;//方阵的行，列
};

//函数实现

template 
SymmetricMatrix::SymmetricMatrix(T* a,size_t size)
                 :_a(new T[size*(size+1)/2])//为_a开辟空间
		 ,_size(size*(size+1)/2)//下标
		 ,_n(size)//行，列
{
	size_t _index = 0;
	for(size_t i=0;i<_n;i++)
	{
		for(size_t j=0;j<_n;j++)
		{
			if(i>=j)
			{
				_a[_index++] = a[i*_n+j];//下矩阵 
			}
			else//上矩阵不存储
				break;
		}
	}
}

template 
SymmetricMatrix::~SymmetricMatrix()
{
	if(_a != NULL)
	{
		delete[] _a;
		_a = NULL;
		_size = 0;
	}
}

template 
T& SymmetricMatrix::Access(size_t i, size_t j)//(i,j)位置上的元素
{
	if(i
void SymmetricMatrix::Display()//打印对称矩阵
{
	for(size_t i=0;i<_n;i++)
	{
		for(size_t j=0;j<_n;j++)
		{
			if(i>=j)//下矩阵
			{
				cout<<_a[i*(i+1)/2+j]<<" ";
			}
			else//上矩阵
			{
				cout<<_a[j*(j+1)/2+i]<<" ";
			}
		}
		cout<
测试函数：
void Test()
{
	int arr[][4]={{0,1,2,3},
	              {1,0,4,5},
	              {2,4,0,6},
	              {3,5,6,0}};
	SymmetricMatrix sm((int*)arr,4);
	sm.Display();
	int ret = sm.Access(2,3);
	cout<
测试结果：
接下来呢，我们看一下稀疏矩阵。
所谓系数矩阵呢，就是指矩阵中的大多数元素为0。当非零元素的个数低于总元素的30%时，这样的矩阵称为稀疏矩阵。如下所示：
 
如何存储稀疏矩阵呀，对于稀疏矩阵的存储，采取只存储非零元素的方法。由于稀疏矩阵的元素并没有规律，所以在存储元素时，还必须存储非零元素的行号和列号。这就是稀疏矩阵的三元组表示法。
三元组的结构：
template 
struct Triple
{
	Triple(const T& value = T(),size_t row = 0,size_t col = 0)//初始化
		:_value(value)
		,_row(row)
		,_col(col)
	{}
	T _value; //值
	size_t _row;//行
	size_t _col;//列
}
代码实现：
template 
class SpareMatrix//稀疏矩阵
{
public:
	SpareMatrix();//无参构造函数
	SpareMatrix(T* a,size_t m,size_t n,const T& invalue);//有参构造函数
	void Display();//打印
	SpareMatrix Transport();//转置
	SpareMatrix FastTransport();//快速转置
protected:
	vector > _a;//存储三元组的数组
	size_t _rowSize;//行
	size_t _colSize;//列
	T _invalue;//非法值
};

template 
SpareMatrix::SpareMatrix(T *a, size_t m, size_t n, const T& invalue)
                :_rowSize(m)
		,_colSize(n)
		,_invalue(invalue)
{
	for(size_t i=0;i(a[i*n+j],i,j));
			}
		}
	}
}
template 
SpareMatrix::SpareMatrix()
:_rowSize(0)
,_colSize(0)
{}
template 
void SpareMatrix::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<<_invalue<<" ";
			}	
		}
		cout<
SpareMatrix SpareMatrix::Transport()//从三元数组上入手，以列为主，重新存储
{
	SpareMatrix tmp;
	tmp._rowSize = _colSize;//行
	tmp._colSize = _rowSize;//列
	tmp._invalue = _invalue;

	Triple t;
	for(size_t i=0;i<_colSize;i++)
	{
		size_t index = 0;
		while(index < _a.size())
		{
			if(_a[index]._col == i)
			{
				t._row = _a[index]._col;//交换行号，列号
				t._col = _a[index]._row;
				t._value = _a[index]._value;
				tmp._a.push_back(t);
			}
			++index;
		}	
	}
	return tmp;
}

template 
SpareMatrix SpareMatrix::FastTransport()//快速逆置
{
	SpareMatrix tmp;
	tmp._rowSize = _colSize;//行
	tmp._colSize = _rowSize;//列
	tmp._invalue = _invalue;

	SpareMatrix rowCount = new int[tmp._rowSize];//记录每一列元素的个数
	SpareMatrix rowStart = new int[tmp._rowSize];//记录元素在数组上开始的位置
	memset(rowCount,0,sizeof(int)*tmp._rowSize);//初始化为0
	memset(rowStart,0,sizeof(int)*tmp._rowSize);

	size_t index = 0;
	while(index < _a.size())//统计每一列上的元素个数
	{
		rowCount[_a[index]._col]++;
		++index;
	}

	index = 0;
	rowStart[0] = 0;
	for(size_t i=1;i<_colSize;i++)//每个元素在数组中开始的位置
	{
		rowSize[i] = rowSize[i-1] + rowCount[i-1];
	}

	index = 0;
	tmp._a.resize(_a.size());//开辟空间并默认为0
	while(index < _a.size())
	{
		size_t rowIndex = _a[index]._col
		int& start = rowStart[rowIndex];

		Triple t;
		t._value = _value;
		t._row = col;
		t._col = _row;

		tmp._a[start++] = t;	
	}
	return tmp;
}

//测试函数：
void Test()
{
	int arr[4][5] = {{0,1,0,0,0},
	                 {0,0,0,2,0},
	                 {0,4,0,0,0},
	                 {0,0,3,0,0}};
	SpareMatrix sm((int*)arr,4,5,int());
	sm.Display();
	//sm.Transport((int*)arr,4,5,int());
	//sm.Display(5,4);
	SpareMatrix ret = sm.Transport();
	ret.Display();

	SpareMatrix ret1 = sm.FastTransport();
	ret1.Display();

	return 0;
}
测试结果：
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
            

            本文标题：特殊矩阵的压缩存储-创新互联            

            转载注明：http://cqcxhl.com/article/dcgphi.html