阅读:0
作者:严长生
稀疏矩阵的三元组表示(带源码+解析)
稀疏矩阵,就是只含有少量非 0 元素的矩阵。如下图所示:

图 1 稀疏矩阵
图 1 为 4*4 的矩阵,由于矩阵中只有两个非 0 元素,其他元素都为 0 ,所以可归为稀疏矩阵的范畴。
存储此类矩阵时,若用普通方式将所有元素一一存储,会造成内存的大量浪费(存储了很多的 0),而且在访问和操作元素的时候也会造成时间上的浪费。
所以,稀疏矩阵在计算机中的存储方式是:只存储非 0 元素,使用三元组表的方法进行存储。
通过矩阵具有的总行数和列数,以及所有非 0 元素所在的位置和值,就可以唯一确定这个稀疏矩阵。
例如,使用三元组表的方式存储图 1 的稀疏矩阵,则只需存储以下信息:
通过以上信息,我们就可以还原出如图 1 所示的稀疏矩阵。
其三元组表法存储稀疏矩阵的实现代码为:

图 1 稀疏矩阵
图 1 为 4*4 的矩阵,由于矩阵中只有两个非 0 元素,其他元素都为 0 ,所以可归为稀疏矩阵的范畴。
存储此类矩阵时,若用普通方式将所有元素一一存储,会造成内存的大量浪费(存储了很多的 0),而且在访问和操作元素的时候也会造成时间上的浪费。
所以,稀疏矩阵在计算机中的存储方式是:只存储非 0 元素,使用三元组表的方法进行存储。
三元组表存储稀疏矩阵
稀疏矩阵采用只存储非 0 元素的方式存储整个稀疏矩阵,需要存储以下信息:- 各个非 0 元素所在矩阵中的位置,包括:行标、列标和此非 0 元素的值;
- 记录该稀疏矩阵的总行数和总列数;
通过矩阵具有的总行数和列数,以及所有非 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
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
稀疏矩阵的存储除了用三元组表法,还可以用行逻辑链接的顺序表和十字链表来存储,详解介绍可阅读《矩阵的压缩存储算法》一文。