特殊矩阵的压缩存储

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

  （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 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;
}

测试结果：

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

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

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

三元组的结构：

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;
}

测试结果：