什么是稀疏矩阵呢, 就是在 M*N 的矩阵中, 有效值的个数远小于无效值的个数, 并且这些数据的分布没有规律. 在压缩存储稀疏矩阵的时候我们只存储极少数的有效数据. 我们在这里使用三元组存储每一个有效数据, 三元组按原矩阵中的位置, 以行优先级先后次序依次存放. 下面我们来看一下代码实现.
- #include
- #include
- #include
- usingnamespace std;
- template
- class SparseMatrix
- {
- // 三元组
- template
- struct Trituple
- {
- Trituple()// 给一个默认构造函数
- {}
- Trituple(size_t row, size_t col, const T& data)
- :_row(row)
- ,_col(col)
- ,_data(data)
- {}
- size_t _row;
- size_t _col;
- T _data;
- };
- public:
- // 稀疏矩阵的压缩存储
- SparseMatrix()
- {}
- SparseMatrix(int* arr, size_t row, size_t col, const T& invalid)
- :_row(row)
- ,_col(col)
- ,_invalid(invalid)
- {
- for(int i = 0; i < row; i++)
- {
- for(int j = 0; j < col; ++j)
- {
- if(arr[i*col+j] != invalid)// 将有效值存储在一个一维数组中
- _sm.push_back(Trituple(i,j,arr[i*col+j]));// 将三元组的无名对象 push 进去
- }
- }
- }
- // 访问稀疏矩阵中 row 行 col 中的元素
- T& Acess(int row, int col)
- {
- //1,
- /*for(int idx = 0; idx < _sm.size(); idx++)// 遍历一遍
- {
- if(_sm[idx]._row == row && _sm[idx]._col == col)// 当前行列与我们要访问那个元素行列相同时返回这个有效值
- return _sm[idx]._data;
- }
- return _invalid;*/// 否则返回无效值
- //2,
- vector>::iterator it = _sm.begin();// 定义一个迭代器, 指向起始位置
- while(it != _sm.end())// 未到最后一个元素时
- {
- if(it->_row == row && it->_col == col)// 行列相等输出值
- return it->_data;
- ++it;// 迭代器向后移动
- }
- return _invalid;
- }
- // 还原稀疏矩阵
- template
- friend ostream& operator<<(ostream& _cout, SparseMatrix& s)// 重载 <<{
- size_t idex = 0;
- for(size_t i = 0; i < s._row; i++)
- {
- for(size_t j = 0; j < s._col; j++)
- {
- if(idex < s._sm.size()/* 防止数组越界 */ && s._sm[idex]._row == i && s._sm[idex]._col == j)
- {
- _cout<
- ++idex;
- }
- else
- _cout<
- }
- _cout<
- }
- return _cout;
- }
- // 实现稀疏矩阵的逆置 时间复杂度 O(M*N)(M 为元素个数 N 为矩阵列数)
- SparseMatrix Transport()
- {
- SparseMatrix sm;
- sm._row = _col;
- sm._col = _row;
- sm._invalid = _invalid;
- for(size_t i = 0; i < _col; i++)
- {
- vector>::iterator it = _sm.begin();
- while(it != _sm.end())
- {
- if(it->_col == i)// 从原矩阵第 0 列开始, 将每列中的有效值依次放入新的稀疏矩阵
- sm._sm.push_back(Trituple (i, it->_row, it->_data));
- ++it;
- }
- }
- return sm;
- }
- // 实现稀疏矩阵的快速转置 时间复杂度 O(N)+O(M)
- SparseMatrix FastTransport()
- {
- SparseMatrix sm;
- sm._col = _row;
- sm._row = _col;
- sm._invalid = _invalid;
- sm._sm.resize(_sm.size());// 开辟空间
- //1, 统计原矩阵中每一列有多少个有效元素
- int* pCount = newint[_col];// 开辟原矩阵中列个数的空间
- memset(pCount, 0, _col*sizeof(pCount[0]));
- for(int i = 0; i < _sm.size(); i++)
- pCount[_sm[i]._col]++;
- //2, 原矩阵每一列在新矩阵中的起始位值
- int* pAddr = newint[_col];
- memset(pAddr, 0, _col*sizeof(pAddr[0]));
- for(int i = 1/* 从 1 开始, 第一个位置起始为 0 已经放入 */; i < _sm.size(); i++)
- {
- pAddr[i] = pAddr[i - 1] + pCount[i - 1];// 前一个起始位值 + 前一列有效元素个数
- }
- //3, 放置元素到新空间
- for(int i = 0; i < _sm.size(); i++)
- {
- int& addr = pAddr[_sm[i]._col];
- sm._sm[addr] = Trituple(_sm[i]._col,_sm[i]._row,_sm[i]._data);
- addr++;
- }
- return sm;
- }
- // 实现稀疏矩阵的加法操作 1
- /*SparseMatrix operator+(const SparseMatrix& sp)
- {
- int i = 0, j = 0, k = 0;
- T v;
- SparseMatrix s;
- if(this->_col != sp._col || this->_row != sp._row)
- exit(1);
- s._row = sp._row;
- s._col = sp._col;
- s._invalid = sp._invalid;
- while(i < this->_sm.size() && j < sp._sm.size())
- {
- if(this->_sm[i]._row == sp._sm[j]._row)
- {
- if(this->_sm[i]._col < sp._sm[j]._col)
- {
- s._sm.push_back(Trituple(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));
- i++;
- k++;
- }
- else if(this->_sm[i]._col > sp._sm[j]._col)
- {
- s._sm.push_back(Trituple(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));
- j++;
- k++;
- }
- else
- {
- v = this->_sm[i]._data + sp._sm[j]._data;
- if(v)
- {
- s._sm.push_back(Trituple(sp._sm[j]._row, sp._sm[j]._col, v));
- k++;
- }
- i++;
- j++;
- }
- }
- else if(this->_sm[i]._row < sp._sm[j]._row)
- {
- s._sm.push_back(Trituple(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));
- i++;
- k++;
- }
- else
- {
- s._sm.push_back(Trituple(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));
- j++;
- k++;
- }
- }
- return s;
- }*/
- // 实现稀疏矩阵的加法操作 2
- SparseMatrix operator+(const SparseMatrix& sp)
- {
- assert(_row == sp._row && _col == sp._col);// 检测两个相加的矩阵行列是否相等
- SparseMatrix ret;
- ret._row = _row;
- ret._col = _col;
- ret._invalid = _invalid;
- int iLidx = 0, iRidx = 0;// 定义两个索引
- while(iLidx < _sm.size() && iRidx < sp._sm.size())
- {
- size_t AddrLeft = _sm[iLidx]._row*_col+_sm[iLidx]._col;// 左边矩阵的起始位值
- size_t AddrRight = sp._sm[iRidx]._row*sp._col+sp._sm[iRidx]._col;// 右边矩阵起始位值
- if(AddrLeft < AddrRight)// 左 < 右, 将左边有效值放入和矩阵中, 左边的索引加加
- {
- ret._sm.push_back(Trituple(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));
- iLidx++;
- }
- elseif(AddrLeft > AddrRight)
- {
- ret._sm.push_back(Trituple(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));
- iRidx++;
- }
- else// 当左边等于右边判断相加后和是否为 0, 不为 0 放入
- {
- Trituple temp(_sm[iLidx]);
- temp._data += sp._sm[iRidx]._data;
- if(temp._data)
- {
- ret._sm.push_back(temp);
- iLidx++;
- iRidx++;
- }
- }
- }
- while(iLidx < _sm.size())// 左边还有剩余则放入剩余元素
- {
- ret._sm.push_back(Trituple(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));
- iLidx++;
- }
- while(iRidx < sp._sm.size())
- {
- ret._sm.push_back(Trituple(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));
- iRidx++;
- }
- return ret;
- }
- private:
- size_t _row;
- size_t _col;
- vector> _sm;
- T _invalid;// 无效值
- };
- int main()
- {
- int arr[6][5] = {
- {1,0,3,0,5},
- {0,0,0,0,0},
- {0,0,0,0,0},
- {1,0,3,0,5},
- {0,0,0,0,0},
- {0,0,0,0,0}};
- int arr1[6][5] = {
- {1,0,3,0,5},
- {0,0,0,0,0},
- {0,0,2,4,0},
- {1,0,3,0,5},
- {0,0,0,1,0},
- {0,0,0,0,1}};
- SparseMatrix s((int*)arr,6,5,0);
- SparseMatrix s1((int*)arr1,6,5,0);
- cout<<"访问三行四列元素"<
- cout<
- cout<
- cout<<"快速转置"<
- cout<
- cout<
- cout<<"矩阵 s:"<
- cout<
- cout<<"矩阵 s1:"<
- cout<
- cout<<"s+s1 求和:"<
- cout<
- system("pause");
- return 0;
- }
运行结果截图:
在上面的代码中用到 C++ 模板, 标准库中 vector 容器, 以及迭代器实现了一些基本的操作, 如访问稀疏矩阵中某个元素, 输出稀疏矩阵, 稀疏矩阵的转置以及快速转置还有两个稀疏矩阵的加法.
快速转置操作的基本思路是:
(1) 统计原矩阵中每一列有多少个有效元素;
(2) 原矩阵中每一列在新矩阵中的起始地址;
(3) 放置元素到新空间中.
还需注意的是, 在我们打印这个稀疏矩阵时虽然也可以直接调用访问元素的 Acess 接口, 但是每次进去之后都得遍历一遍, 时间复杂度较高, 所以我们不采取这种办法, 而是比较当前行列的值, 若相等输出有效元素, 不等则输出无效元素 0.
来源: http://stor.51cto.com/art/201808/582126.htm