C++实现稀疏矩阵的压缩存储实例
什么是稀疏矩阵呢,就是在M*N的矩阵中,有效值的个数远小于无效值的个数,并且这些数据的分布没有规律。在压缩存储稀疏矩阵的时候我们只存储极少数的有效数据。我们在这里使用三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后次序依次存放。下面我们来看一下代码实现。
创新互联公司主营灌阳网站建设的网络公司,主营网站建设方案,成都app软件开发公司,灌阳h5小程序制作搭建,灌阳网站营销推广欢迎灌阳等地区企业咨询
#include#include #include using namespace 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< 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 = new int[_col];//开辟原矩阵中列个数的空间 memset(pCount, 0, _col*sizeof(pCount[0])); for(int i = 0; i < _sm.size(); i++) pCount[_sm[i]._col]++; //2、原矩阵每一列在新矩阵中的起始位值 int* pAddr = new int[_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++; } else if(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<<"访问三行四列元素"<
运行结果截图:
在上面的代码中用到C++模板、标准库中vector容器,以及迭代器实现了一些基本的操作,如访问稀疏矩阵中某个元素,输出稀疏矩阵、稀疏矩阵的转置以及快速转置还有两个稀疏矩阵的加法。
快速转置操作的基本思路是:
(1)统计原矩阵中每一列有多少个有效元素;
(2)原矩阵中每一列在新矩阵中的起始地址;
(3)放置元素到新空间中。
还需注意的是,在我们打印这个稀疏矩阵时虽然也可以直接调用访问元素的Acess接口,但是每次进去之后都得遍历一遍,时间复杂度较高,所以我们不采取这种办法,而是比较当前行列的值,若相等输出有效元素,不等则输出无效元素0。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持创新互联。
新闻名称:C++实现稀疏矩阵的压缩存储实例
标题链接:http://myzitong.com/article/jdcigs.html