在普遍的印象中，矩阵是由方括号围住，同时各个坐标的数字整齐的排列着，
数据结构——稀疏矩阵
。如下图所示：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)
0449
100a
201b
303c
420d
521e
623f
730g
831h
933i
通过这种方式来存储，大大节约了空间，但同时带来了一定的麻烦（主要是矩阵运算时，不太好理解）。
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,b_value = b[0].value; if(a_col != b_row) { std::cout << "error"; return; } //c矩阵为b的转置矩阵 //先获取结果矩阵最大长度 item* c = new item[b_value+1]; transpose(b,c); //下面所述的row表示结果数组的行标，col表示结果数组的列标 int row = a[1].row; //结果矩阵的行标row一定是从这里开始的 int col = 0; //列标col暂置为0 //_begin用于标记row行初始位置， int _begin=1; //如：循环时，前面row行已经处理完了，这时a数组的前面row行对于后续计算也就没意义了，这里_begin的作用就是用于记录a数组的row+1行位置作用 int sum,num=1; //sum存储的结果数组（row,col）处的value值，num用于存储结果数组的下标 for(int i=1;i<=a_value;) //从a数组1开始遍历，直至a数组尾 { col = c[1].row; //由于c为b数组转置矩阵，其行标就是结果数组的列标col，由矩阵的乘法性质知，每次col都从c[1].row开始的，故每次循环开始时，要重置下。 sum = 0; for(int j=1;j<=b_value+1;) //此处value+1的作用是应对这种情况：a数组未遍历完，而j值已经取遍c的下标，而j++的作用导致超出c数组范围，可能会越界，而下面的第一个if作用也正是处理这种状况 { if(j>b_value) //j值已经超出了b_value，意味着数组已被完全遍历，说明当前行row的值已经完全找出了。 { result[num].row = row; //这时我们就可以把之前记录的sum填入结果数组中，同时下标num要自加1 result[num].col = col; result[num].value = sum; num++; break; //当前行的所有非0值均已找出，可以跳出该循环了 } if(i>a_value||a[i].row != row) //1、此时a矩阵该行已迭代完，没有可算的值2、当前row行已经迭代完，若继续迭代，行值就变了， { result[num].row = row; //所以此时也可以将sum值存入结果数组中，同时下标num要自加1. result[num].col = col; result[num].value = sum; num++; i = _begin; //为了计算当前行的下一个（下一个col值）非零值，i要为该行的起始位置开始遍历 for(;j<=b_value&&c[j].row==col;j++);//主要作用为了将当前行值为col的全部遍历过，但不作任何其他处理，然后进入下一col值 if(j>b_value)break; //可能出现j的值比b_value大，就要跳出循环了。 col = c[j].row; //将列值置为下一个col值 } else if(c[j].row != col) //由于c数组的row表示结果数值的列值，该条件说明当前列值与c数组的row值不等，意味着结果数组的列值应该下移了。 { result[num].row = row; //处理方式与上述有些类似 result[num].col = col; result[num].value = sum; num++; i = _begin; col = c[j].row; } else if(a[i].col < c[j].col) //下面3个条件很好理解。 { i++; } else if(a[i].col == c[j].col) { sum += a[i++].value * c[j++].value; } else if(a[i].col > c[j].col) { j++; } } for(;i<=a_value&&a[i].row == row;i++); //通过递归，将当前行迭代，直到进行下一个row行值。 if(i>a_value) //如果i的值超出最大值，说明已经算完所有行了。 break; //终止循环 row = a[i].row; _begin = i; //同时记下此时row对应的开始下标。 } result[0].row = a_row; result[0].col = b_col; result[0].value = num-1; delete[] c; }电脑资料
《数据结构——稀疏矩阵》(http://meiwen.anslib.com)。