稀疏矩阵实验报告.docx
《稀疏矩阵实验报告.docx》由会员分享，可在线阅读，更多相关《稀疏矩阵实验报告.docx（23页珍藏版）》请在冰点文库上搜索。
稀疏矩阵实验报告
稀疏矩阵实验报告
稀疏矩阵
实
验
报
告
班级：
信管1102
姓名：
喻雅刚
学号：
11300530210
日期：
1月3号
期《稀疏矩阵》实验报告
◎实验
题目:
有输入界面（图形或文字界面都可），能区分加法、减法、乘法和转置；能处理任意输入的典型数据和进行出错数据处理（例如乘法，当第一个矩阵的列数不等于第二个矩阵的行数时）；必须采用三元组作存储结构，不能采用数组等形式；输出要求用矩阵的形式输出（即习题集136页的形式），当第一个矩阵的行数不等于第二个矩阵的行数时，注意如第三个乘法的形式输出
◎实验目的：
设计算法，实现矩阵的加减乘以及转置。
◎实验内容：
有输入界面（图形或文字界面都可），能区分加法、减法、乘法和转置；能处理任意输入的典型数据和进行出错数据处理（例如乘法，当第一个矩阵的列数不等于第二个矩阵的行数时）；必须采用三元组作存储结构，不能采用数组等形式；输出要求用矩阵的形式输出（即习题集136页的形式），当第一个矩阵的行数不等于第二个矩阵的行数时，注意如第三个乘法的形式输出
一、需求分析^p
说明程序设计的任务，强调的是程序要做什么，明确规定：
1、输入的形式和输入值的范围；2、输出的形式；3、程序所能达到的功能；4、测试数据：
包括正确的输入及其输出结果和含有错误的输入及其输出结果。
二概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。
三详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法；画出函数的调用关系。
?
四使用说明、测试分析^p及结果
1、说明如何使用你编写的程序；2、测试结果与分析^p；3、调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析^p；4、运行界面。
五、实验总结
1、算法的时空分析^p和改进设想等等，见示例。
报告：
（一）需求分析^p
1．本演示程序中，矩阵的行列人为规定，由个人输入需要计算的矩阵，首先选择自己需要计算方式，在输入所需要计算的矩阵，程序将根据选择进行计算，最后输出结果。
2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（所需计算矩阵的行列数及矩阵内个元素），程序将自动将稀疏矩阵保存在三元标中。
3．程序执行的命令包括：
（1）构建三元列表；
（2）输入所需计算矩阵的行列数；（3）输入矩阵内的全部元素（4）根据选择进行矩阵计算（5）输出矩阵
4．测试数据
（1）a.mu=3a.nu=3，101
200
021
b.mub.nu012
111
102
加法输出：
113减法输出：
1-1-1乘法输出：
114
3111-1-1000
123-12-1302
（二）概要设计
为了实现上述操作，应以单向循环链表为存储结构。
1．input（b）
基本操作：
以此输入稀疏矩阵内每个元素
操作结果：
建立三元列表b，并想稀疏矩阵内输入数据
addmtir（a,b,c）;
初始条件：
存在两个不为空稀疏矩阵和一个空的三元列表
操作结果：
将两个稀疏矩阵相加，并将得数存储在c中
transposesmatri（a,b）;
初始条件：
存在一个不为空稀疏矩阵和一个空的三元列表
操作结果：
将含有数据的稀疏矩阵转置，并将得数存储在b中
multmatri（a,b,c）;
初始条件：
存在两个不为空稀疏矩阵和一个空的三元列表
操作结果：
将两个稀疏矩阵相乘，并将得数存储在c中
submtir（a,b,c）
初始条件：
存在两个不为空稀疏矩阵和一个空的三元列表
操作结果：
将两个稀疏矩阵相加减，并将得数存储在c中
Output（）
初始条件：
存放稀疏矩阵三元列表存在
操作结果：
输出计算后的稀疏矩阵
2．本程序包含三个模块：
（1）主程序模块；
（2）输入需要计算的稀疏矩阵
（3）选择计算方法，并计算
（4）输出计算后的矩阵
（5）模块调用图：
主程序模块
输入需要计算的稀疏矩阵
选择计算方法，并计算
输出计算后的矩阵
（三）详细设计
1．元素类型，列表类型和指针类型：
#include
#include
#definemasize100
typedefintdatatype;
typedefstruct//定义三元组
{
inti,j;
datatype;
}matri;
typedefstruct//定义三元组表
{
matridata[masize];
intmu,nu,tu;//矩阵行,列,非零元个数
}tripulematri;
2．每个模块的分析^p：
（1）主程序模块：
voidmain
{
printf（“----------------矩阵计算---------------\n”）;
printf（“请选择你需要的计算方式\n”）;
printf（“-----------------1.稀疏矩阵的转置---------------\n”）;
printf（“-----------------2.稀疏矩阵的加法---------------\n”）;
printf（“-----------------3.稀疏矩阵的减法---------------\n”）;
printf（“-----------------4.稀疏矩阵的乘法---------------\n”）;
char;
scanf（“c”,）;
tripulematria,b,c;
switch
{
case#;1#;:
//tripulematria,b;
printf（“请输入矩阵的行数与列数\n”）;
scanf（“dd”,a.mu,a.nu）;
b.mu=a.mu;
b.nu=a.nu;
printf（“请输入一个矩阵，例如：
\n”）;
printf（“123\n234\n456\n”）;
printf（“请输入\n”）;
input（a）;
transposesmatri（a,b）;
output（b）;
break;
case#;2#;:
//tripulematria,b,c;
printf（“请输入矩阵的行数与列数\n”）;
scanf（“dd”,a.mu,a.nu）;
b.mu=a.mu;
b.nu=a.nu;
printf（“请输入两个矩阵，例如：
\n”）;
printf（“123\n234\n456\n”）;
printf（“请输入\n”）;
printf（“请输入第一个矩阵\n”）;
input（a）;
printf（“请输入第二个矩阵\n”）;
input（b）;
addmtir（a,b,c）;
output（c）;
break;
case#;3#;:
//tripulematria,b,c;;
printf（“请输入矩阵的行数与列数\n”）;
scanf（“dd”,a.mu,a.nu）;
b.mu=a.mu;
b.nu=a.nu;
printf（“请输入两个矩阵，例如：
\n”）;
printf（“123\n234\n456\n”）;
printf（“请输入\n”）;
printf（“请输入第一个矩阵\n”）;
input（a）;
printf（“请输入第二个矩阵\n”）;
input（b）;
submtir（a,b,c）;
break;
case#;4#;:
//tripulematria,b,c;;
printf（“请输入矩阵的行数与列数\n”）;
scanf（“dd”,a.mu,a.nu）;
b.mu=a.mu;
b.nu=a.nu;
printf（“请输入两个矩阵，例如：
\n”）;
printf（“123\n234\n456\n”）;
printf（“请输入第一个矩阵\n”）;
input（a）;
printf（“请输入第二个矩阵\n”）;
input（b）;
multmatri（a,b,c）;
break;
case#;5#;:
eit（0）;
break;
system（“pause”）;
}
（2）输入数据
voidinput（tripulematria）
{
inti,j,k=0;
datatype;
for（i=0;imu;i++）
{
for（j=0;jnu;j++）
{
scanf（“d”,）;
if//如果是非零元
{
a->data[k].i=i;
a->data[k].j=j;
a->data[k].=;
k++;
}
}
}
a->tu=k;
}//input
（3）加法
datatypeaddmtir（tripulematria,tripulematrib,tripulematric）
{
intk=0,l=0;
c->mu=a->mu;
c->nu=a->nu;
c->tu=0;
while（ktultu）
{
if（（a->data[k].i==b->data[l].i）（a->data[k].j==b->data[l].j））
{
inttemp=a->data[k].+b->data[l].;
if（temp!
=0）
{
c->data[c->tu].=a->data[k].+b->data[l].;
c->data[c->tu].i=a->data[k].i;
c->data[c->tu].j=a->data[k].j;
c->tu++;
}
k++;l++;
}
else
if（（a->data[k].i==b->data[l].i）（a->data[k].jdata[l].j））
{
c->data[c->tu].=a->data[k].;
c->data[c->tu].i=a->data[k].i;
c->data[c->tu].j=a->data[k].j;
c->tu++;
k++;
}
else
{
if（（（a->data[k].i==b->data[l].i）（a->data[k].j>b->data[l].j））||（a->data[k].i>b->data[l].i））
{
c->data[c->tu].i=b->data[l].i;
c->data[c->tu].j=b->data[l].j;
c->data[c->tu].=b->data[l].;
c->tu++;
l++;
}
}
}
while（ktu）
{
c->data[c->tu].=a->data[k].;
c->data[c->tu].i=a->data[k].i;
c->data[c->tu].j=a->data[k].j;
c->tu++;
k++;
}
while（ltu）
{
c->data[c->tu].i=b->data[l].i;
c->data[c->tu].j=b->data[l].j;
c->data[c->tu].=b->data[l].;
c->tu++;
l++;
}
return
（1）;
}
（4）减法
datatypesubmtir（tripulematria,tripulematrib,tripulematric）//减法
{
intk=0,l=0;
c->mu=a->mu;
c->nu=a->nu;
c->tu=0;
while（ktultu）
{
if（（a->data[k].i==b->data[l].i）（a->data[k].j==b->data[l].j））
{
//inttemp=a->data[k].-b->data[l].;
//if（temp!
=0）
//{
c->data[c->tu].=a->data[k].-b->data[l].;
c->data[c->tu].i=a->data[k].i;
c->data[c->tu].j=a->data[k].j;
c->tu++;
//}
k++;l++;
}
else
if（（a->data[k].i==b->data[l].i）（a->data[k].jdata[l].j）||（a->data[k].idata[l].i））
{
c->data[c->tu].=a->data[k].;
c->data[c->tu].i=a->data[k].i;
c->data[c->tu].j=a->data[k].j;
c->tu++;
k++;
}
else
{
if（（（a->data[k].i==b->data[l].i）（a->data[k].j>b->data[l].j））||（a->data[k].i>b->data[l].i））
{
c->data[c->tu].i=b->data[l].i;
c->data[c->tu].j=b->data[l].j;
c->data[c->tu].=-b->data[l].;
c->tu++;
l++;
}
}
}
while（ktu）
{
c->data[c->tu].=a->data[k].;
c->data[c->tu].i=a->data[k].i;
c->data[c->tu].j=a->data[k].j;
c->tu++;
k++;
}
while（ltu）
{
c->data[c->tu].i=b->data[l].i;
c->data[c->tu].j=b->data[l].j;
c->data[c->tu].=-b->data[l].;
c->tu++;
l++;
}
return
（1）;
}
（5）转置
inttransposemarti（tripulematria,tripulematrib）
{
intcol,p,q;
b->mu=a->nu;
b->nu=a->mu;
b->tu=a->tu;
if（b->tu）
{
q=0;
for（col=0;colnu;col++）
{
for（p=0;ptu;p++）
if（a->data[p].j==col）
{
b->data[p].i=a->data[q].j;
b->data[p].j=a->data[q].i;
b->data[p].=a->data[q].;
q++;
}
}
}
return
（1）;
}//稀疏矩阵的转置算法
（六）乘法intmultmatri（tripulematria,tripulematrib,tripulematric）
{
intrpos1[masize],rpos2[masize],num[masize],rpos3[masize];
introw1,row2,arow,tp,t,brow,ccol,p,q,k;
intctemp[masize];
if（a->tu）
{
for（row1=0;row1mu;row1++）
{
num[row1]=0;
}
for（row1=0;row1tu;row1++）
{
++num[a->data[row1].i];
}
rpos1[0]=0;
for（row1=1;row1mu;row1++）
{
rpos1[row1]=rpos1[row1-1]+num[row1-1];
}
}
if（b->tu）
{
for（row2=0;row2tu;row2++）
{
num[row2]=0;
}
for（row2=0;row2tu;row2++）++num[b->data[row2].i];
rpos2[0]=0;
for（row2=1;row2mu;row2++）rpos2[row2]=rpos2[row2-1]+num[row2-1];
}
c->mu=a->mu;c->nu=b->nu;c->tu=0;
if（a->tub->tu!
=0）
{
for（arow=0;arowmu;arow++）
{
for（k=0;ktu+1;
if（arowmu-1）
{
tp=rpos1[arow+1];
}
else
tp=a->tu;
for（p=rpos1[arow];pdata[p].j;//找到对应元在b中的行号
if（brownu-1）
{
t=rpos2[brow+1];
}
elset=b->tu;
for（q=rpos2[brow];qdata[q].j;//乘积元素在Q中的列号
ctemp[ccol]+=（a->data[p].）（b->data[q].）;
}
}
for（ccol=0;ccolnu;ccol++）
{
if（ctemp[ccol]）
{
if（c->tu>masize）
{
return0;
}
c->data[c->tu].i=arow;
c->data[c->tu].j=ccol;
c->data[c->tu].=ctemp[ccol];
c->tu++;
}
}
}
}
return1;
}
（4）函数调用关系图
main
input（a）;
transposesmatri（a,b）;
submtir（a,b,c）;
addmtir（a,b,c）;
multmatri（a,b,c）;
output;
3．完整的程序：
//稀疏矩阵.cpp:
定义控制台应用程序的入口点。
//
#include
#definemasize100
typedefstruct
{
inti,j;//该非零元的行和列
intv;//该非零元的值
}
triple;typedefstruct
{
tripledata[masize];//非零元三元组表，data[0]未用
intrpos[masize];
intm,n,t;//矩阵的行数，列数和非零元个数
}
tripletable;
voidconvert//矩阵的转置
{intk;
tripletableA,B;
printf（“输入稀疏矩阵A的行数，列数和非零元个数：
”）;
scanf（“ddd”,A.m,A.n,A.t）;
for（k=1;kmasize）return;
C.data[C.t].i=arow;
C.data[C.t].j=ccol;
C.data[C.t].v=ctemp[ccol];
}
}
}
}
inta[100][100]={0};
for（k=1;k<=A.t;k++）
{
a[A.data[k].i][A.data[k].j]=A.data[k].v;
}
printf（“A输入为：
\n”）;
for（k=1;k<=A.m;k++）
{
for（intl=1;l<=A.n;l++）
printf（“d”,a[k][l]）;
printf（“\n”）;
}
intb[100][100]={0};
for（k=1;k<=B.t;k++）
{
b[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf（“B输入为：
\n”）;
for（k=1;k<=B.m;k++）
{
for（intl=1;l<=B.n;l++）
printf（“d”,b[k][l]）;
printf（“\n”）;
}
intc[100][100]={0};
for（k=1;k<=C.t;k++）
{
c[C.data[k].i][C.data[k].j]=C.data[k].v;
}
printf（“乘法结果C为：
\n”）;
for（k=1;k<=C.m;k++）
{
for（intl=1;l<=C.n;l++）
printf（“d”,c[k][l]）;
printf（“\n”）;
}
}
voidmain
{
printf（“=============菜单==============\n”）;
printf（“1矩阵转置\n”）;
printf（“2矩阵加法\n”）;
printf（“3矩阵减法\n”）;
printf（“4矩阵乘法\n”）;
printf（“======================================\n\n”）;loop:
printf（“请选择相应操作的序号:
”）;
inty;
scanf（“d”,y）;
switch（y）
{
case1:
convert;
printf（“\n”）;
gotoloop;
case2:
add;
printf（“\n”）;
gotoloop;
case3:
jian;
printf（“\n”）;
gotoloop;
case4:
multi;
printf（“\n”）;
gotoloop;
}
}
}（四）程序使用说明及测试结果
1．程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
----------------矩阵计算---------------
请选择你需要的计算方式
-----------------1.稀疏矩阵的转置---------------
-----------------2.稀疏矩阵的加法---------------
-----------------3.稀疏矩阵的减法---------------
-----------------4.稀疏矩阵的乘法---------------
1
请输入矩阵的行数与列数
33
请输入一个矩阵，例如：
123
111
111
得出：
111
211
311
请按任意键继续
3．调试中的错误及解决办法。
（1）转置出现问题
（2）输出时无法利用数组第一个空间
（3）三元表定义是无rpos（每行第一个非零元位置）
解决方式：
逐步调试，以及问同学，自己更改算法，计算出rpos
4．运行界面
（五）、实验总结（实验心得）
你在编程过程中花时多少？
2天
多少时间在纸上设计？
1天
多少时间上机输入和调试？
1天
多少时间在思考问题？
2天
遇到了哪些难题？
对算法的思想领会的不深，程序无法输出，程序无限循环，程序崩溃等问题，还有由于疏忽导致的拼写错误
你是怎么克服的？
重新逐步调试，和同学交流。
你的收获有哪些？
平时要多和同学交流解决问题，在程序上不能有一点马虎大意，平时也应该多看一些有用的编程类的书
实验成绩：
指导教师签名：
批阅日期：
升级会员 