1、稀疏矩陣：M*N的矩陣，矩陣中有效值的個(gè)數(shù)遠(yuǎn)小于無效值的個(gè)數(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íng)銷、平房企業(yè)策劃、平房品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們大的嘉獎(jiǎng)；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供平房建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：chinadenli.net

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

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

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

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

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

#include<iostream>
using namespace std;
#include<assert.h>
#include<vector>//vector是一個(gè)能夠存放任意類型的動(dòng)態(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)先級(jí)存放稀疏矩陣,壓縮存儲(chǔ)值存儲(chǔ)極少數(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>
//時(shí)間復(fù)雜度為：O(_cols*有效數(shù)據(jù)個(gè)數(shù))，空間復(fù)雜度：O(1)
SparseMatrix<T> SparseMatrix<T>::Transpose()//轉(zhuǎn)置
{//原矩陣中元素以行優(yōu)先存儲(chǔ)，轉(zhuǎn)置后的矩陣是以原矩陣的列優(yōu)先存儲(chǔ)的
	size_t indx;
	SparseMatrix<T> tmp;//新建一個(gè)稀疏矩陣存放交換后的行列和有效數(shù)據(jù)
	tmp._invalid = _invalid;
	tmp._rows = _cols;
	tmp._cols = _rows;
	tmp._array.reserve(_array.size());//reserve()擴(kuò)容到size
	for (size_t i = 0; i < _cols; i++)//以列進(jìn)行查找，進(jìn)行行列交換
	{
		indx = 0;//將列數(shù)為i的有效元素進(jìn)行行列交換
		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>
//時(shí)間復(fù)雜度為：O(_cols+有效數(shù)據(jù)個(gè)數(shù))，空間復(fù)雜度：O(_cols)
SparseMatrix<T> SparseMatrix<T>::FastTranspose()//快速轉(zhuǎn)置
{
	SparseMatrix<T> tmp;//新建一個(gè)稀疏矩陣存放交換后的行列和有效數(shù)據(jù)
	tmp._invalid = _invalid;
	tmp._rows = _cols;
	tmp._cols = _rows;
	tmp._array.resize(_array.size());//reserve()只擴(kuò)容到，但不一定能用此空間，resize()開辟size個(gè)空間
	//rowCounts統(tǒng)計(jì)轉(zhuǎn)置后的矩陣每一行的數(shù)據(jù)個(gè)數(shù)(原矩陣的每列的)
	//rowStarts統(tǒng)計(jì)轉(zhuǎn)置后的矩陣每一行在壓縮矩陣中存儲(chǔ)的開始位置
	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)計(jì)每列數(shù)據(jù)個(gè)數(shù)，2 0 2 0 2 
		indx++;
	}
	rowStarts[0] = 0;//記錄開始位置
	for (size_t i = 1; i < _cols; i++)
	{//轉(zhuǎn)置的矩陣每一行在壓縮矩陣中存儲(chǔ)的開始位置，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;
}

測(cè)試用例如下：

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

對(duì)稱矩陣及對(duì)稱矩陣的壓縮存儲(chǔ)

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

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

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

下面對(duì)下三角的壓縮存儲(chǔ)的具體實(shí)現(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ùn)用下三角矩陣的對(duì)稱矩陣和壓縮存儲(chǔ)的對(duì)應(yīng)關(guān)系：
					//下三角存儲(chǔ)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小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

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

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

廣告

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