服务器之家：专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++实现稀疏矩阵的压缩存储实例

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

2021-05-17 15:44z517602658 C/C++

本篇文章主要介绍了C++实现稀疏矩阵的压缩存储实例，小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
#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++实现稀疏矩阵的压缩存储实例

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

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

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

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

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

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

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

原文链接：http://blog.csdn.net/z517602658/article/details/70500188?utm_source=tuicool&utm_medium=referral

  • C++
  • 稀疏矩阵
  • 压缩存储

    • 延伸 · 阅读

    精彩推荐
    • C/C++学习C++编程的必备软件

      学习C++编程的必备软件

      本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件，这里推荐给大家...

      谢恩铭10102021-05-08
    • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

      详解c语言中的 strcpy和strncpy字符串函数使用

      strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用，感兴趣的朋友跟随小编要求看看吧...

      spring-go5642021-07-02
    • C/C++c++ 单线程实现同时监听多个端口

      c++ 单线程实现同时监听多个端口

      这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法，帮助大家更好的理解和学习使用c++，感兴趣的朋友可以了解下...

      源之缘11542021-10-27
    • C/C++C/C++经典实例之模拟计算器示例代码

      C/C++经典实例之模拟计算器示例代码

      最近在看到的一个需求，本以为比较简单，但花了不少时间，所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料，文中通过示...

      jia150610152021-06-07
    • C/C++深入理解goto语句的替代实现方式分析

      深入理解goto语句的替代实现方式分析

      本篇文章是对goto语句的替代实现方式进行了详细的分析介绍，需要的朋友参考下...

      C语言教程网7342020-12-03
    • C/C++C语言中炫酷的文件操作实例详解

      C语言中炫酷的文件操作实例详解

      内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

      针眼_6702022-01-24
    • C/C++C语言实现电脑关机程序

      C语言实现电脑关机程序

      这篇文章主要为大家详细介绍了C语言实现电脑关机程序，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      xiaocaidayong8482021-08-20
    • C/C++C++之重载 重定义与重写用法详解

      C++之重载 重定义与重写用法详解

      这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

      青山的青6062022-01-04
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 CEF2623 　 栈区 　 平滑处理 　 消息传递 　 NSString 　 右值引用 　 数据滚动 　 Simulink 　 libfreetype 　 同名 　 素数交换 　 ZOJ 　 多继承法 　 地址参数 　 Visual C++ 　 C语言教程 　 堆区 　 静态存储区 　 XML解析器 　 tinyxml 　 C++教程 　 错误调试 　 打开程序 　 WinExec 　 strcat 　 程序内部 　 颜色加亮 　 对象模型 　 内存错误 　
    © 2019-2025 服务器之家(www.zzvips.com) 版权所有关于我们联系我们版权申明网站地图