稀疏矩阵

beyes

稀疏矩阵
稀疏矩阵 ( Sparse Matrices ) 是二维数字的一种特殊情况，因为数组内的大部分内容没填满，整个空间显得稀稀拉拉，故称之为稀疏矩阵。如下表格所示：
[table=432px][tr][td]  
[/td][td]  
[/td][td]1
[/td][td]  
[/td][td]
[/td][td]  
[/td][td]
[/td][td]
[/td][td]  
[/td][td]  
[/td][/tr][tr][td] 
[/td][td]
[/td][td]
[/td][td]
[/td][td]9
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][/tr][tr][td] 
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]2
[/td][td]
[/td][td]
[/td][/tr][tr][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]3
[/td][td]
[/td][td]
[/td][td]
[/td][/tr][tr][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]
[/td][td]5
[/td][td]
[/td][td]
[/td][/tr][/table]
为了增加数组的使用率，可以对这个矩阵进行压缩，压缩方法为：

5	10	5
0	2	1
1	3	9
2	5	2
3	4	3
4	7	6

上面数组，设为 Max [6][3];
Max [0][0] = 5 表示压缩前数组一共有 5 行；
Max [0][1] = 10 表示压缩前数组一共有 10 列；
Max [0][3] = 5 表示压缩前数组一共存储有 5 个元素。

第 1 行 掉 第 5 行，每行依次原数组中元素的所处数组中的行列值和自身值。

下面代码实现稀疏矩阵的压缩：

#include <stdio.h>

int main (void)
{
    int i;
    int j;
    int k = 1;

    int spar_max [5][10] = {   /*定义稀疏矩阵*/
                    0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 9, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 2, 0, 0,
                    0, 0, 0, 0, 0, 0, 3, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 5, 0, 0 };
    int com_max [6][3];
   
    com_max [0][0] = 5;    /*被压缩数组行数*/
    com_max [0][1] = 10;    /*被压缩数组列数*/
    com_max [0][2] = 5;    /*被压缩数组元素个数*/

    for (i = 0; i < 5; i++) {
        for (j = 0; j < 10; j++) {
            if (spar_max [i][j] != 0) {
                com_max [k][0] = i;
                com_max [k][1] = j;
                com_max [k][2] = spar_max [i][j];
            }
                       
        }
        k += 1;
    }       
   
    /*输出压缩后的数组*/
    for (i = 0; i < 6; i++) {
       for (j = 0; j < 3; j++)
           printf ("%-4d", com_max [i][j]);
          
       printf("\n");
    }

    return (0);
}

运行及输出：

beyes@linux-beyes:~/C/structer> ./sparse_matrices.exe
5   10  5  
0   2   1  
1   4   9  
2   7   2  
3   6   3  
4   7   5