假设在m*n的矩阵中,有t个元素不为0。令稀疏因子s=t/(m*n),通常认为s<0.05时称为稀疏矩阵。
有时为了节省存储空间,可以对这类矩阵进行压缩存储。所谓的压缩存储就是,为多个相同的值分配存储在一个空间,对零元不分配空间。而稀疏矩阵是只存储有效值,无效值只分配一个空间。
在这里我们用一个顺序表vector存储稀疏矩阵的有效值的行,列,值三个元素。
struct Triple { int _cow; int _col; T _value; Triple(int cow,int col,T value) :_cow(cow) , _col(col) , _value(value) {} Triple() :_cow(0) , _col(0) { } };
class SparseMatrix { public: SparseMatrix(T* a, int m, int n, const T& invalid) :_cow(m) , _col(n) , _invalue(invalid) { for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (a[i*n + j] != invalid) { Triple<T> tmp(i, j, a[i*n + j]); _a.push_back(tmp); } } } } protected: vector<Triple<T>> _a; int _cow;//矩阵行数 int _col;//矩阵列数 T _invalue;//无效值 };
下面我们来讨论一下稀疏矩阵的转置,转置运算时最简单的一种矩阵运算。要得到转置矩阵,我们只要做到三点。
将矩阵的行列值相互交换
每个三元组的i和j相互交换
重排三元组之间的次序便可以实现转置
SparseMatrix<T> Transport() { SparseMatrix<T> tmp; tmp._cow = _col; tmp._col = _cow; tmp._invalue = _invalue; for (size_t i = 0; i < _col; ++i)//遍历每一列,找到每一列有效值 { size_t index = 0; while (index < _a.size()) { if (_a[index]._col == i) { Triple<T> tp; tp._col = _a[index]._cow; tp._cow = _a[index]._col; tp._value = _a[index]._value; tmp._a.push_back(tp); } index++; } } return tmp; }
对于矩阵的转置,我们首先得要了解转置后行列的变化。转置前的行变成了转置后的列。对于三元组顺序表中的元素是遵循行优先存储的。所以要得到转置后的每一行的有效值,只要循环遍历转置前的每一列即可。
矩阵的转置可以优化,使用快速转置。
SparseMatrix<T> FastTransport() { SparseMatrix<T> tmp; tmp._cow = _col; tmp._col = _cow; tmp._invalue = _invalue; tmp._a.resize(_a.size()); int* cowCount = new int[_col]; int* cowStart = new int[_col]; memset(cowCount, 0, sizeof(int)*_col); memset(cowStart, 0, sizeof(int)*_col); size_t index = 0; while (index < _a.size()) { cowCount[_a[index++]._col]++; cowStart[0]; for (size_t i = 1; i < _col; ++i) { cowStart[i] = cowStart[i - 1] + cowCount[i - 1]; } } index = 0; while (index < _a.size()) { int& cowBegin = cowStart[_a[index]._col]; Triple<T> tp; tp._col = _a[index]._cow; tp._cow = _a[index]._col; tp._value = _a[index]._value; tmp._a[cowBegin] = tp; cowBegin++; index++; } return tmp; }
快速转置的思想是开辟两个数组用来存每一行有效值的个数,另一个用来存每个有效值在转置后顺序表vector中的起始位置。使用数组可以快速找到有效数据在转置后顺序表中的位置
以下是完整代码:
#pragma once #include<iostream> #include<vector> using namespace std; template<class T> struct Triple { int _cow; int _col; T _value; Triple(int cow,int col,T value) :_cow(cow) , _col(col) , _value(value) {} Triple() :_cow(0) , _col(0) { } }; template<class T> class SparseMatrix { public: SparseMatrix(T* a, int m, int n, const T& invalid) :_cow(m) , _col(n) , _invalue(invalid) { for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (a[i*n + j] != invalid) { Triple<T> tmp(i, j, a[i*n + j]); _a.push_back(tmp); } } } } SparseMatrix() :_cow(0) , _col(0) {} SparseMatrix<T> Transport() { SparseMatrix<T> tmp; tmp._cow = _col; tmp._col = _cow; tmp._invalue = _invalue; for (size_t i = 0; i < _col; ++i) { size_t index = 0; while (index < _a.size()) { if (_a[index]._col == i) { Triple<T> tp; tp._col = _a[index]._cow; tp._cow = _a[index]._col; tp._value = _a[index]._value; tmp._a.push_back(tp); } index++; } } return tmp; } SparseMatrix<T> FastTransport() { SparseMatrix<T> tmp; tmp._cow = _col; tmp._col = _cow; tmp._invalue = _invalue; tmp._a.resize(_a.size()); int* cowCount = new int[_col]; int* cowStart = new int[_col]; memset(cowCount, 0, sizeof(int)*_col); memset(cowStart, 0, sizeof(int)*_col); size_t index = 0; while (index < _a.size()) { cowCount[_a[index++]._col]++; cowStart[0]; for (size_t i = 1; i < _col; ++i) { cowStart[i] = cowStart[i - 1] + cowCount[i - 1]; } } index = 0; while (index < _a.size()) { int& cowBegin = cowStart[_a[index]._col]; Triple<T> tp; tp._col = _a[index]._cow; tp._cow = _a[index]._col; tp._value = _a[index]._value; tmp._a[cowBegin] = tp; cowBegin++; index++; } return tmp; } void Display() { size_t index = 0; for (int i = 0; i < _cow; i++) { for (int j = 0; j < _col; j++) { if (index < _a.size()//此处必须加index<_a.size()这个条件, //并且在最前面访问到最后一个有效值后再_a[index]会访问越界 &&_a[index]._cow == i && _a[index]._col == j) { cout << _a[index]._value << " "; ++index; } else { cout << _invalue << " "; } } cout << endl; } cout << endl; } protected: vector<Triple<T>> _a; int _cow;//矩阵行数 int _col;//矩阵列数 T _invalue; };
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。