稀疏矩阵：矩阵中大多数元素为0的矩阵（本文以行序为主序）
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名与空间、
雅安服务器托管、营销软件、网站建设、
晋中网站维护、网站推广。
稀疏矩阵的三元组表述法：
类型结构：
template
struct Triple
{
int _row;
int _col;
T _value;
};
template
class SparseMatrix
{
public:
SparseMatrix::SparseMatrix();
SparseMatrix(const T* array, size_t row, size_t col, const T& invalid);
~SparseMatrix();
void Display()const;
SparseMatrix Transport()const;
SparseMatrix FastTransport()const;
protected:
vector> _array;
size_t _rowCount;
size_t _colCount;
T _invalid;
};
代码实现压缩存储：
//稀疏矩阵
template
SparseMatrix::SparseMatrix(){}
template
SparseMatrix::SparseMatrix(const T* array, size_t row, size_t col, const T& invalid)
:_rowCount(row), _colCount(col), _invalid(invalid)
{
assert(array);
for (size_t i = 0; i < row; ++i)
{
for (size_t j = 0; j < col; ++j)
{
if (array[i*col + j] != invalid)
{
this->_array.push_back({ i, j, array[i*col + j] });
}
}
}
}
template
SparseMatrix::~SparseMatrix()
{}
template
void SparseMatrix::Display()const
{
size_t size = this->_array.size();
size_t iCount = 0;
for (size_t i = 0; i < this->_rowCount; ++i)
{
for (size_t j = 0; j < this->_colCount; ++j)
{
if (iCount < size && i == this->_array[iCount]._row && j == this->_array[iCount]._col)
{
cout << this->_array[iCount]._value << " ";
++iCount;
}
else
{
cout << this->_invalid << " ";
}
}
cout << endl;
}
}
稀疏矩阵的转置：
1）列序递增转置法：找出第i行全部元素：从头到尾扫描三元组表A，找出其中所有_col==i的三元组，转置后放入三元组表B中。代码实现如下：
template
SparseMatrix SparseMatrix::Transport()const
{
SparseMatrix ret;
ret._rowCount = this->_colCount;
ret._colCount = this->_rowCount;
ret._invalid = this->_invalid;
size_t size = this->_array.size();
for (size_t col = 0; col < this->_colCount; ++col)
{
for (size_t iCount = 0; iCount < size; ++iCount)
{
if (this->_array[iCount]._col == col)
{
ret._array.push_back({ this->_array[iCount]._col, this->_array[iCount]._row,
this->_array[iCount]._value });
}
}
}
return ret;
}
2）一次定位快速转置法
在方法1中为了使转置后矩阵的三元组表B仍按行序递增存放，必须多次扫描被转置的矩阵的三元组表A。为了能将被转置三元组表A的元素一次定位到三元组B的正确位置上，需要预先计算以下数据：
i)待转置矩阵三元组表A每一列中非0元素的总个数，即转置后矩阵三元组元素B的每一行的非0元素总个数
ii)待转置矩阵每一列中第一个非0元素在三元组表B中的正确位置，即转置后矩阵每一行中第一个非0元素在三元组B中的正确位置
为此，需要设两个数组分别为num[] 和 pos[] ,其中num[col]用来存放三元组表A第col列中非0元素元素总个数，pos[col]用来存放转置前三元组表A中第col列中第一个非0元素在三元组表B中的存储位置。
num[col]的计算方法：将三元组表A扫描一遍，对于其中列号为col的元素，给相应的num数组中下标为col的元素加1.
pos[col]的计算方法：
i)pos[0] = 0,表示三元组表A中，列值为0的第一个非0元素在三元组表B中的下标值。
ii)pos[col] = pos[col - 1] + num[col - 1],其中1<=coleg:
0 1 9 0 0 0 0
0 0 0 0 0 0 0
3 0 0 0 0 4 0
0 0 2 0 0 0 0
0 8 0 0 0 0 0
5 0 0 7 0 0 0
| col | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| num[col] | 2 | 2 | 2 | 1 | 0 | 1 | 0 |
| pos[col] | 0 | 2 | 4 | 6 | 7 | 7 | 8 |
代码实现：
template
SparseMatrix SparseMatrix::Transport()const
{
SparseMatrix ret;
ret._rowCount = this->_colCount;
ret._colCount = this->_rowCount;
ret._invalid = this->_invalid;
size_t size = this->_array.size();
for (size_t col = 0; col < this->_colCount; ++col)
{
for (size_t iCount = 0; iCount < size; ++iCount)
{
if (this->_array[iCount]._col == col)
{
ret._array.push_back({ this->_array[iCount]._col, this->_array[iCount]._row,
this->_array[iCount]._value });
}
}
}
return ret;
}
template
SparseMatrix SparseMatrix::FastTransport()const
{
SparseMatrix ret;
ret._rowCount = this->_colCount;
ret._colCount = this->_rowCount;
ret._invalid = this->_invalid;
size_t size = this->_array.size();
ret._array.resize(size);
vector num(this->_colCount);
vector pos(this->_colCount); //pos[i] = pos[i-1]+num[i-1] i>0
for (size_t i = 0; i < size; ++i)
{
++num[this->_array[i]._col];
}
for (size_t col = 1; col < this->_colCount; ++col)
{
pos[col] = pos[col - 1] + num[col - 1];
}
for (size_t i = 0; i < size; ++i)
{
ret._array[pos[this->_array[i]._col]++] = { this->_array[i]._col, this->_array[i]._row, this->_array[i]._value };
}
return ret;
}
运行结果：
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
分享文章：稀疏矩阵的压缩存储与转置-创新互联
标题来源：http://cdkjz.cn/article/csggps.html
