特殊矩阵的压缩存储

向右看齐 2022-01-12 17:51 294阅读 0赞

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

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

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

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

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

[![wKioL1cWSufBUodkAAAGyARsPlY872.png][]][wKioL1cWSufBUodkAAAGyARsPlY872.png]

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

在此程序中需要注意:

(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 T>
    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 <class T>
    SymmetricMatrix<T>::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 <class T>
    SymmetricMatrix<T>::~SymmetricMatrix()
    {
    	if(_a != NULL)
    	{
    		delete[] _a;
    		_a = NULL;
    		_size = 0;
    	}
    }
    
    template <class T>
    T& SymmetricMatrix<T>::Access(size_t i, size_t j)//(i,j)位置上的元素
    {
    	if(i<j)//上矩阵
    	{
    		swap(i,j);//对称，交换
    	}
    	return _a[i*(i+1)/2+j];
    }
    
    template <class T>
    void SymmetricMatrix<T>::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<<endl;
    	}
    	cout<<endl;
    }

测试函数：

void Test()
    {
    	int arr[][4]={
         {0,1,2,3},
    	              {1,0,4,5},
    	              {2,4,0,6},
    	              {3,5,6,0}};
    	SymmetricMatrix<int> sm((int*)arr,4);
    	sm.Display();
    	int ret = sm.Access(2,3);
    	cout<<ret<<endl;
    	return 0;
    }

测试结果：

[![wKioL1cWT6iwo2i3AAAOghmzccA643.png][]][wKioL1cWT6iwo2i3AAAOghmzccA643.png]

接下来呢，我们看一下稀疏矩阵。

所谓系数矩阵呢，就是指矩阵中的大多数元素为0。当非零元素的个数低于总元素的30%时，这样的矩阵称为稀疏矩阵。如下所示：

[![wKioL1cWUNiS390nAAAFcx05FiI569.png][]][wKioL1cWUNiS390nAAAFcx05FiI569.png]

如何存储稀疏矩阵呀，对于稀疏矩阵的存储，采取只存储非零元素的方法。由于稀疏矩阵的元素并没有规律，所以在存储元素时，还必须存储非零元素的行号和列号。这就是稀疏矩阵的三元组表示法。

三元组的结构：

template <class T>
    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 T>
    class SpareMatrix//稀疏矩阵
    {
    public:
    	SpareMatrix();//无参构造函数
    	SpareMatrix(T* a,size_t m,size_t n,const T& invalue);//有参构造函数
    	void Display();//打印
    	SpareMatrix<T> Transport();//转置
    	SpareMatrix<T> FastTransport();//快速转置
    protected:
    	vector<Triple<T> > _a;//存储三元组的数组
    	size_t _rowSize;//行
    	size_t _colSize;//列
    	T _invalue;//非法值
    };
    
    template <class T>
    SpareMatrix<T>::SpareMatrix(T *a, size_t m, size_t n, const T& invalue)
                    :_rowSize(m)
    		,_colSize(n)
    		,_invalue(invalue)
    {
    	for(size_t i=0;i<m;i++)
    	{
    		for(size_t j=0;j<n;j++)
    		{
    			if(a[i*n+j] != invalue)
    			{
    				_a.push_back(Triple<T>(a[i*n+j],i,j));
    			}
    		}
    	}
    }
    template <class T>
    SpareMatrix<T>::SpareMatrix()
    :_rowSize(0)
    ,_colSize(0)
    {}
    template <class T>
    void SpareMatrix<T>::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<<endl;
    	}
    	cout<<endl;
    }
    
    template <class T>
    SpareMatrix<T> SpareMatrix<T>::Transport()//从三元数组上入手，以列为主，重新存储
    {
    	SpareMatrix<T> tmp;
    	tmp._rowSize = _colSize;//行
    	tmp._colSize = _rowSize;//列
    	tmp._invalue = _invalue;
    
    	Triple<T> 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 <class T>
    SpareMatrix<T> SpareMatrix<T>::FastTransport()//快速逆置
    {
    	SpareMatrix<T> tmp;
    	tmp._rowSize = _colSize;//行
    	tmp._colSize = _rowSize;//列
    	tmp._invalue = _invalue;
    
    	SpareMatrix<T> rowCount = new int[tmp._rowSize];//记录每一列元素的个数
    	SpareMatrix<T> 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;
    		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<int> sm((int*)arr,4,5,int());
    	sm.Display();
    	//sm.Transport((int*)arr,4,5,int());
    	//sm.Display(5,4);
    	SpareMatrix<int> ret = sm.Transport();
    	ret.Display();
    
    	SpareMatrix<int> ret1 = sm.FastTransport();
    	ret1.Display();
    
    	return 0;
    }

测试结果：

[![wKioL1cWWDDjmtaxAAAWX4jY-kk517.png][]][wKioL1cWWDDjmtaxAAAWX4jY-kk517.png]

转载于:https://blog.51cto.com/10810429/1765602

[wKioL1cWSufBUodkAAAGyARsPlY872.png]: /images/20220113/6c87394f4b3d42e3a04bcd143dc7d941.png
[wKioL1cWT6iwo2i3AAAOghmzccA643.png]: https://s1.51cto.com/wyfs02/M01/7F/32/wKioL1cWT6iwo2i3AAAOghmzccA643.png
[wKioL1cWUNiS390nAAAFcx05FiI569.png]: /images/20220113/b48b780c698246dc9f3c646061bef09e.png
[wKioL1cWWDDjmtaxAAAWX4jY-kk517.png]: https://s1.51cto.com/wyfs02/M00/7F/32/wKioL1cWWDDjmtaxAAAWX4jY-kk517.png