clip_image001
看到图示后，第一反应当然是用一个二维数组来表示，即简单又易懂。但我们又会碰到下图所示矩阵：
clip_image001[8]
看看这个矩阵，0好多啊（我们称之为稀疏矩阵），若用二维数组来表示，会重复存储了很多个0了，这样浪费了空间。
故要采取一种特殊的方式来存储这样的矩阵，这里就提出了数组的方式来存储这样的矩阵。
复制代码
typedef struct
{
int row; //行坐标
int col; //列坐标
int value; //该点的值
} item;
复制代码
这里item表示矩阵中点，那么一个稀疏矩阵（非0值的个数为num）的描述就如下：
用item[num+1]来表示一个矩阵，为啥要num+1，先作一点说明：
item数组的首值为{行数，列数，非0值个数}结构，除首值外，其余值表示的矩阵中非0值的行列坐标以及本身的值。先上个小例子，来解释下：
clip_image001[10]
已知上述矩阵非0值的个数为：16-7=9；用数组item test[9+1]来表示
数组下标(i)
行(row)
列(col)
值(value)
0
4
4
9
1
0
0
a
2
0
1
b
3
0
3
c
4
2
0
d
5
2
1
e
6
2
3
f
7
3
0
g
8
3
1
h
9
3
3
i
通过这种方式来存储，大大节约了空间，但同时带来了一定的麻烦（主要是矩阵运算时，不太好理解）。
1、矩阵转置运算
矩阵转置：即把矩阵行值变列值，列值变成行值，对于二维数组而言，就是将二维数组的下标进行互换即可，原始：a[i][j]=value；转换后：a[j][i]=value；
但转置对于用数组表示的矩阵来说，理解起来也简单，即将行列互换。
复制代码
void transpose1(item* a,item* b)
{
int col = a[0].row;
int row = a[0].col;
int value = a[0].value;
b[0].row = row; //先将b[0]的值填充好
b[0].col = col;
b[0].value = value;
int num=1; //num表示b矩阵的数组下标，因为首值已经设好，故从1开始
for(int i=0;i
{
for(int j=1;j<=value;j++) //数组下标由小到大遍历
{
if(a[j].col == i) //当a矩阵的列标与b的行标相等，则做如下处理
{
b[num].col = a[j].row; //从这可以看出，b的列标在同行标下，是从小到大排列的。
b[num].row = i;
b[num].value = a[j].value;
num++;
}
}
}
}
复制代码
从代码中，我们可以轻松看出，时间复杂度是比较大的，两层循环的缘故；O(row*(value))；若value为row*col的话，这个开销就非常大了。
书中提出了快速的转置的方式，简要描述如下：
a、首先找出转置后的矩阵，每行非0的个数。（通过遍历原始数组，对col的值进行次数统计）
b、获取每行非0值的起始数组下标；（已经0行的起始数组下标为1，而1行的起始数组下标就是0行的起始下标+0行中非0值的个数，同理下推）
c、遍历原始数组（从下标1开始），首先获得结果数组的下标，由原始数组的列标（结果数组行标）根据b步骤来判断循环的当前下标应该在结果数组的什么位置。
说的好绕口，看程序。
复制代码
void transpose(item* a,item* b)//a为原始矩阵，b为转置后的矩阵。
{
int row = a[0].col;
int col = a[0].row;
int value = a[0].value;
b[0].row = row;
b[0].col = col;
b[0].value = value;
//先统计下各行非0的个数
//先初始个存储各行非0的数组
int* p = new int[row];
for(int i=0;i<=row;i++)
{
p[i]=0;
}
for(int i=1;i<=value;i++)
{
p[a[i].col]++;
}
//推算每行的起始点
int* start = new int[row];
start[0] = 1;
for(int i=1;i
{
start[i] = start[i-1]+p[i-1];
}
for(int i=1;i<=value;i++)
{
int j = start[a[i].col]++;//用于获取数组下标，注意下标右移
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].value = a[i].value;
}
delete[] start;
delete[] p;
}
复制代码
到此，我们也就完成了转置运算。
2、矩阵的乘法
在上一篇中，讲述过了矩阵乘法，这里就不做赘述了
对于稀疏矩阵来说，乘法相对来说，处理起来比较烦锁，并不像二维数组处理起来那么无脑。因为并不能从两个矩阵的非零值个数中，直接获得乘积后的结果矩阵的非零值个数。例如：
clip_image001[12]
可以看出来，处理还是比较复杂的。
复制代码
void mult(item* a,item* b,item* result)
{
//根据矩阵相乘的具体算法步骤，即结果矩阵的（i,j）为a矩阵的i行与b矩阵的j列对应相乘，
//那么我们可以做一个转换，可以看成a矩阵的i行与b矩阵的转置后的j行对应相乘，
//对应的根据是：a矩阵的列数与b转置后的矩阵的列数相对应
//首先对右边的矩阵进行转置操作
int a_row = a[0].row,a_col = a[0].col,a_value = a[0].value;
int b_row = b[0].row,b_col = b[0].col,