阅读:0       作者:严长生

稀疏矩阵的三元组表示(带源码+解析)

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

图 1 稀疏矩阵

图 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;
}
运行结果:
请输入矩阵非 0 元素的个数:
2
请输入所有非0 元素的三元组:i j data
2 3 1
3 2 2
请输入矩阵的行数、列数:
4 4
0 0 0 0
0 0 1 0
0 2 0 0
0 0 0 0

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