稀疏矩陣的壓縮存儲和轉(zhuǎn)置-創(chuàng)新互聯(lián)

1、稀疏矩陣：M*N的矩陣，矩陣中有效值的個數(shù)遠(yuǎn)小于無效值的個數(shù)，且這些數(shù)據(jù)的分布沒有規(guī)律。

成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于網(wǎng)站制作、網(wǎng)站建設(shè)、平房網(wǎng)絡(luò)推廣、成都微信小程序、平房網(wǎng)絡(luò)營銷、平房企業(yè)策劃、平房品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們大的嘉獎；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供平房建站搭建服務(wù)，24小時服務(wù)熱線：13518219792，官方網(wǎng)址：muchs.cn

2、稀疏矩陣的壓縮存儲：壓縮存儲值存儲極少數(shù)的有效數(shù)據(jù)。

  由于非零元素分布沒有任何規(guī)律，所以在進行壓縮存儲的時侯需要存儲無效值的同時還要存儲有效元素在矩陣中的位置，即有效元素所在的行號和列號，也就是在存儲某個元素比如aij的值的同時，還需要存儲該元素所在的行號i和它的列號j，這樣就構(gòu)成了一個三元組(i,j,aij)的線性表。

  使用{ row, col, value }三元組存儲每一個有效數(shù)據(jù)，三元組按原矩陣中的位置，以行優(yōu)先級先后順序依次存放。

3、稀疏矩陣的轉(zhuǎn)置:將原矩陣的行、列對換，也就是將[i][j]和[j][i]位置上的數(shù)據(jù)對換。

稀疏矩陣的壓縮存儲和轉(zhuǎn)置

具體實現(xiàn)如下：

#include<iostream>
using namespace std;
#include<assert.h>
#include<vector>//vector是一個能夠存放任意類型的動態(tài)數(shù)組，能夠增加和壓縮數(shù)據(jù)，也認(rèn)為是容器
template<class T>
struct Triple//三元組結(jié)構(gòu)體
{
	int _row;
	int _col;
	T _value;//非法值/無效值
	Triple()
		:_row(0)
		, _col(0)
		, _value(0)
	{}
	Triple(int row, int col, T& value)
		:_row(row)
		, _col(col)
		, _value(value)
	{}
};
template<class T>
class SparseMatrix
{
public:
	SparseMatrix();
	SparseMatrix(T* array, int n, int m, const T& invalid);
	~SparseMatrix();
	void Display();
	SparseMatrix<T> Transpose();//轉(zhuǎn)置
	SparseMatrix<T> FastTranspose();//快速轉(zhuǎn)置
private:
	vector<Triple<T>> _array;
	size_t _rows;
	size_t _cols;
	T _invalid;
};
template<class T>
SparseMatrix<T>::SparseMatrix()
:_rows(0)
, _cols(0)
, _invalid(0)
{}
template<class T>
SparseMatrix<T>::~SparseMatrix()
{}
template<class T>
SparseMatrix<T>::SparseMatrix(T* array, int m, int n, const T& invalid)
:_rows(m)
, _cols(n)
, _invalid(invalid)
{//由于數(shù)組定義必須知道列數(shù)，則以行優(yōu)先級存放稀疏矩陣,壓縮存儲值存儲極少數(shù)的有效數(shù)據(jù)
	assert(array);
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (array[n*i + j] != invalid)
			{
				_array.push_back(Triple<T>(i, j, array[n*i + j]));//vector中push_back插入數(shù)據(jù)
			}
		}
	}
}
template<class T>
void SparseMatrix<T>::Display()
{
	//使用下標(biāo)訪問元素
	size_t indx = 0;
	for (size_t i = 0; i < _rows; i++)
	{
		for (size_t j = 0; j < _cols; j++)
		{//如果_array[indx]的行列等于i和j，且indx在范圍內(nèi)就打印其有效值，否則打印無效值0
			if (indx < _array.size() && _array[indx]._row == i && _array[indx]._col == j)
			{
				cout << _array[indx]._value << " ";
				indx++;
			}
			else
			{
				cout << _invalid << " ";
			}
		}
		cout << endl;
	}
	cout << endl;
	////使用迭代器訪問所有有效元素
	//vector<Triple<T>>::iterator it;
	//for (it = _array.begin(); it != _array.end(); it++)
	//{
	//	cout << "row:" << (*it)._row << " col:" << (*it)._col << endl;
	//	cout << "_value:" << (*it)._value << endl;
	//}
	//cout << endl;
}
template<class T>
//時間復(fù)雜度為：O(_cols*有效數(shù)據(jù)個數(shù))，空間復(fù)雜度：O(1)
SparseMatrix<T> SparseMatrix<T>::Transpose()//轉(zhuǎn)置
{//原矩陣中元素以行優(yōu)先存儲，轉(zhuǎn)置后的矩陣是以原矩陣的列優(yōu)先存儲的
	size_t indx;
	SparseMatrix<T> tmp;//新建一個稀疏矩陣存放交換后的行列和有效數(shù)據(jù)
	tmp._invalid = _invalid;
	tmp._rows = _cols;
	tmp._cols = _rows;
	tmp._array.reserve(_array.size());//reserve()擴容到size
	for (size_t i = 0; i < _cols; i++)//以列進行查找，進行行列交換
	{
		indx = 0;//將列數(shù)為i的有效元素進行行列交換
		while (indx < _array.size())
		{
			if (i == _array[indx]._col)
			{
				//Triple<T> point;
				//point._row = _array[indx]._col;
				//point._col = _array[indx]._row;
				//point._value = _array[indx]._value;
				//tmp._array.push_back(point);
				tmp._array.push_back(Triple<T>(i, _array[indx]._row, _array[indx]._value));
			}
			indx++;
		}
	}
	return tmp;
}
template<class T>
//時間復(fù)雜度為：O(_cols+有效數(shù)據(jù)個數(shù))，空間復(fù)雜度：O(_cols)
SparseMatrix<T> SparseMatrix<T>::FastTranspose()//快速轉(zhuǎn)置
{
	SparseMatrix<T> tmp;//新建一個稀疏矩陣存放交換后的行列和有效數(shù)據(jù)
	tmp._invalid = _invalid;
	tmp._rows = _cols;
	tmp._cols = _rows;
	tmp._array.resize(_array.size());//reserve()只擴容到，但不一定能用此空間，resize()開辟size個空間
	//rowCounts統(tǒng)計轉(zhuǎn)置后的矩陣每一行的數(shù)據(jù)個數(shù)(原矩陣的每列的)
	//rowStarts統(tǒng)計轉(zhuǎn)置后的矩陣每一行在壓縮矩陣中存儲的開始位置
	int* rowCounts = new int[_cols];
	int* rowStarts = new int[_cols];
	memset(rowCounts, 0, sizeof(int)*_cols);//memset()按字節(jié)初始化為某值（0）
	memset(rowStarts, 0, sizeof(int)*_cols);
	size_t indx = 0;
	while (indx < _array.size())
	{
		rowCounts[_array[indx]._col]++;//利用下標(biāo)統(tǒng)計每列數(shù)據(jù)個數(shù)，2 0 2 0 2 
		indx++;
	}
	rowStarts[0] = 0;//記錄開始位置
	for (size_t i = 1; i < _cols; i++)
	{//轉(zhuǎn)置的矩陣每一行在壓縮矩陣中存儲的開始位置，0 2 2 4 4
		rowStarts[i] = rowCounts[i - 1] + rowStarts[i - 1];
	}
	indx = 0;
	while (indx < _array.size())//快速定位
	{//rowStarts存放轉(zhuǎn)置后每一行的開始位置，rowStart不斷更新同行數(shù)據(jù)位置,轉(zhuǎn)置后同一行數(shù)據(jù)的位置不斷++，故用&
		int& rowStart = rowStarts[_array[indx]._col];
		tmp._array[rowStart++] = Triple<T>(_array[indx]._col, _array[indx]._row, _array[indx]._value);
		indx++;
	}
	return tmp;
}

測試用例如下：

void Test2()
{
	int a[][5] = {
		{ 5, 0, 3, 0, 1 },
		{ 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0 },
		{ 6, 0, 4, 0, 2 },
		{ 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0 },
	};
	SparseMatrix<int> s1((int*)a, 6, 5, 0);
	s1.Display();
	SparseMatrix<int> s2;
	s2 = s1.Transpose();
	s2.Display();
	SparseMatrix<int> s3;
	s3 = s1.FastTranspose();
	s3.Display();
}

對稱矩陣及對稱矩陣的壓縮存儲

設(shè)一個N*M的方陣A，A中任意元素Aij，當(dāng)且僅當(dāng)Aij == Aji(0<=i<=N-1&&0<=j<=N-1)，則矩陣A是對稱矩陣。以矩陣的對角線為分隔，分為上三角和下三角。

壓縮存儲稱矩陣存儲時只需要存儲上三角/下三角的數(shù)據(jù)，所以最多存儲n(n+1)/2個數(shù)據(jù)。

對稱矩陣和壓縮存儲的對應(yīng)關(guān)系：下三角存儲i>=j, SymmetricMatrix[i][j]==Array[i*(i+1)/2+j]

下面對下三角的壓縮存儲的具體實現(xiàn)：

template<class T>
class SymmetricMatrix
{
public:
	SymmetricMatrix()
		:_a(NULL)
		, _size(0)
	{}
	SymmetricMatrix(T* a, const size_t size)
		:_a(new T[size*(size+1)/2])
		, _size(size*(size+1)/2)
	{
		assert(a);
		//size_t indx = 0;
		for (size_t i = 0; i < size; i++)
		{
			for (size_t j = 0; j < size; j++)
			{
				if (i >= j)//if (i >= j && indx < _size)
				{
					//方法一：_a[indx] = a[i*size + j];indx++;
					//方法二：運用下三角矩陣的對稱矩陣和壓縮存儲的對應(yīng)關(guān)系：
					//下三角存儲i>=j,  SymmetricMatrix[i][j] == Array[i*(i+1)/2+j]
					_a[i*(i + 1) / 2 + j] = a[i*size + j];
				}
			}
		}
	}
	void Display()
	{
		if (_a)
		{
			for (size_t indx = 0; indx < _size; indx++)
			{
				cout << _a[indx] << " ";
			}
			cout << "\nsize = " << _size << endl;
		}
	}
	~SymmetricMatrix()
	{
		if (_a)
		{
			delete[] _a;
		}
	}
private:
	T* _a;
	size_t _size;
};
void Test1()
{
	int a[][5] = {
		{ 0, 1, 2, 3, 4 },
		{ 1, 0, 1, 2, 3 },
		{ 2, 1, 0, 1, 2 },
		{ 3, 2, 1, 0, 1 }, 
		{ 4, 3, 2, 1, 0 },
	};
	SymmetricMatrix<int> s1((int*)a, 5);
	s1.Display();
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站題目：稀疏矩陣的壓縮存儲和轉(zhuǎn)置-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://muchs.cn/article46/dejohg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、搜索引擎優(yōu)化、商城網(wǎng)站、做網(wǎng)站、營銷型網(wǎng)站建設(shè)、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都定制網(wǎng)站建設(shè)