|
数据结构——稀疏矩阵三元组形式相加
一.稀疏矩阵的在C语言上的定义描述
typedef struct
{
int i,j;//该非零元的行列下标
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];//非零元三元组表，data[0]未用
int mu,nu,tu; //矩阵的行数，列数和非零元个数
}TSMatrix;
稀疏矩阵相关知识见博客：数据结构——稀疏矩阵的转置
二.矩阵加法算法
算法思想 在A，B两矩阵的非零元向后遍历的时候，以行为第一比较元，列为第二比较元，把行列值小的先放入C中，并且对应矩阵非零元向后遍历一位。当行列值都相同时，若两非零元相加不为零，则把相加后的值放入C中。直至A或B的非零元遍历结束，把还有剩余元素的矩阵所剩非零元放到C的末尾。相加完成。
//矩阵加法
Status SumTriple(TSMatrix A,TSMatrix B,TSMatrix &C)
{
if((A.mu!=B.mu)||(A.nu!=B.nu))
{
printf("不是同类型矩阵，不能进行加法运算\n");
return ERROR;
}
C.mu=A.mu;
C.nu=B.nu;
int a=1,b=1;
while(a
EnterTriple(C,A.data[a].i,A.data[a].j,A.data[a].e);
a++;
}
else if(A.data[a].i==B.data[b].i)
//如果a中数据的行号等于b中数据行号，则看列号，把列号小的放入C，若行列都相同，若相加不为0，则相加后放入C
{
if(A.data[a].j
EnterTriple(C,B.data[b].i,B.data[b].j,B.data[b].e);
b++;
}
else
{
if(B.data[b].e+A.data[a].e!=0)
EnterTriple(C,B.data[b].i,B.data[b].j,B.data[b].e+A.data[a].e);
a++;
b++;
}
}
else//如果a中数据的行号大于b中数据行号，把B放进C
{
EnterTriple(C,B.data[b].i,B.data[b].j,B.data[b].e);
b++;
}
}
//把还有剩余数据的数组的数据放到C中
while(a
EnterTriple(C,B.data[b].i,B.data[b].j,B.data[b].e);
b++;
}
}
void EnterTriple(TSMatrix &C,int i,int j,int e)
{
C.tu++;
C.data[C.tu].i=i;
C.data[C.tu].j=j;
C.data[C.tu].e=e;
}
另附：稀疏矩阵的创建和遍历输出函数
//创建矩阵
Status CreateSMatrix(TSMatrix &M)
{
printf("请输入矩阵的行数：\t");
scanf("%d",&M.mu);
printf("请输入矩阵的列数：\t");
scanf("%d",&M.nu);
printf("请输入矩阵的非零元个数：\t");
scanf("%d",&M.tu);
printf("请输入非零元素的行列值和元素值\n(三个元素以空格为分隔符 每组元素以回车为分隔符):\n") ;
for(int a=1;a
int k=1;
for(int m=1;m
if((M.data[k].i==m)&&(M.data[k].j==n))
{
printf("%4d",M.data[k].e);
k++;
}
else
{
printf("%4d",0);
}
}
printf("\n");
}
return TRUE;
}
|