C++语言程序设计:稀疏矩阵的压缩存储
小标 2018-06-25 来源 : 阅读 679 评论 0

摘要:本文主要向大家介绍了C++语言程序设计的稀疏矩阵的压缩存储,通过具体的代码向大家展示,希望对大家学习C++语言程序设计有所帮助。

本文主要向大家介绍了C++语言程序设计的稀疏矩阵的压缩存储,通过具体的代码向大家展示,希望对大家学习C++语言程序设计有所帮助。

[cpp] view plain copy print?
1. #include <vector>  
2. #include <iostream>     
3. using namespace std;  
4. template<class T>  
5. class SparseMatrix  
6. {  
7. public:  
8.     // 稀疏矩阵的压缩存储  
9.     SparseMatrix(int* array, size_t row, size_t col, const T& invalid)  
10.         : _row(row)  
11.         , _col(col)  
12.         , _invalid(invalid)  
13.     {  
14.         for (size_t i = 0; i < row; ++i)  
15.         {  
16.             for (size_t j = 0; j < col; ++j)  
17.             {  
18.                 if (array[i*col+j] != invalid)  
19.                 {  
20.                     Trituple<T> a(i, j, array[i*col + j]);  
21.                     _sm.push_back(a);  
22.                 }  
23.             }  
24.         }  
25.     }  
26.   
27.     SparseMatrix()  
28.     {}  
29.   
30.     // 访问稀疏矩阵中row行col中的元素  
31.     T& Access(int row, int col)  
32.     {  
33.         ////遍历数组两种方法  
34.         ////1.for循环  
35.         ////2.迭代器  
36.         //vector<Trituple<T>>::iterator it = _sm.begin();  
37.   
38.         //while (it != _sm.end())  
39.         //{  
40.         //  if (it->_row == row&&it->_col == col)  
41.         //  {  
42.         //      return it->_data;  
43.         //  }  
44.         //  it++;  
45.         //}  
46.         //return _invalid;  
47.         for (size_t i = 0; i < _sm.size(); ++i)  
48.         {  
49.             if (_sm[i]._row == row&&_sm[i]._col == col)  
50.             {  
51.                 return _sm[i]._data;  
52.             }  
53.             return _invalid;  
54.         }  
55.     }  
56.   
57.     // 还原稀疏矩阵  
58.     template<class T>  
59.     friend ostream& operator<<(ostream& _cout, SparseMatrix<T>& s)//要申明为友元函数  
60.     {  
61.         int index = 0;  
62.         for (size_t i = 0; i < s._row; ++i)  
63.         {  
64.             for (size_t j = 0; j < s._col; ++j)  
65.             {  
66.                 if (index<s._sm.size() && i == s._sm[index]._row&&j == s._sm[index]._col) 
67.                 {  
68.                     _cout << s._sm[index++]._data << " ";  
69.                 }  
70.                 else  
71.                 {  
72.                     _cout << s._invalid << " ";  
73.                 }  
74.             }  
75.             _cout << endl;  
76.         }  
77.         return _cout;  
78.     }  
79.   
80.     // 实现稀疏矩阵的逆置,并给出时间复杂度  
81.     //直接存储是有问题的,打印是按照行优先打印存储也要行优先存储  
82.     SparseMatrix<T> Transprot()  
83.     {  
84.         SparseMatrix<T> sm;//定义一个逆转后的结构体  
85.         sm._col = _row;  
86.         sm._row = _col;  
87.         sm._invalid = _invalid;  
88.         /*使用迭代器*/  
89.         //for (int i = 0; i < _col; ++i)  
90.         //{  
91.         //  vector<Trituple<T>>::iterator it = _sm.begin();  
92.         //  while (it != _sm.end())  
93.         //  {  
94.         //      if (i == it->_col)  
95.         //      {  
96.         //          sm._sm.push_back(Trituple<T>(it->_col, it->_row, it->_data));  
97.         //      }  
98.         //      it++;  
99.   
100.         //  }  
101.         //}  
102.         //return sm;  
103.         //时间复杂度O(M*N)  
104.         for (size_t i = 0; i < _col; ++i)  
105.         {  
106.             size_t index = 0;  
107.             while (index < _sm.size())  
108.             {  
109.                 if (_sm[index]._col == i)  
110.                 {  
111.                     //三元组tmp存入满足下表i的元素  
112.                     Trituple<T> tmp(_sm[index]._col, _sm[index]._row, _sm[index]._data); 
113.                     sm._sm.push_back(tmp);  
114.                 }  
115.                 ++index;//此处要++index而不是index++  
116.             }  
117.               
118.         }  
119.         return sm;  
120.     }  
121.   
122.     // 实现稀疏矩阵的快速逆置,并给出时间复杂度  
123.     SparseMatrix<T> FastTransprot()  
124.     {  
125.         SparseMatrix<T> sm;//定义一个逆转后的结构体  
126.         sm._col = _row;  
127.         sm._row = _col;  
128.         sm._invalid = _invalid;  
129.         sm._sm.reserve(_sm.size());//开辟有效元素个空间  
130.   
131.         //1、统计原矩阵中每一列有多少个有效元素  
132.         int* pCount = new int[_col];  
133.         memset(pCount, 0, _col*sizeof(pCount[0]));  
134.         for (int i = 1; i < _sm.size(); ++i)  
135.         {  
136.             pCount[_sm[i]._col]++;  
137.         }  
138.   
139.         //2、原矩阵的每一列在新矩阵中的起始位置  
140.         int* pAddr = new int[_col];  
141.         memset(pAddr, 0, _col*sizeof(pAddr[0]));  
142.         for (int j = 1; j < _col; ++j)  
143.         {  
144.             pAddr[j] = pAddr[j - 1] + pCount[j - 1];  
145.         }  
146.         //3、放置元素到新的空间  
147.         for (int i = 0; i < _sm.size(); ++i)  
148.         {  
149.             //Trituple<T> t(_sm[i]._col, _sm[i]._row, _sm[i]._data);  
150.             //sm._sm[pAddr[_sm[i]._col]] = t;  
151.             //pAddr[_sm[i]._col] ++;  
152.             int & addr = pAddr[_sm[i]._col];  
153.             sm._sm[addr] = Trituple<T>(_sm[i]._col, _sm[i]._row, _sm[i]._data);  
154.             addr++;  
155.         }  
156.   
157.         return sm;  
158.     }  
159.   
160.     //  // 实现稀疏矩阵的加法操作  
161.     //SparseMatrix<T> operator+(const SparseMatrix<T>& sp);  
162.   
163.     //三元组  
164.     template<class T>  
165.     struct Trituple  
166.     {  
167.         Trituple(size_t row, size_t col, const T& data)  
168.             : _row(row)  
169.             , _col(col)  
170.             , _data(data)  
171.         {}  
172.   
173.         Trituple()//无参数构造函数  
174.         {}  
175.   
176.         size_t _row;  
177.         size_t _col;  
178.         T _data;  
179.     };  
180. private:  
181.     vector<Trituple<T>> _sm;  
182.     size_t _row;  
183.     size_t _col;  
184.     T _invalid;  
185. };  
186. void TestSparseMatrix()  
187. {  
188.     int array[6][5] =  
189.     {   
190.         { 1, 0, 3, 0, 5 },  
191.         { 0, 0, 0, 0, 0 },  
192.         { 0, 0, 0, 0, 0 },  
193.         { 2, 0, 4, 0, 6 },  
194.         { 0, 0, 0, 0, 0 },  
195.         { 0, 0, 0, 0, 0 } };  
196.     SparseMatrix<int> sp((int*)array, sizeof(array) / sizeof(array[0]), sizeof(array[0]) / sizeof(array[0][0]), 0);  
197.   
198.     cout << sp << endl;  
199.     cout << endl;  
200.   
201.     SparseMatrix<int> sp1 = sp.Transprot();  
202.   
203.     cout << sp1 << endl;  
204.   
205.     SparseMatrix<int> sp2 = sp.FastTransprot();  
206.       
207.     cout << sp2 << endl;  
208. }  
209. int main()  
210. {  
211.     TestSparseMatrix();  
212.     system("pause");  
213.     return 0;  
214. }

以上就介绍了C/C+的相关知识,希望对C/C+有兴趣的朋友有所帮助。了解更多内容,请关注职坐标编程语言C/C+频道!


本文由 @小标 发布于职坐标。未经许可,禁止转载。
喜欢 | 1 不喜欢 | 0
看完这篇文章有何感觉?已经有1人表态,100%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:z_zhizuobiao
小职老师的微信号:z_zhizuobiao

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    

©2015 www.zhizuobiao.com All Rights Reserved

208小时内训课程