c++稀疏矩阵的压缩存储
稀疏矩阵
M*N的矩阵 其中有效值的个数远小于无效值的个数 且分布没有规律
Eg:
int array [6][5] = {{1, 0, 3, 0, 5},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{2, 0, 4, 0, 6},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}};
稀疏矩阵的压缩存储
压缩存储值存储极少数的有效数据。使用{row,col,value}//行 列 值三元组存储每一个有效 数据,三元组按原矩阵中的位置,以行优先级先后顺序依次存放。
程序代码:
#include<vector>//pushpopoperator[]和顺序表一致template<classT>structTriple//定义一个三元组可以直接访问的定义成struct{size_t_row;size_t_col;T_value;Triple(size_trow,size_tcol,constT&value):_row(row),_col(col),_value(value){}};template<classT>classSparseMatrix{public:SparseMatrix(constT*a,size_tM,size_tN,constT&invalid)//constT&invalid表示哪个是无效数据:_M(M),_N(N),invalid(invalid){for(size_ti=0;i<M;++i){for(size_tj=0;j<N;++j){if(a[i*N+j]!=invalid)//不等于无效值{Triple<T>t(i,j,a[i*N+j]);_a.push_back(t);}}}}voidDisplay(){size_tindex=0;for(size_ti=0;i<_M;++i){for(size_tj=0;j<_N;++j){if(index<_a.size()&&i==_a[index]._row&&j==_a[index]._col){cout<<_a[index].value<<"";++index;}else{cout<<_invalid<<"";}}cout<<endl;}cout<<endl;}protected://存三元组数组//Triple<T>*_a;直接用动态顺序表vector<Triple<T>>_a;size_t_M;size_t_N;T_invalid;};voidTest2(){inta[6][5]={{1,0,3,0,5},{0,0,0,0,0},{0,0,0,0,0},{2,0,4,0,6},{0,0,0,0,0},{0,0,0,0,0}};SparseMatrix<int>sm((int*)a,6,5,0);//强制转换成一维数组数组6行5列非法值0sm.Display();}#include<iostream>usingnamespacestd;#include<stdlib.h>#include"Matrix.h"intmain(){//Test1();Test2();system("pause");return0;}
运行结果:
1 0 3 0 5
0 0 0 0 0
0 0 0 0 0
2 0 4 0 6
0 0 0 0 0
0 0 0 0 0
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。