本片博客讨论的特殊矩阵包括两部分：
成都创新互联公司主要从事成都做网站、成都网站建设、成都外贸网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务宝应,10多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792
（1）元素分布有特殊规律的矩阵，寻找规律对应的公式实现压缩存储。如：对称矩阵。
（2）非零元素很少的稀疏矩阵，可采用只存储非零元素的方式实现压缩存储。
首先呢，先来讨论下对称矩阵。
所谓对称矩阵呢，就是行和列相同，上矩阵和下矩阵对称。还是看图吧，一目了然。
看此矩阵，若要将其存储，会浪费空间。就对称这一特征来说，可只存储其上矩阵或者下矩阵。就以存储下矩阵为例。
在此程序中需要注意:
(1)若矩阵为N*N，则需要为其开辟N*（N+1）/2大的数组。
(2)矩阵i行j列的元素对应数组的下标为i*(i+1)/2+j的元素。
即：SymmetricMatrix[i][j] ==> Array[i*(i+1)/2+j]。
代码实现：
template
class SymmetricMatrix
{
public: //声明
SymmetricMatrix(T* a,size_t size);
~SymmetricMatrix();
T& Access(size_t i,size_t j);
void Display();
protected:
T* _a;//数组
size_t _size;//压缩矩阵的下标
size_t _n;//方阵的行，列
};
//函数实现
template
SymmetricMatrix::SymmetricMatrix(T* a,size_t size)
:_a(new T[size*(size+1)/2])//为_a开辟空间
,_size(size*(size+1)/2)//下标
,_n(size)//行，列
{
size_t _index = 0;
for(size_t i=0;i<_n;i++)
{
for(size_t j=0;j<_n;j++)
{
if(i>=j)
{
_a[_index++] = a[i*_n+j];//下矩阵
}
else//上矩阵不存储
break;
}
}
}
template
SymmetricMatrix::~SymmetricMatrix()
{
if(_a != NULL)
{
delete[] _a;
_a = NULL;
_size = 0;
}
}
template
T& SymmetricMatrix::Access(size_t i, size_t j)//(i,j)位置上的元素
{
if(i
void SymmetricMatrix::Display()//打印对称矩阵
{
for(size_t i=0;i<_n;i++)
{
for(size_t j=0;j<_n;j++)
{
if(i>=j)//下矩阵
{
cout<<_a[i*(i+1)/2+j]<<" ";
}
else//上矩阵
{
cout<<_a[j*(j+1)/2+i]<<" ";
}
}
cout<测试函数：
void Test()
{
int arr[][4]={{0,1,2,3},
{1,0,4,5},
{2,4,0,6},
{3,5,6,0}};
SymmetricMatrix sm((int*)arr,4);
sm.Display();
int ret = sm.Access(2,3);
cout<测试结果：
接下来呢，我们看一下稀疏矩阵。
所谓系数矩阵呢，就是指矩阵中的大多数元素为0。当非零元素的个数低于总元素的30%时，这样的矩阵称为稀疏矩阵。如下所示：
如何存储稀疏矩阵呀，对于稀疏矩阵的存储，采取只存储非零元素的方法。由于稀疏矩阵的元素并没有规律，所以在存储元素时，还必须存储非零元素的行号和列号。这就是稀疏矩阵的三元组表示法。
三元组的结构：
template
struct Triple
{
Triple(const T& value = T(),size_t row = 0,size_t col = 0)//初始化
:_value(value)
,_row(row)
,_col(col)
{}
T _value; //值
size_t _row;//行
size_t _col;//列
}
代码实现：
template
class SpareMatrix//稀疏矩阵
{
public:
SpareMatrix();//无参构造函数
SpareMatrix(T* a,size_t m,size_t n,const T& invalue);//有参构造函数
void Display();//打印
SpareMatrix Transport();//转置
SpareMatrix FastTransport();//快速转置
protected:
vector > _a;//存储三元组的数组
size_t _rowSize;//行
size_t _colSize;//列
T _invalue;//非法值
};
template
SpareMatrix::SpareMatrix(T *a, size_t m, size_t n, const T& invalue)
:_rowSize(m)
,_colSize(n)
,_invalue(invalue)
{
for(size_t i=0;i(a[i*n+j],i,j));
}
}
}
}
template
SpareMatrix::SpareMatrix()
:_rowSize(0)
,_colSize(0)
{}
template
void SpareMatrix::Display()
{
size_t index = 0;
for(size_t i=0;i<_rowSize;i++)
{
for(size_t j=0;j<_colSize;j++)
{
if(index<_a.size()&&(_a[index]._row == i)&&(_a[index]._col == j))
{
cout<<_a[index]._value<<" ";
++index;
}
else
{
cout<<_invalue<<" ";
}
}
cout<
SpareMatrix SpareMatrix::Transport()//从三元数组上入手，以列为主，重新存储
{
SpareMatrix tmp;
tmp._rowSize = _colSize;//行
tmp._colSize = _rowSize;//列
tmp._invalue = _invalue;
Triple t;
for(size_t i=0;i<_colSize;i++)
{
size_t index = 0;
while(index < _a.size())
{
if(_a[index]._col == i)
{
t._row = _a[index]._col;//交换行号，列号
t._col = _a[index]._row;
t._value = _a[index]._value;
tmp._a.push_back(t);
}
++index;
}
}
return tmp;
}
template
SpareMatrix SpareMatrix::FastTransport()//快速逆置
{
SpareMatrix tmp;
tmp._rowSize = _colSize;//行
tmp._colSize = _rowSize;//列
tmp._invalue = _invalue;
SpareMatrix rowCount = new int[tmp._rowSize];//记录每一列元素的个数
SpareMatrix rowStart = new int[tmp._rowSize];//记录元素在数组上开始的位置
memset(rowCount,0,sizeof(int)*tmp._rowSize);//初始化为0
memset(rowStart,0,sizeof(int)*tmp._rowSize);
size_t index = 0;
while(index < _a.size())//统计每一列上的元素个数
{
rowCount[_a[index]._col]++;
++index;
}
index = 0;
rowStart[0] = 0;
for(size_t i=1;i<_colSize;i++)//每个元素在数组中开始的位置
{
rowSize[i] = rowSize[i-1] + rowCount[i-1];
}
index = 0;
tmp._a.resize(_a.size());//开辟空间并默认为0
while(index < _a.size())
{
size_t rowIndex = _a[index]._col
int& start = rowStart[rowIndex];
Triple t;
t._value = _value;
t._row = col;
t._col = _row;
tmp._a[start++] = t;
}
return tmp;
}
//测试函数：
void Test()
{
int arr[4][5] = {{0,1,0,0,0},
{0,0,0,2,0},
{0,4,0,0,0},
{0,0,3,0,0}};
SpareMatrix sm((int*)arr,4,5,int());
sm.Display();
//sm.Transport((int*)arr,4,5,int());
//sm.Display(5,4);
SpareMatrix ret = sm.Transport();
ret.Display();
SpareMatrix ret1 = sm.FastTransport();
ret1.Display();
return 0;
}
测试结果：
分享标题：特殊矩阵的压缩存储
文章地址：http://cxhlcq.com/article/gpesih.html
重庆分公司
重庆分公司
