本文是关于稀疏矩阵（二维数组）压缩的问题，大多数数据结构的教材里面都是采用的3个数字来表示原数组的一个元素的方法，即该元素在原数组里的行、列和元素的值。产生如下矩阵：
-------------------
|  x  |  y  |  v  |
-------------------
|  x1 |  y1 |  v1 |      <- 矩阵1
-------------------
|  x2 |  y2 |  v2 |
-------------------
      .......

在矩阵1中，x、y分别表示原数组的行和列，v表示原数组中非零元素的个数。xi、yi、vi ( i = 1, 2, ... v )非别表示第i个非零元素所处的行、列和该元素的值。例如：
/ 0 3 0 0 0 \
| 1 0 0 2 0 |
| 0 0 0 0 0 |   <- 矩阵2
\ 0 0 0 0 4 /

经压缩后生成矩阵3

-------------------
|  4  |  5  |  4  |
-------------------
|  0  |  1  |  3  |
-------------------
|  1  |  0  |  1  |    <- 矩阵3
-------------------
|  1  |  3  |  2  |
-------------------
|  3  |  4  |  4  |
-------------------

该压缩法的缺点：
让我们来算一下，如果有这样一个矩阵，m行，n列，j个非零元素，压缩后生成的矩阵的元素个数为k，那么，上述的方法（简称：算法I）有这样的关系：
  k = 3 * j + 3
那么，很显然的，只有当 k < m * n 的时候，压缩才有意义，也就是说：
  k < m * n  =>  m * n > 3 * j + 3
也就是说，非零元素个数小于数组元素的三分之一减三个的时候 ( j < ( m * n / 3 ) - 3 ) 算法I才有效。那么，当j变大的时候，也就是说大于1/3总元素个数的时候，还能够进行压缩吗？

我这里就给出我所想出来的算法，当 j 介于 1/3 到 1/2 之间的算法（简称：算法II）。

预备知识：
其实也不是什么太深奥的知识，大家都知道的:)  算法II利用了一些C/C++的特点（因为我熟悉这两门语言，其他的我不太了解）。
1、C/C++有这样的特点，他们都把数组（一维或多维）数组当作一维的来处理。比如矩阵2，那个非零元素2，既是 "[ 1 ] [ 3 ]"，也是"[ 8 ]"。
2、C/C++不管你的数组有多少行，他只管有多少列，也就是说：一行的元素的个数，到哪里算是到了下一列。于是就有这样的定义方式：
  T array [ ] [ 2 ] = { 1, 2, 3, 4, 5, 6 };
而如果这样定义就错误了：
  T array [ 3 ] [ ] = { 1, 2, 3, 4, 5, 6 };
想一想也应该是这样，C/C++不处理溢出，所以，指针就只管往下走吧，到哪里无所谓。而如果他不知道在那里拐弯，那就不叫多维数组了吧:)

预备知识讲完了:P

下面开始算法II，或许你已经知道了我的想法：
让我们这样压缩：

-------------                          
|  x  |  y  |
-------------
|  x1 |  v1 |
-------------   <- 矩阵4
|  x2 |  v2 |
-------------
    .....

x、y表示原数组的大小和列数（也就是每行元素的个数），xi、vi ( i = 1, 2, ... j // j 是非零元素个数 ) 分别表示第i个非零元素在原矩阵等价的一维矩阵里面的位置、该元素的值。这样很拗口的解释却是不好说也不好理解，举个例子，就拿刚才的矩阵2吧，经算法II压缩，生成：

/ 0 3 0 0 0 \
| 1 0 0 2 0 |                
| 0 0 0 0 0 |   <- 矩阵2 
\ 0 0 0 0 4 /

  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19
{ 0, 3, 0, 0, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 }
-------------
|  20 |  5  |
-------------
|  1  |  3  |
-------------
|  5  |  1  |   <- 矩阵5
-------------
|  8  |  2  |
-------------
|  19 |  4  |
-------------

让我们来算一下，如果有这样一个矩阵，m行，n列，j个非零元素，压缩后生成的矩阵的元素个数为k，那么，上述的方法（简称：算法II）有这样的关系：
  k = 2 * j + 2
则：
  k < m * n  =>  j < ( m * n / 2 ) - 2
于是，只要非零元素小于半数，算法II就可以起到压缩的效果。

注：算法II生成的矩阵中没有表示非零元素个数的变量，确实没有，不过很简单就可以计算出来。