三元组表相加.docx
《三元组表相加.docx》由会员分享，可在线阅读，更多相关《三元组表相加.docx（15页珍藏版）》请在冰点文库上搜索。
三元组表相加
1问题要求及任务描述
1.1题目要求
三元组表相加
问题描述：
利用数组的顺序存储结构，实现特殊矩阵的压缩存储和稀疏矩阵的三元组存储和加法实现
基本要求：
1）利用稀疏矩阵的三元组存储，来实现两矩阵相加
2）利用稀疏矩阵的三元组存储，来实现两矩阵相乘
两个希疏矩阵分别用两个文件存放，相加后的矩阵存入一个文件后在屏幕上显示
1.2主要任务
我主要负责编写两个非零稀疏矩阵相乘的程序，两个已经经过压缩存储的矩阵，运用矩阵相乘的标准法来进行计算。
2解决问题的主要思路和方法
2.1关键问题
输入两个稀疏矩阵，进行两个矩阵相乘。
然后输出相乘后的结果。
2.2拟采用解决问题的方法
运用矩阵相乘的标准法进行编程序。
利用数组的顺序存储结构，实现特殊矩阵的压缩存储和稀疏矩阵的三元组存储和加法实现，利用稀疏矩阵的三元组存储，来实现两矩阵相乘。
先输入两个矩阵，判断前一个矩阵的列数是否已后一个矩阵的行数相等，不相等就返回错误，否则继续执行，接着就使用标准法进行计算。
完成后输出正确结果。
2.3主要算法和处理流程图
是
是
否
是
否
是
否
3程序实现
3.1程序实现时应考虑的问题
3.2主要源代码及说明
#include
#include
usingnamespacestd;
#defineOK1
#defineERROR0
constintMAXSIZE=100;//定义非零元素的最多个数
typedefstruct//定义三元组元素
{
intr,c;//矩阵的行号和列号
intv;//矩阵元素值
}Triple;
typedefstruct//定义普通三元组对象
{
Tripledata[MAXSIZE+1];
introws,cols,nzeroNums;//行数、列数、非零元素个数
}TSMatrix;
template
boolInputTSMatrix（T&M,inty）
{
cout<<"输入矩阵的行数、列数和非零元素个数:
";
cin>>M.rows>>M.cols>>M.nzeroNums;
cout<<"请输入非零元素对应的行号、列号和相应的元素值:
"<for（inti=1;i<=M.nzeroNums;i++）
{
cin>>M.data[i].r>>M.data[i].c>>M.data[i].v;
}
returntrue;
}
template
boolOutputSMatrix（TM）
{
inti,j,k=1;
for（i=0;i{
for（j=0;j{
if（（M.data[k].r-1）==i&&（M.data[k].c-1）==j）
{
cout<k++;
}
else
cout<}//end_j
cout<}//end_i
returntrue;
}
//两个稀疏矩阵的加法
intAddMatrix（TSMatrixM,TSMatrixN,TSMatrixQ）
{
//求采用三元组顺序表存储表示的稀疏矩阵M和N的和，,结果赋给矩阵Q
if（（M.rows<=0）||（M.cols<=0）||（M.nzeroNums<0）||（N.rows<=0）||（N.cols<=0）||（N.nzeroNums<0））
returnERROR;
if（M.rows!
=N.rows||M.cols!
=N.cols）
returnERROR;
Q.rows=M.rows;
Q.cols=M.cols;
Q.nzeroNums=0;
intx=0,y=0;
for（inti=1;i<=Q.rows;i++）
{
for（intj=1;j<=Q.cols;j++）
{
for（intp=1;p<=M.nzeroNums;p++）
{
if（（i==M.data[p].r）&&（j==M.data[p].c））
{
x=M.data[p].v;
break;
}
elsex=0;
}//forp
for（intq=1;q<=N.nzeroNums;q++）
{
if（（i==N.data[q].r）&&（j==N.data[q].c））
{
y=N.data[q].v;
break;
}
elsey=0;
}//forq
if（（x+y）!
=0）
{
Q.data[Q.nzeroNums+1].r=i;
Q.data[Q.nzeroNums+1].c=j;
Q.data[Q.nzeroNums+1].v=x+y;
Q.nzeroNums++;
}//if
}//forj
}//fori
cout<<"加法结果是：
"<<"\n";
OutputSMatrix（Q）;
returnOK;
}
//得到矩阵元素M[i][j]的值
intvalue（TSMatrixM,inti,intj）
{
intk;
for（k=1;k<=M.nzeroNums;k++）
{
if（M.data[k].r==i&&M.data[k].c==j）
{
returnM.data[k].v;
}
}
return0;
}
//矩阵乘法的算法
intMultMat（TSMatrixA,TSMatrixB,TSMatrixC）
{
inti,j,k,temp=0,p=1;
if（A.cols!
=B.rows）
{
cout<<"矩阵A的列数不等于矩阵B的行数不能相乘!
\n";
return0;
}
else
{
for（i=1;i<=A.rows;i++）
{
for（j=1;j<=B.cols;j++）
{
temp=0;
for（k=1;k<=A.cols;k++）
{
temp+=value（A,i,k）*value（B,k,j）;//矩阵元素累积相加
}
if（temp!
=0）//如果不等以0，则将行号和列号存到C的三元组中。
{
C.data[p].r=i;
C.data[p].c=j;
C.data[p].v=temp;
p++;
}
}
}
C.rows=A.rows;//将A的行数赋给C的行数
C.cols=B.cols;//将B的列数赋给C的列数
C.nzeroNums=p-1;
cout<<"输出两个稀疏矩阵的积:
"<OutputSMatrix（C）;//输出相乘后的结果
return1;
}
}
voidsaveA（TSMatrixD）
{FILE*fp;
inti;
if（（fp=fopen（"1.txt","wb"））==NULL）
{printf（"cannotopenfile\n"）;
return;
}
for（i=0;iif（fwrite（&D.data[i],sizeof（Triple）,1,fp）!
=1）
printf（"filewriteerror\n"）;
fclose（fp）;
}
voidsaveB（TSMatrixD）
{FILE*fp;
inti;
if（（fp=fopen（"2.txt","wb"））==NULL）
{printf（"cannotopenfile\n"）;
return;
}
for（i=0;iif（fwrite（&D.data[i],sizeof（Triple）,1,fp）!
=1）
printf（"filewriteerror\n"）;
fclose（fp）;
}
voidsaveC（TSMatrixD）
{FILE*fp;
inti;
if（（fp=fopen（"3.txt","wb"））==NULL）
{printf（"cannotopenfile\n"）;
return;
}
for（i=0;iif（fwrite（&D.data[i],sizeof（Triple）,1,fp）!
=1）
printf（"filewriteerror\n"）;
fclose（fp）;
}
voidmain（）
{TSMatrixA,B,C,D;
InputTSMatrix（A,1）;
OutputSMatrix（A）;
saveA（A）;
InputTSMatrix（B,1）;
OutputSMatrix（B）;
saveB（B）;
MultMat（A,B,D）;
AddMatrix（A,B,C）;
saveC（C）;
}
4测试
4.1测试结果及分析
经过检验测试，结果正确！
5小结
5.1本问题解决方法及程序实现小结
利用数组的顺序存储结构，实现特殊矩阵的压缩存储和稀疏矩阵的三元组存储和加法实现，利用稀疏矩阵的三元组存储，运用矩阵相乘的标准法进行编程序，来实现两矩阵相乘。
先输入两个矩阵，判断前一个矩阵的列数是否已后一个矩阵的行数相等，不相等就返回错误，否则继续执行，接着就使用标准法进行计算。
完成后输出正确结果。
经过测试，程序运行结果完全正确！
5.2尚未解决的问题及下一步工作思路
1.两个稀疏矩阵未能成功的分别用两个文件存放，相加后的矩阵未能成功的存入一个文件。
2.相乘算法未能减少时间复杂度，我现在有的是标准法三重循环，实际上可以用二重循环也就可以的了。
3.以后尽量减少循环次数，也就是减少时间复杂度。
6参考文献
[1]朱战力.数据结构.电子工业出版社.2010.11
升级会员 