阅读：0       作者：严长生

稀疏矩阵，就是只含有少量非 0 元素的矩阵。如下图所示：

图 1 为 4*4 的矩阵，由于矩阵中只有两个非 0 元素，其他元素都为 0 ，所以可归为稀疏矩阵的范畴。

存储此类矩阵时，若用普通方式将所有元素一一存储，会造成内存的大量浪费（存储了很多的 0），而且在访问和操作元素的时候也会造成时间上的浪费。

所以，稀疏矩阵在计算机中的存储方式是：只存储非 0 元素，使用三元组表的方法进行存储。

三元组表存储稀疏矩阵

稀疏矩阵采用只存储非 0 元素的方式存储整个稀疏矩阵，需要存储以下信息：

1. 各个非 0 元素所在矩阵中的位置，包括：行标、列标和此非 0 元素的值；
2. 记录该稀疏矩阵的总行数和总列数；

通过矩阵具有的总行数和列数，以及所有非 0 元素所在的位置和值，就可以唯一确定这个稀疏矩阵。

例如，使用三元组表的方式存储图 1 的稀疏矩阵，则只需存储以下信息：

• 非 0 元素 1 和 2 的位置，即行标、列标和其值，分别是：（2,3,1）和（3,2,2）；
• 记录稀疏矩阵的行数和列数，即有 4 行 4 列；

通过以上信息，我们就可以还原出如图 1 所示的稀疏矩阵。

其三元组表法存储稀疏矩阵的实现代码为：

#include <stdio.h>
#define number 100
//三元组结构体
typedef struct {
    int i,j;//行标i，列标j
    int data;//元素值
}triple;
//矩阵的结构表示
typedef struct {
    triple data[number];//存储该矩阵中所有非0元素的三元组
    int n,m,num;//n和m分别记录矩阵的行数和列数，num记录矩阵中所有的非0元素的个数
}TSMatrix;
int main(){
    TSMatrix T;
    int i,j,k;
    printf("请输入矩阵非 0 元素的个数:\n");
    scanf("%d",&T.num);
    printf("请输入所有非0 元素的三元组：i j data\n");
    for(i=0;i<T.num;i++){
        scanf("%d %d %d",&T.data[i].i,&T.data[i].j,&T.data[i].data);
    }
    printf("请输入矩阵的行数、列数:\n");
    scanf("%d %d",&T.n,&T.m);
    //输出稀疏矩阵
    for(i=0;i<T.n;i++){
        for(j=0;j<T.m;j++){
            for(k=0;k<T.num;k++){
                //若此行此列有非 0 值，则输入
                if(T.data[k].i == i+1 && T.data[k].j == j+1){
                    printf("%d ",T.data[k].data);
                    break;
                }
            }
            //若三元组表中无此行此列的非0值记录，则输出 0
            if(k == T.num){
                printf("0 ");
            }
        }
        printf("\n");
    }
    return 0;
}

运行结果：

稀疏矩阵的存储除了用三元组表法，还可以用行逻辑链接的顺序表和十字链表来存储，详解介绍可阅读《矩阵的压缩存储算法》一文。