稀疏矩阵的压缩存储
创新互联 - 成都多线机房，四川服务器租用，成都服务器租用，四川网通托管,绵阳服务器托管，德阳服务器托管，遂宁服务器托管，绵阳服务器托管，四川云主机，成都云主机，西南云主机，成都多线机房，西南服务器托管，四川/成都大带宽，机柜大带宽租用·托管，四川老牌ＩＤＣ服务商
压缩存储值存储极少数的有效数据。使用{row,col,value}三元组存储每一个有效数据，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。
压缩存储：行优先一行一行扫 有效数据存入以为矩阵_arr
列转置法 : 从前向后遍历压缩矩阵，先找列号为0的存入 转置矩阵的压缩矩阵.然后从前向后找列号为1的 。。。直到转置矩阵的压缩矩阵大小和 原矩阵的一样大 这时就找完了
时间复杂度为 O(原矩阵列数 * 压缩矩阵长度)
一次定位快速转置法：
设置两个辅助矩阵 RowCounts 和 RowStart
RowCounts 记录 原矩阵每列的有效元素元素的个数 （这里Row指的是转置矩阵的行 RowCount指的也就是转置矩阵 的 行有效元个数）
RowStart 记录的是 原矩阵 每列首个有效元素 在 转置矩阵 的压缩矩阵中的坐标 （也就是 转置矩阵 的 每行首个有效元素 在 转置矩阵 的压缩矩阵中的 坐标）
RowStart[n]可以由 RowCount[n-1]和上一个RowStart[n-1]求得 n>0
RowStart[0] = 0;
利用 RowStart 可以实现 由 原矩阵 的压缩矩阵元素 到 转置矩阵的压缩矩阵 的一次快速定位
如：
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
using namespace std;
/***
*
*稀疏矩阵
*压缩存储
*转置 （一般 和 快速转置）
*2016-4-18
*bozi
******************/
//三元组
template
struct Triple
{
size_t _row;
size_t _col;
T _value;
Triple()
{}
Triple(size_t row, size_t col, T value)
:_row(row)
,_col(col)
,_value(value)
{}
};
//稀疏矩阵
template
class SparesMatrix
{
public:
SparesMatrix();
SparesMatrix(const T* array, size_t row, size_t col, const T& invalid);
SparesMatrix
SparesMatrix
void Display() const;
protected:
vector
size_t _rowMatrix;
size_t _colMatrix;
T _invalid;//定义的无效值
};
template
SparesMatrix
{}
template
SparesMatrix
:_rowMatrix(row)
,_colMatrix(col)
,_invalid(invalid)
{
for (size_t i = 0; i < _rowMatrix; i++)
{
for (size_t j = 0; j < _colMatrix; j++)
{
if (array[i * col + j] != invalid)
{
//_array.push_back({i, j, array[i * col + j]});
_array.push_back(Triple
}
}
}
}
template
void SparesMatrix
{
size_t arr_size = _array.size();
assert(arr_size != 0);
size_t index = 0;
for (size_t i = 0; i < _rowMatrix; i++)
{
for (size_t j = 0; j < _colMatrix; j++)
{
if (index < arr_size && _array[index]._row == i && _array[index]._col == j)
{
cout<<_array[index]._value<<"";
index++;
}
else
{
cout<<_invalid<<"";
}
}
cout< } cout< } //转置 （列转置法） template SparesMatrix { size_t arr_size = _array.size(); assert(arr_size != 0); SparesMatrix ret._rowMatrix = _colMatrix; ret._colMatrix = _rowMatrix; ret._invalid = _invalid; ret._array.reserve(arr_size);//先开辟这么大的空间 提高效率 防止后面push_back()每次不够还要开辟 //在原来的 行优先的 数组_array中，每次遍历一遍，找到这次列号与对应 的列j相等的元素 将这个元素行列互换 存入ret._array //相当于 将 原数组的 行优先 转化为 列优先 //原数组的列优先 就相当于 转置后矩阵的 行优先 for (size_t j = 0; j < _colMatrix; j++) { size_t index = 0; while (index < arr_size) { if (_array[index]._col == j) { //ret._array.push_back({_array[index]._col, _array[index]._row, _array[index]._value}); ret._array.push_back(Triple } index++; } if (arr_size == ret._array.size()) { break; } } return ret; } template SparesMatrix { size_t arr_size = _array.size(); assert(arr_size > 0); size_t index = 0; SparesMatrix ret._rowMatrix = _colMatrix; ret._colMatrix = _rowMatrix; ret._invalid = _invalid; ret._array.resize(arr_size);// 调整大小 （不能用reserve(只是空间变大 但Size没变) 而resize 是调整大小 两个都变） // 两张辅助表 //RowCounts记录原矩阵 每列的 非零元素 //RowStart记录原矩阵列优先时 每列首个非零元的 坐标 //用这两张表 可以马上把 _array数组中的元素 定位到 ret._array(新表)中 int* RowCounts = new int[_colMatrix]; int* RowStart = new int[_colMatrix]; memset(RowCounts, 0, _colMatrix * sizeof(int)); memset(RowStart, 0, _colMatrix * sizeof(int)); // 初始化RowCounts for (size_t i = 0; i < arr_size; i++) { RowCounts[_array[i]._col]++;//【好方法 统计可以用到】由列号找到对应RowCounts } RowStart[0] = 0; // 初始化 RowStart（由 RowCount 求出 RowStart） for (size_t i = 1; i < _colMatrix; i++)//注意i 从1开始 { RowStart[i] = RowStart[i - 1] + RowCounts[i - 1]; } //根据RowStart 将原矩阵_array中的元素 一次 快速 的 对应到 ret.array for (size_t i = 0; i< arr_size; i++) { //ret._array[RowStart[array[i]._col]++] = {_array[i]._col, _array[i]._row, _array[i]._value}; //RowStart[_array[i]._col]++ 更新下一个元素 在 ret._array中的 位置 ret._array[RowStart[_array[i]._col]++] = Triple } delete[] RowCounts; delete[] RowStart; return ret; } void testSparseMatrix() { int array[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,}, }; SparesMatrix s1.Display(); SparesMatrix s2 = s1.Transport(); cout<<"转置后的矩阵为："< s2.Display(); SparesMatrix s3 = s1.FastTransport(); cout<<"快速转置后的矩阵为："< s3.Display(); } int main() { testSparseMatrix(); return 0; }
网站名称：稀疏矩阵-压缩存储-列转置法-一次定位快速转置法
网页URL：http://kswsj.cn/article/jcegij.html
