稀疏矩阵:矩阵中大多数元素为0的矩阵(本文以行序为主序)
我们提供的服务有:做网站、成都网站建设、微信公众号开发、网站优化、网站认证、修文ssl等。为上千企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的修文网站制作公司
稀疏矩阵的三元组表述法:
类型结构:
templatestruct Triple { int _row; int _col; T _value; }; template class SparseMatrix { public: SparseMatrix ::SparseMatrix(); SparseMatrix(const T* array, size_t row, size_t col, const T& invalid); ~SparseMatrix(); void Display()const; SparseMatrix Transport()const; SparseMatrix FastTransport()const; protected: vector > _array; size_t _rowCount; size_t _colCount; T _invalid; };
代码实现压缩存储:
//稀疏矩阵 templateSparseMatrix ::SparseMatrix(){} template SparseMatrix ::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 SparseMatrix ::~SparseMatrix() {} template void SparseMatrix ::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中。代码实现如下:
templateSparseMatrix SparseMatrix ::Transport()const { SparseMatrix 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 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 代码实现: 运行结果:col 0 1 2 3 4 5 6 num[col] 2 2 2 1 0 1 0 pos[col] 0 2 4 6 7 7 8 template
分享题目:稀疏矩阵的压缩存储与转置
URL链接:http://cdkjz.cn/article/johjjj.html