C++实现稀疏矩阵的压缩存储实例

什么是稀疏矩阵呢，就是在M*N的矩阵中，有效值的个数远小于无效值的个数，并且这些数据的分布没有规律。在压缩存储稀疏矩阵的时候我们只存储极少数的有效数据。我们在这里使用三元组存储每一个有效数据，三元组按原矩阵中的位置，以行优先级先后次序依次存放。下面我们来看一下代码实现。

#include<iostream> 
#include<vector> 
#include<assert.h> 
using namespace std; 
 
template<class T> 
class SparseMatrix 
{ 
  //三元组 
  template<class T> 
  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<T>(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<Trituple<T>>::iterator it = _sm.begin();//定义一个迭代器,指向起始位置 
    while(it != _sm.end())//未到最后一个元素时 
    { 
      if(it->_row == row && it->_col == col)//行列相等输出值 
        return it->_data; 
      ++it;//迭代器向后移动 
    } 
    return _invalid; 
  } 
  //还原稀疏矩阵 
  template<typename T> 
  friend ostream& operator<<(ostream& _cout, SparseMatrix<T>& 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<<s._sm[idex]._data<<" "; 
          ++idex; 
        } 
        else 
          _cout<<s._invalid<<" "; 
         
      } 
      _cout<<endl; 
    } 
    return _cout; 
  } 
  //实现稀疏矩阵的逆置 时间复杂度O(M*N)(M为元素个数N为矩阵列数) 
  SparseMatrix<T> Transport() 
  { 
    SparseMatrix<T> sm; 
    sm._row = _col; 
    sm._col = _row; 
    sm._invalid = _invalid; 
    for(size_t i = 0; i < _col; i++) 
    { 
      vector<Trituple<T>>::iterator it = _sm.begin(); 
      while(it != _sm.end()) 
      { 
        if(it->_col == i)//从原矩阵第0列开始，将每列中的有效值依次放入新的稀疏矩阵 
          sm._sm.push_back(Trituple<T> (i, it->_row, it->_data)); 
        ++it; 
      } 
    } 
    return sm; 
  } 
  //实现稀疏矩阵的快速转置 时间复杂度O(N)+O(M) 
  SparseMatrix<T> FastTransport() 
  { 
    SparseMatrix<T> 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<T>(_sm[i]._col,_sm[i]._row,_sm[i]._data); 
      addr++; 
    } 
    return sm; 
  } 
  //实现稀疏矩阵的加法操作1 
  /*SparseMatrix<T> operator+(const SparseMatrix<T>& sp) 
  { 
    int i = 0, j = 0, k = 0; 
    T v; 
    SparseMatrix<T> 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<T>(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<T>(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<T>(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<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data)); 
        i++; 
        k++; 
      } 
      else 
      { 
        s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data)); 
        j++; 
        k++; 
      } 
    } 
    return s; 
  }*/ 
  //实现稀疏矩阵的加法操作2 
  SparseMatrix<T> operator+(const SparseMatrix<T>& sp) 
  { 
    assert(_row == sp._row && _col == sp._col);//检测两个相加的矩阵行列是否相等 
    SparseMatrix<T> 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<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data)); 
        iLidx++; 
      } 
      else if(AddrLeft > AddrRight) 
      { 
        ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data)); 
        iRidx++; 
      } 
      else//当左边等于右边判断相加后和是否为0，不为0放入 
      { 
        Trituple<T> 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<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data)); 
      iLidx++; 
    } 
    while(iRidx < sp._sm.size()) 
    { 
      ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data)); 
      iRidx++; 
    } 
    return ret; 
  } 
private: 
  size_t _row; 
  size_t _col; 
  vector<Trituple<T>> _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<int> s((int*)arr,6,5,0); 
  SparseMatrix<int> s1((int*)arr1,6,5,0); 
  cout<<"访问三行四列元素"<<endl; 
  cout<<s.Acess(3,4)<<endl; 
  cout<<s<<endl; 
  cout<<"快速转置"<<endl; 
  cout<<s.FastTransport(); 
  cout<<endl; 
  cout<<"矩阵s："<<endl; 
  cout<<s<<endl; 
  cout<<"矩阵s1："<<endl; 
  cout<<s1<<endl; 
  cout<<"s+s1求和："<<endl; 
  cout<<s1+s<<endl; 
  system("pause"); 
  return 0; 
} 

运行结果截图：

在上面的代码中用到C++模板、标准库中vector容器，以及迭代器实现了一些基本的操作，如访问稀疏矩阵中某个元素，输出稀疏矩阵、稀疏矩阵的转置以及快速转置还有两个稀疏矩阵的加法。

快速转置操作的基本思路是：

（1）统计原矩阵中每一列有多少个有效元素；

（2）原矩阵中每一列在新矩阵中的起始地址；

（3）放置元素到新空间中。

还需注意的是，在我们打印这个稀疏矩阵时虽然也可以直接调用访问元素的Acess接口，但是每次进去之后都得遍历一遍，时间复杂度较高，所以我们不采取这种办法，而是比较当前行列的值，若相等输出有效元素，不等则输出无效元素0。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

# C++  # 稀疏矩阵压缩存储  # C++稀疏矩阵存储  # C++稀疏矩阵存储方法  # C++稀疏矩阵的各种基本运算并实现加法乘法  # C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储  # C++ 实现稀疏矩阵的压缩存储的实例  # C++超详细讲解稀疏矩阵  # 有效值  # 遍历  # 一遍  # 迭代  # 到新  # 有多少个  # 的是  # 在这里  # 较高  # 可以直接  # 不为  # 在上面  # 都得  # 还需  # 未到  # 大家多多  # 库中  # 加加  # 按原  # 组中 

相关文章： c# F# 的 MailboxProcessor 和 C# 的 Actor 模型  网站网页制作电话怎么打,怎样安装和使用钉钉软件免费打电话？  如何通过主机屋免费建站教程十分钟搭建网站？  专业型网站制作公司有哪些,我设计专业的，谁给推荐几个设计师兼职类的网站？  如何在IIS服务器上快速部署高效网站？  如何在Golang中处理模块冲突_解决依赖版本不兼容问题  C++用Dijkstra(迪杰斯特拉)算法求最短路径  如何正确下载安装西数主机建站助手？  如何用wdcp快速搭建高效网站？  高防网站服务器：DDoS防御与BGP线路的AI智能防护方案  建站VPS配置与SEO优化指南：关键词排名提升策略  如何使用Golang table-driven基准测试_多组数据测量函数效率  如何选择建站程序？包含哪些必备功能与类型？  php json中文编码为null的解决办法  建站之星如何实现五合一智能建站与营销推广？  网站制作模板下载什么软件,ppt模板免费下载网站？  猪八戒网站制作视频,开发一个猪八戒网站，大约需要多少？或者自己请程序员，需要什么程序员，多少程序员能完成？  建站之星会员如何解锁更多建站功能？  广东专业制作网站有哪些,广东省能源集团有限公司官网？  网站专业制作公司,网站编辑是做什么的？好做吗？工作前景如何？  道歉网站制作流程,世纪佳缘致歉小吴事件，相亲网站身份信息伪造该如何稽查？  css网站制作参考文献有哪些,易聊怎么注册？  北京营销型网站制作公司,可以用python做一个营销推广网站吗？  存储型VPS适合搭建中小型网站吗？  制作网页的网站有哪些,电脑上怎么做网页？  网站制作和推广的区别,想自己建立一个网站做推广，有什么快捷方法马上做好一个网站？  建站之星导航如何优化提升用户体验？  如何快速上传自定义模板至建站之星？  零基础网站服务器架设实战：轻量应用与域名解析配置指南  如何挑选优质建站一级代理提升网站排名？  5种Android数据存储方式汇总  创业网站制作流程,创业网站可靠吗？  广州网站制作公司哪家好一点,广州欧莱雅百库网络科技有限公司官网？  建站主机解析：虚拟主机配置与服务器选择指南  公司网站设计制作厂家,怎么创建自己的一个网站？  ,南京靠谱的征婚网站？  C#如何使用XPathNavigator高效查询XML  活动邀请函制作网站有哪些,活动邀请函文案？  Thinkphp 中 distinct 的用法解析  如何在阿里云完成域名注册与建站？  网站制作难吗安全吗,做一个网站需要多久时间？  Swift开发中switch语句值绑定模式  外贸公司网站制作哪家好,maersk船公司官网？  网站专业制作公司有哪些,做一个公司网站要多少钱？  如何在阿里云部署织梦网站？  高防服务器租用首荐平台，企业级优惠套餐快速部署  如何通过宝塔面板实现本地网站访问？  深圳企业网站制作设计,在深圳如何网上全流程注册公司？  宁波自助建站系统如何快速打造专业企业网站？  C#如何序列化对象为XML XmlSerializer用法