西工大数据结构实验DS03.docx
《西工大数据结构实验DS03.docx》由会员分享，可在线阅读，更多相关《西工大数据结构实验DS03.docx（26页珍藏版）》请在冰点文库上搜索。
西工大数据结构实验DS03
《数据结构》实验报告
班级:
学号:
姓名:
E-mail:
日期:
◎实验题目:
稀疏矩阵运算器。
◎实验目的：
设计合适的数据结构，熟悉矩阵三元组的结构，熟悉通过非零元三元组输出整个矩阵的操作，并熟悉通过三元组的运算进行矩阵的转置、加法、减法和乘法。
◎实验内容：
通过算法实现，构造合适的数据结构，对矩阵进行转置、加法、减法或者乘法运算。
要求有输入界面，能区分加法、减法、乘法和转置；能处理任意输入的典型数据和进行出错数据处理
一、需求分析
1．本程序演示中，用户通过输入界面输入相应的运算法则的序号选择相应矩阵运算，矩阵的行数、列数和非零元个数通过用户输入获得，并且通过三元组的输入获得矩阵的信息，而后根据选择进行矩阵的转置、加法、减法或者乘法运算。
。
2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入矩阵的行数、列数、非零元个数以及矩阵三元组的信息。
3．程序执行的命令包括：
（1）构造矩阵；
（2）输入矩阵三元组信息；
（3）矩阵的运算：
1）矩阵的转置；
2）矩阵的加法；
3）矩阵的减法；
4）矩阵的乘法；
（4）输出矩阵；
（5）结束。
4、测试数据：
矩阵的转置：
输入矩阵的行数、列数以及非零元个数：
3,3,2
输入矩阵三元组信息：
1,1,1
2,3,1
输出的矩阵为：
100
000
010
矩阵的加法：
输入矩阵A的行数、列数以及非零元个数：
3,3,2
输入矩阵三元组信息：
1,1,1
2,3,1
输入矩阵A的行数、列数以及非零元个数：
3,3,2
输入矩阵三元组信息：
1,1,1
2,2,1
输出的矩阵为：
200
011
000
矩阵的减法：
输入矩阵A的行数、列数以及非零元个数：
3,3,2
输入矩阵三元组信息：
1,1,1
2,3,1
输入矩阵A的行数、列数以及非零元个数：
3,3,2
输入矩阵三元组信息：
1,1,1
2,2,1
输出的矩阵为：
000
0-11
100
矩阵的加法：
输入矩阵A的行数、列数以及非零元个数：
1,4,4
输入矩阵三元组信息：
1,1,1
1,2,2
1,3,3
1,4,4
输入矩阵A的行数、列数以及非零元个数：
4,1,4
输入矩阵三元组信息：
1,1,1
2,1,2
3,1,3
4,1,4
输出的矩阵为：
30
二、概要设计
为实现上述算法，选择矩阵三元组为本程序的存储结构。
1、基本操作：
Input（）
操作结果：
构造矩阵
Output（）
初始条件：
矩阵已经存在
操作结果：
输出矩阵
Transpose（）
初始条件：
矩阵已经存在
操作结果：
转置输入的矩阵
Add（）
初始条件：
矩阵A与矩阵B已经存在
操作结果：
求矩阵A与矩阵B的和
Sub（）
初始条件：
矩阵A与矩阵B已经存在
操作结果：
求矩阵A与矩阵B的差
Mul（）
初始条件：
矩阵A与矩阵B已经存在
操作结果：
求矩阵A与矩阵B的积
2、本程序包括三个模块：
（1）主程序模块
（2）构造矩阵模块
（3）矩阵运算模块
1）矩阵转置模块
2）矩阵加法模块
3）矩阵减法模块
4）矩阵乘法模块
（4）输出矩阵模块
3、模块调用关系图
主程序模块
构造矩阵模块
矩阵运算模块
矩阵转置模块
矩阵加法模块
矩阵减法模块
矩阵乘法模块
输出矩阵模块
三详细设计
1、定义存储矩阵三元组结构：
（1）定义存储三元组结构：
#include
#include
#defineMaxsize12500//定义矩阵的非零元的个数最大为12500
typedefstruct
{
inti,j;
inte;
}Triple;
typedefstruct
{
Tripledata[Maxsize+1];
intmu,nu,tu;
}TSMatrix,*Matrix;
TSMatrixT,M,S;
2、每个模块的分析：
（1）主程序模块：
voidmain（）
{
intm;
printf（"********************************************************************************"）;
printf（"*********************************矩阵运算器*********************************"）;
printf（"********************************************************************************"）;
printf（"\n"）;
printf（"请选择需要的矩阵运算：
\n1、矩阵的转置\n2、矩阵的加法\n3、矩阵的减法\n4、矩阵的乘法\n"）;
scanf（"%d",&m）;
if（m==1）
{
printf（"矩阵转置运算\n"）;
printf（"\n"）;
Input（T）;
printf（"矩阵为：
\n"）;
Output（T）;
Transpose（T,M）;
printf（"转置矩阵为：
\n"）;
Output（M）;
}
elseif（m==2）
{
printf（"矩阵加法运算\n"）;
printf（"\n"）;
Input（T）;
printf（"矩阵A为：
\n"）;
Output（T）;
Input（M）;
printf（"矩阵B为：
\n"）;
Output（M）;
Add（T,M,S）;
printf（"矩阵A与B的和为：
\n"）;
Output（S）;
}
elseif（m==3）
{
printf（"矩阵减法运算\n"）;
printf（"\n"）;
Input（T）;
printf（"矩阵A为：
\n"）;
Output（T）;
Input（M）;
printf（"矩阵B为：
\n"）;
Output（M）;
Sub（T,M,S）;
printf（"矩阵A与B的差为：
\n"）;
Output（S）;
}
elseif（m==4）
{
printf（"矩阵乘法运算\n"）;
printf（"\n"）;
Input（T）;
printf（"矩阵A为：
\n"）;
Output（T）;
Input（M）;
printf（"矩阵B为：
\n"）;
Output（M）;
Mul（T,M,S）;
printf（"矩阵A与B的积为：
\n"）;
Output（S）;
}
elseprintf（"Error"）;
}
（2）构造矩阵模块：
voidInput（TSMatrix&T）
{
inti;
printf（"请输入矩阵的行数、列数以及非零元的个数：
\n"）;
scanf（"%d,%d,%d",&T.mu,&T.nu,&T.tu）;
printf（"请用三元组形式输入矩阵的元素（行,列,非零元素）:
\n"）;
for（i=1;i<=T.tu;i++）//记录矩阵中非零元的信息
{
scanf（"%d,%d,%d",&T.data[i].i,&T.data[i].j,&T.data[i].e）;
}
}
（3）矩阵运算模块：
1）矩阵转置模块：
voidTranspose（TSMatrixT,TSMatrix&M）//矩阵的置换
{
intp,q,m;
M.mu=T.mu;
M.nu=T.nu;
M.tu=T.tu;
if（M.tu）
{
m=1;
for（p=1;p<=T.mu;p++）
for（q=1;q<=T.nu;q++）
{
M.data[m].i=T.data[m].j;
M.data[m].j=T.data[m].i;
M.data[m].e=T.data[m].e;
++m;
}
}
}
2）矩阵加法模块：
voidAdd（TSMatrixT,TSMatrixM,TSMatrix&S）//矩阵的加法
{
intk1,l1,n1;
intk2,l2,n2;
intn=1;
Matrixp,q;
p=&T;
q=&M;
S.mu=T.mu;
S.nu=T.nu;
for（k1=1,n1=1,k2=1,n2=1;k1<=p->mu,k2<=q->mu;k1++,k2++）
for（l1=1,l2=1;l1<=p->nu,l2<=q->nu;l1++,l2++）
{
if（p->data[n1].i==k1&&p->data[n1].j==l1）
{
if（q->data[n2].i==k2&&q->data[n2].j==l2）
{
S.data[n].i=k1;
S.data[n].j=l1;
S.data[n].e=p->data[n1].e+q->data[n2].e;
n1++;
n2++;
n++;
}
else
{
S.data[n].i=k1;
S.data[n].j=l1;
S.data[n].e=p->data[n1].e;
n++;
n1++;
}
}
else
{
if（q->data[n2].i==k2&&q->data[n2].j==l2）
{
S.data[n].i=k1;
S.data[n].j=l1;
S.data[n].e=q->data[n2].e;
n++;
n2++;
}
else
{
S.data[n].i=k1;
S.data[n].j=l1;
S.data[n].e=0;
n++;
}
}
}
}
3）矩阵减法模块：
voidSub（TSMatrixT,TSMatrixM,TSMatrix&S）//矩阵的减法
{
intk1,l1,n1;
intk2,l2,n2;
intn=1;
Matrixp,q;
p=&T;
q=&M;
S.mu=T.mu;
S.nu=T.nu;
for（k1=1,n1=1,k2=1,n2=1;k1<=p->mu,k2<=q->mu;k1++,k2++）
for（l1=1,l2=1;l1<=p->nu,l2<=q->nu;l1++,l2++）
{
if（p->data[n1].i==k1&&p->data[n1].j==l1）
{
if（q->data[n2].i==k2&&q->data[n2].j==l2）
{
S.data[n].i=k1;
S.data[n].j=l1;
S.data[n].e=p->data[n1].e-q->data[n2].e;
n1++;
n2++;
n++;
}
else
{
S.data[n].i=k1;
S.data[n].j=l1;
S.data[n].e=p->data[n1].e;
n++;
n1++;
}
}
else
{
if（q->data[n2].i==k2&&q->data[n2].j==l2）
{
S.data[n].i=k1;
S.data[n].j=l1;
S.data[n].e=0-q->data[n2].e;
n++;
n2++;
}
else
{
S.data[n].i=k1;
S.data[n].j=l1;
S.data[n].e=0;
n++;
}
}
}
}
4）矩阵乘法模块：
voidMul（TSMatrixT,TSMatrixM,TSMatrix&S）//矩阵的乘法
{
intl1,n1;
intk2,n2;
intk,l,n=1;
Matrixp,q;
p=&T;
q=&M;
if（T.nu!
=M.mu）printf（"Error"）;
S.mu=T.mu;
S.nu=M.nu;
for（k=1;k<=T.mu;k++）
for（l=1;l<=M.nu;l++）
{
S.data[n].i=k;
S.data[n].j=l;
S.data[n].e=0;
for（l1=1,k2=1,n1=1,n2=1;l1<=T.nu,k2<=M.mu;l1++,k2++）
{
if（（p->data[n1].i==k&&p->data[n1].j==l1）&&（q->data[n2].i==k2&&q->data[n2].j==l））
{
S.data[n].e=T.data[n1].e*M.data[n2].e+S.data[n].e;
n1++;
n2++;
}
elseif（（p->data[n1].i==k&&p->data[n1].j==l1）&&（q->data[n2].i!
=k2||q->data[n2].j!
=l））
{
S.data[n].e=0+S.data[n].e;
n1++;
}
elseif（（p->data[n1].i!
=k||p->data[n1].j!
=l1）&&（q->data[n2].i==k2&&q->data[n2].j==l））
{
S.data[n].e=0+S.data[n].e;
n2++;
}
elseS.data[n].e=0+S.data[n].e;
}
n++;
}
}
（4）输出矩阵模块：
voidOutput（TSMatrixT）//通过输入的三元组信息输出矩阵
{
intk,l,n;
Matrixp;
p=&T;
for（k=1,n=1;k<=p->mu;k++）
{
for（l=1;l<=p->nu;l++）
{
if（p->data[n].i==k&&p->data[n].j==l）
{
printf（"%5d",p->data[n].e）;
n++;
}
else
printf（"%5d",0）;
}
printf（"\n"）;
}
printf（"\n"）;
}
voidTranspose（TSMatrixT,TSMatrix&M）//矩阵的置换
{
intp,q,m;
M.mu=T.mu;
M.nu=T.nu;
M.tu=T.tu;
if（M.tu）
{
m=1;
for（p=1;p<=T.mu;p++）
for（q=1;q<=T.nu;q++）
{
M.data[m].i=T.data[m].j;
M.data[m].j=T.data[m].i;
M.data[m].e=T.data[m].e;
++m;
}
}
}
3、模块调用关系图：
main（）
Input（）
Transpose（）
Add（）
Sub（）
Mul（）
Output（）
四使用说明、测试分析及结果
1、程序使用说明：
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示的提示信息：
*********************************************************************
***************************矩阵运算器****************************
*********************************************************************
请选择需要的矩阵运算：
1、矩阵的转置
2、矩阵的加法
3、矩阵的减法
4、矩阵的乘法
—>输入需要的矩阵运算
若选择1：
矩阵转置运算
请输入矩阵的行数、列数以及非零元的个数：
—>输入矩阵的行数、列数以及非零元的个数
请用三元组形式输入矩阵的元素（行,列,非零元素）:
—>输入矩阵三元组信息
矩阵为：
—>输出输入的矩阵
转置矩阵为：
—>输出转置矩阵
若选择2：
矩阵加法运算
请输入矩阵的行数、列数以及非零元的个数：
—>输入矩阵的行数、列数以及非零元的个数
请用三元组形式输入矩阵的元素（行,列,非零元素）:
—>输入矩阵三元组信息
矩阵A为：
—>输出矩阵A
请输入矩阵的行数、列数以及非零元的个数：
—>输入矩阵的行数、列数以及非零元的个数
请用三元组形式输入矩阵的元素（行,列,非零元素）:
—>输入矩阵三元组信息
矩阵B为：
—>输出矩阵B
矩阵A与B的和为：
—>输出A与B的和
若选择3：
矩阵减法运算
请输入矩阵的行数、列数以及非零元的个数：
—>输入矩阵的行数、列数以及非零元的个数
请用三元组形式输入矩阵的元素（行,列,非零元素）:
—>输入矩阵三元组信息
矩阵A为：
—>输出矩阵A
请输入矩阵的行数、列数以及非零元的个数：
—>输入矩阵的行数、列数以及非零元的个数
请用三元组形式输入矩阵的元素（行,列,非零元素）:
—>输入矩阵三元组信息
矩阵B为：
—>输出矩阵B
矩阵A与B的差为：
—>输出A与B的差
若选择4：
矩阵乘法运算
请输入矩阵的行数、列数以及非零元的个数：
—>输入矩阵的行数、列数以及非零元的个数
请用三元组形式输入矩阵的元素（行,列,非零元素）:
—>输入矩阵三元组信息
矩阵A为：
—>输出矩阵A
请输入矩阵的行数、列数以及非零元的个数：
—>输入矩阵的行数、列数以及非零元的个数
请用三元组形式输入矩阵的元素（行,列,非零元素）:
—>输入矩阵三元组信息
矩阵B为：
—>输出矩阵B
矩阵A与B的积为：
—>输出A与B的积
2、测试结果：
（1）矩阵的转置：
输入：
请输入矩阵的行数、列数以及非零元的个数：
3,3,2
请用三元组形式输入矩阵的元素（行,列,非零元素）:
1,1,1
2,3,1
矩阵为：
100
001
000
输出：
转置矩阵为：
100
000
000
（2）矩阵的加法：
输入：
请输入矩阵的行数、列数以及非零元的个数：
3,3,2
请用三元组形式输入矩阵的元素（行,列,非零元素）:
1,1,1
2,3,1
请输入矩阵的行数、列数以及非零元的个数：
3,3,2
请用三元组形式输入矩阵的元素（行,列,非零元素）:
1,1,1
2,2,1
输出：
矩阵A为：
100
001
000
矩阵B为：
100
010
000
矩阵A与B的和为：
200
011
000
（3）矩阵的减法：
请输入矩阵的行数、列数以及非零元的个数：
3,3,2
请用三元组形式输入矩阵的元素（行,列,非零元素）:
1,1,1
2,3,1
请输入矩阵的行数、列数以及非零元的个数：
3,3,2
请用三元组形式输入矩阵的元素（行,列,非零元素）:
1,1,1
2,2,1
输出：
矩阵A为：
100
001
000
矩阵B为：
100
010
000
矩阵A与B的差为：
000
0-11
000
（4）矩阵的乘法：
请输入矩阵的行数、列数以及非零元的个数：
1,4,4
请用三元组形式输入矩阵的元素（行,列,非零元素）:
1,1,1
1,2,2
1,3,3
1,4,4
请输入矩阵的行数、列数以及非零元的个数：
4,1,4
请用三元组形式输入矩阵的元素（行,列,非零元素）:
1,1,1
2,1,2
3,1,3
4,1,4
输出：
矩阵A为：
1234
矩阵B为：
1
2
3
4
矩阵A与B的积为：
30
3、运行界面：
（1）矩阵的转置：
（2）矩阵的加法：
（3）矩阵的减法：
（4）矩阵的乘法：
五、实验总结
使用三元组存储矩阵信息，优点在于节省存储空间，但不便于矩阵的输出与各种运算，这需要我们对结构体和数组的运算十分熟悉，这个程序可以实现矩阵的转置、加法、减法和乘法四种运算，但是在输入矩阵三元组信息的时候需要按顺序输入，这个程序还可以在输入和输出的结构上进行调整，使存储空间减小，希望以后能写出更加巧妙地程序。
教师评语：
实验成绩：
指导教师签名：
批阅日期：
升级会员 