温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

稀疏矩阵的压缩存储与转置

发布时间:2020-08-05 23:08:34 来源:网络 阅读:512 作者:夜的寂寞 栏目:编程语言

稀疏矩阵:矩阵中大多数元素为0的矩阵(本文以行序为主序)

稀疏矩阵的三元组表述法:

        稀疏矩阵的压缩存储与转置

类型结构:

template <typename T>
struct Triple
{
	int _row;
	int _col;
	T _value;
};

template <typename T>
class SparseMatrix
{
public:
	SparseMatrix<T>::SparseMatrix();
	SparseMatrix(const T* array, size_t row, size_t col, const T& invalid);
	~SparseMatrix();
	void Display()const;
	SparseMatrix<T> Transport()const;
	SparseMatrix<T> FastTransport()const;
protected:
	vector<Triple<T>> _array;
	size_t _rowCount;
	size_t _colCount;
	T _invalid;
};

代码实现压缩存储:

//稀疏矩阵
template <typename T>
SparseMatrix<T>::SparseMatrix(){}
template <typename T>
SparseMatrix<T>::SparseMatrix(const T* array, size_t row, size_t col, const T& invalid)
:_rowCount(row), _colCount(col), _invalid(invalid)
{
	assert(array);
	for (size_t i = 0; i < row; ++i)
	{
		for (size_t j = 0; j < col; ++j)
		{
			if (array[i*col + j] != invalid)
			{
				this->_array.push_back({ i, j, array[i*col + j] });
			}
		}
	}
}
template <typename T>
SparseMatrix<T>::~SparseMatrix()
{}
template <typename T>
void SparseMatrix<T>::Display()const
{
	size_t size = this->_array.size();
	size_t iCount = 0;
	for (size_t i = 0; i < this->_rowCount; ++i)
	{
		for (size_t j = 0; j < this->_colCount; ++j)
		{
			if (iCount < size && i == this->_array[iCount]._row && j == this->_array[iCount]._col)
			{
				cout << this->_array[iCount]._value << " ";
				++iCount;
			}
			else
			{
				cout << this->_invalid << " ";
			}
		}
		cout << endl;
	}
}

稀疏矩阵的转置:

1)列序递增转置法:找出第i行全部元素:从头到尾扫描三元组表A,找出其中所有_col==i的三元组,转置后放入三元组表B中。代码实现如下:

template <typename T>
SparseMatrix<T> SparseMatrix<T>::Transport()const
{
	SparseMatrix<T> ret;
	ret._rowCount = this->_colCount;
	ret._colCount = this->_rowCount;
	ret._invalid = this->_invalid;
	size_t size = this->_array.size();
	for (size_t col = 0; col < this->_colCount; ++col)
	{
		for (size_t iCount = 0; iCount < size; ++iCount)
		{
			if (this->_array[iCount]._col == col)
			{
				ret._array.push_back({ this->_array[iCount]._col, this->_array[iCount]._row, 
									this->_array[iCount]._value });
			}
		}
	}
	return ret;
}

2)一次定位快速转置法

在方法1中为了使转置后矩阵的三元组表B仍按行序递增存放,必须多次扫描被转置的矩阵的三元组表A。为了能将被转置三元组表A的元素一次定位到三元组B的正确位置上,需要预先计算以下数据:

    i)待转置矩阵三元组表A每一列中非0元素的总个数,即转置后矩阵三元组元素B的每一行的非0元素总个数

    ii)待转置矩阵每一列中第一个非0元素在三元组表B中的正确位置,即转置后矩阵每一行中第一个非0元素在三元组B中的正确位置

    为此,需要设两个数组分别为num[] 和 pos[] ,其中num[col]用来存放三元组表A第col列中非0元素元素总个数,pos[col]用来存放转置前三元组表A中第col列中第一个非0元素在三元组表B中的存储位置。

num[col]的计算方法:将三元组表A扫描一遍,对于其中列号为col的元素,给相应的num数组中下标为col的元素加1.

pos[col]的计算方法:

    i)pos[0] = 0,表示三元组表A中,列值为0的第一个非0元素在三元组表B中的下标值。

    ii)pos[col] = pos[col - 1] + num[col - 1],其中1<=col<A.size();

eg:

0  1  9  0  0  0  0

0  0  0  0  0  0  0

3  0  0  0  0  4  0

0  0  2  0  0  0  0

0  8  0  0  0  0  0

 5  0  0  7  0  0  0 

col0123456
num[col]2221010
pos[col]0246778

代码实现:

template <typename T>
SparseMatrix<T> SparseMatrix<T>::Transport()const
{
	SparseMatrix<T> ret;
	ret._rowCount = this->_colCount;
	ret._colCount = this->_rowCount;
	ret._invalid = this->_invalid;
	size_t size = this->_array.size();
	for (size_t col = 0; col < this->_colCount; ++col)
	{
		for (size_t iCount = 0; iCount < size; ++iCount)
		{
			if (this->_array[iCount]._col == col)
			{
				ret._array.push_back({ this->_array[iCount]._col, this->_array[iCount]._row, 
									this->_array[iCount]._value });
			}
		}
	}
	return ret;
}
template <typename T>
SparseMatrix<T> SparseMatrix<T>::FastTransport()const
{
	SparseMatrix<T> ret;
	ret._rowCount = this->_colCount;
	ret._colCount = this->_rowCount;
	ret._invalid = this->_invalid;
	size_t size = this->_array.size();	
	ret._array.resize(size);
	vector<int> num(this->_colCount);
	vector<int> pos(this->_colCount); //pos[i] = pos[i-1]+num[i-1] i>0
	for (size_t i = 0; i < size; ++i)
	{
		++num[this->_array[i]._col];
	}
	for (size_t col = 1; col < this->_colCount; ++col)
	{
		pos[col] = pos[col - 1] + num[col - 1];
	}
	for (size_t i = 0; i < size; ++i)
	{
		ret._array[pos[this->_array[i]._col]++] = { this->_array[i]._col, this->_array[i]._row, this->_array[i]._value };
	}

	return ret;
}

运行结果:

稀疏矩阵的压缩存储与转置

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI