稀疏矩阵的列序递增法和一次定位快速转置法 _稀疏矩阵

稀疏矩阵：矩阵中大多数元素为0的矩阵，从直观上讲，当非零元素个数低于总元素的30%时，这样的矩阵为稀疏矩阵。
如：
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}};
稀疏矩阵的压缩存储：使用{row,col,value}三元组存储每一个有效数据，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。
矩阵的转置：将原矩阵的行、列对换，也就是将[i][j]和[j][i]位置上的数据对换。
稀疏矩阵的列序递增法：
按照被转置矩阵三元组表A的序列（即转置后三元组表B的行序）递增的顺序进行转置，则转置后矩阵的三元组表B恰好是以“行序为主序的”.
一次定位快速转置法：
在列转置中算法的时间浪费主要在双重循环中，要改善算法的性能，必须去掉双重循环，使得整个转置过程通过一次循环来完成。
为了使得被转置的三元组表A中元素一次定位到三元组表B中，需要计算一下以下数据：
1）,三元组表A中每一列有效值的个数，即转置后矩阵三元组表B中每一行有效值的个数。
2）,三元组表B中每一行有效值的起始位置。
[i] = [i - 1] + [i - 1];

文章插图
代码实现：
#
usingstd;
# //动态数组
//三元组
_row;
_col;
T ;
( row = 0,col = 0, const T& value = http://www.kingceram.com/post/T())
:_row(row)
, _col(col)
, (value)
{}
};
class
://非零值
(T* a = NULL,M = 0,N = 0, const T&= T())
:(M)
, (N)
, ()
for ( i = 0; i < M; ++i)
for ( j = 0; j < N; ++j)
if (a[i*N + j] != )//每行元素个数就是列的个数
t;
t._row = i;
t._col = j;
t. = a[i*N + j];
_a.(t);//在类，插入一个元素
void ()
index = 0;
for ( i = 0; i < ; ++i)
for ( j = 0; j < ; ++j)
if (index < _a.size()&& (_a[index]._row == i)&& (_a[index]._col == j))
【稀疏矩阵的列序递增法和一次定位快速转置法】cout