C++数据结构之对称矩阵及稀疏矩阵的压缩存储
对称矩阵及稀疏矩阵的压缩存储
创新互联公司是一家专业提供五龙口企业网站建设,专注与成都网站设计、成都网站建设、H5开发、小程序制作等业务。10年已为五龙口众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。
1.稀疏矩阵
对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）。
人们无法给出稀疏矩阵的确切定义，一般都只是凭个人的直觉来理解这个概念，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素没有分布规律。
实现代码：
//稀疏矩阵及其压缩存储
#pragma once
#include
#include
using namespace std;
template
struct Triple
{
size_t _r;
size_t _c;
T _value;
Triple(size_t row = 0, size_t col = 0, const T& value = T())
:_r(row)
,_c(col)
,_value(value)
{}
};
template
class SparseMatrix
{
public:
SparseMatrix()
:_row(0)
,_col(0)
,_illegal(T())
{}
SparseMatrix(T* arr, size_t row, size_t col, const T& illegal)
:_row(row)
,_col(col)
,_illegal(illegal)
{
for(size_t i = 0; i t(i,j,arr[i*col+j]);
_matrix.push_back(t);
}
}
}
}
void Display()
{
vector >::iterator iter;
iter = _matrix.begin();
for(size_t i = 0; i<_row; ++i)
{
for(size_t j = 0; j<_col; ++j)
{
if(iter!=_matrix.end()
&&iter->_r == i
&&iter->_c == j)
{
cout << iter->_value <<" ";
++iter;
}
else
{
cout << _illegal <<" ";
}
}
cout << endl;
}
cout << endl;
}
//普通转置(行优先存储)
//列变行，从0列开始，将列数据一个一个放进转置矩阵
SparseMatrix Transpose()
{
SparseMatrix tm;
tm._row = _col;
tm._col = _row;
tm._illegal = _illegal;
tm._matrix.reserve(_matrix.size());
for(size_t i = 0; i<_col; ++i)
{
size_t index = 0;
while(index < _matrix.size())
{
if(_matrix[index]._c == i)
{
Triple t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value);
tm._matrix.push_back(t);
}
++index;
}
}
return tm;
}
SparseMatrix FastTranspose()
{
SparseMatrix tm;
tm._row = _col;
tm._col = _row;
tm._illegal = _illegal;
tm._matrix.resize(_matrix.size());
int* count = new int[_col];//记录每行的元素个数
memset(count, 0, sizeof(int)*_col);
int* start = new int[_col];//转置矩阵中元素的位置
start[0] = 0;
size_t index = 0;
while(index < _matrix.size())
{
count[_matrix[index]._c]++;
++index;
}
for(size_t i=1; i<_col; ++i)
{
start[i] = start[i-1] + count[i-1];
}
index = 0;
while(index < _matrix.size())
{
Triple t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value);
tm._matrix[start[_matrix[index]._c]++] = t; //核心代码
++index;
}
delete[] count;
delete[] start;
return tm;
}
protected:
vector > _matrix;
size_t _row;
size_t _col;
T _illegal;
};
2.对称矩阵
实现代码：
//对称矩阵及其压缩存储
#pragma once
#include
using namespace std;
template
class SymmetricMatrix
{
public:
SymmetricMatrix(T* arr, size_t n)
:_n(n)
,_matrix(new T[n*(n+1)/2])
{
size_t index = 0;
for(size_t i = 0; i= j)
{
_matrix[index] = arr[i*n+j];
++index;
}
else
{
continue;
}
}
}
}
void Display()
{
for(size_t i =0; i < _n; ++i)
{
for(size_t j = 0; j < _n; ++j)
{
/* if(i
以上就是C++ 数据结构实现稀疏矩阵与对称矩阵，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
当前文章：C++数据结构之对称矩阵及稀疏矩阵的压缩存储
转载来源：
http://kswjz.com/article/gpjjcd.html
扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
