特殊矩陣的壓縮存儲

   本片博客討論的特殊矩陣包括兩部分：

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

測試結果：