使用三元组表示法来表示稀疏矩阵。
三元组数据结构是一个长度为n，表内每个元素都有3个分量的线性表，其3个分量分别为行下标和列下标。元素结构体定义如下：
/* 三元组的结构体 */
typedef struct {
int val;// 稀疏矩阵中非零元素的值
int i;// 稀疏矩阵中非零元素的行下标
int j;// 稀疏矩阵中非零元素的列下标
} Trimat;在程序中如果要定义一个含有maxterms个非零元素的稀疏矩阵，则只需写成如下代码：
Trimat trimat[maxterms+1];// maxterms是已经定义的常量语句trimat[k].val表示取第k个非零元素的值；trimat[k].i和trimat[k].j表示取第k个非零元素在矩阵中的行下标和列下标。
下面用一个例子：给定一个稀疏矩阵A（float型），其尺寸为mxn，建立其对应的三元组存储，并通过三元组打印输出矩阵A。
具体实现代码如下：
#include<stdio.h>
#define maxterms 20
#define maxSize 20
/* 三元组的结构体 */
typedef struct {
int val;// 稀疏矩阵中非零元素的值
int i;// 稀疏矩阵中非零元素的行下标
int j;// 稀疏矩阵中非零元素的列下标
} Trimat;
/* 根据稀疏矩阵建立三元组 */
/* A[][maxSize]指的是一个稀疏矩阵；m指的是稀疏矩阵的行数；n指的是稀疏矩阵的列数；trimat[maxterms+1]指的是三元组 */
void createTrimat(float A[][maxSize],int m,int n,Trimat trimat[maxterms+1]) {
int k=1;// 计数器，记录结构体trimat数组的下标
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) { // 双层循环，遍历稀疏矩阵中的每个元素
if(A[i][j]!=0) { // 判断稀疏矩阵中的非零元素
trimat[k].val=A[i][j];// 保存非零元素的值
trimat[k].i=i;// 保存非零元素的行下标
trimat[k].j=j;// 保存非零元素的列下标
k++;// 加1
}
}
}
/* 保存三元组的一些基本信息 */
trimat[0].val=k-1;// 存放的数稀疏矩阵中非零元素的个数
trimat[0].i=m;// 保存的是矩阵行数
trimat[0].j=n;// 保存的是矩阵列数
}
/* 根据三元组打印出原来的稀疏矩阵 */
/* trimat[maxterms+1]指的是三元组 */
void printTrimat(Trimat trimat[maxterms+1]) {
int m=trimat[0].i;// 稀疏矩阵的行数
int n=trimat[0].j;// 稀疏矩阵的列数
int k=1;// 三元组数组的下标，初始为1，因为trimat[0]保存的是三元组的一些基本信息
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) { // 双层循环遍历稀疏矩阵
if(i==trimat[k].i&&j==trimat[k].j) { // 如果i和j能够匹配三元组的下标trimat[k].i和trimat[k].j
printf("%d\t",trimat[k].val);// 如果能够配对则输出三元组的非零元素的值
k++;// 继续遍历三元组的元素
} else {
printf("0\t");// 如果没有匹配则代表该处位置是0
}
}
printf("\n");// 换行
}
}
int main() {
// 稀疏矩阵
float A[][maxSize]= {
{0,0,0,1},
{0,0,3,2},
{1,0,0,0},
{0,2,0,0},
{1,0,0,0}
};
Trimat trimat[maxSize];// 定义一个三元组
createTrimat(A,5,4,trimat);// 调用函数创建三元组
printTrimat(trimat);// 根据三元组打印稀疏矩阵
return 0;
}控制台打印结果如下：
为了简便起见，可以不使用上述结构体定义的方法来定义三元组，直接申请一个二维数组即可。
如：
int trimat[maxterms+1][3];trimat[k][0]表示原矩阵中的元素按行优先排序的第k个非零元素的值；trimat[k][1]、trimat[k][2]表示第k个非零元素在矩阵中的位置。可以看出此时trimat就是一个maxterms行3列的二维数组。规定第0行的三个元素分别来存储非零元素的个数、行数和列数。例如：trimat[0][0]为原矩阵中的非零元素个数，trimat[0][1]和trimat[0][2]为矩阵行数和列数。
所以实现代码如下：
#include<stdio.h>
#define maxterms 20
#define maxSize 20
/* 通过稀疏矩阵来建立三元组B */
/* A[][maxSize]指的是稀疏矩阵；m指的是稀疏矩阵的行数；n指的是稀疏矩阵的列数；B[][3]指的是三元组 */
void createtrimat(float A[][maxSize],int m,int n,float B[][3]) {
int k=1;// 三元组的行下标，初始为1，因为0要存储稀疏矩阵的基本信息
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {// 循环遍历稀疏矩阵的所有元素
if(A[i][j]!=0) {// 判断稀疏矩阵中的非零元素，如果是非零元素
B[k][0]=A[i][j];// 将非零元素保存在B[k][0]
B[k][1]=i;// 将非零元素的行下标保存在B[k][1]
B[k][2]=j;// 将非零元素的列下标保存在B[k][2]
k++;
}
}
}
/* 保存稀疏矩阵的基本信息 */
B[0][0]=k-1;// 专门用B[0][0]来保存稀疏矩阵中非零元素的个数
B[0][1]=m;// 专门用B[0][1]来保存稀疏矩阵的行数
B[0][2]=n;// 专门用B[0][2]来保存稀疏矩阵的列数
}
/* 通过三元组打印稀疏矩阵A */
/* B[][3]指的是三元组 */
void print(float B[][3]) {
int k=1;// 计数器，记录三元组行下标的位置，从1开始，0表示的是稀疏矩阵的基本信息
for(int i=0; i<B[0][1]; i++) {
for(int j=0; j<B[0][2]; j++) {// 循环遍历稀疏矩阵的行和列
if(i==(int)B[k][1]&&j==(int)B[k][2]) {// 判断i和j是否与三元组中的行下标和列下标是否配对
printf("%1.f\t",B[k][0]);// 如果配对则输出稀疏矩阵的非零元素
k++;// 计数器加1，下一行
} else {// 如果不能配对，则是零元素
printf("0\t");// 输出零即可
}
}
printf("\n");// 换行
}
}
int main() {
// 稀疏矩阵
float A[][maxSize]= {
{0,0,0,1},
{0,0,3,2},
{1,0,0,0},
{0,2,0,0},
{1,0,0,0}
};
float trimat[maxterms][3];// 定义一个三元组
createtrimat(A,5,4,trimat);// 调用函数创建三元组
print(trimat);// 根据三元组打印稀疏矩阵
return 0;
}结果一样
