数据结构课程教学设计(稀疏矩阵运算器).doc
-/实习报告题目：编制一个稀疏矩阵运算器的程序班级：智能科学与技术系 姓名：尤雅萍 学号：31520082204064 完成日期：2009-11-27一需求分析1.【问题描述】 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2.【基本要求】 以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加，相减和相乘的运算，稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。3.【测试数据】（1）10 0 0 0 0 0 10 0 0 0 0 9 + 0 0 -1 = 0 0 8 -1 0 0 1 0 -3 0 0 -3（2）10 0 0 0 10 0 0 9 - 0 -1 = 0 10 -1 0 1 -3 -2 3（3）4 -3 0 0 1 3 0 0 0 -6 0 0 0 0 8 0 4 2 0 8 0 0 0 0 1 0 0 * 0 1 0 = 0 1 0 0 0 0 0 70 1 0 0 0 0 0 0 0 04.【实现提示】（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行，列数对于所要求作的运算是否匹配，可设矩阵的行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。（3）在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。二概要设计1. 设定数组的抽象数据类型定义：ADT SparseMatrix数据对象：D= m和n分别称为矩阵的行数和列数数据关系：R=Row，ColRow=|1=i=m，a=j=n-1 Col=|1=i=m-1，a=jmu,&T-nu,&T-tu);printf(n);if(T-tuMAXSIZE|T-mu21)printf(非零个数超出定义范围！出错！);exit(0);for(k=1;ktu;k+)printf(请输入第%d个非零元素的行数,列数及其值: ,k);scanf(%d%d%d,&T-datak.i,&T-datak.j,&T-datak.e);void AddRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /稀疏矩阵相加int p,q,k=1;if(M.mu!=N.mu|M.nu!=N.nu)printf(你的输入不满足矩阵相加的条件!n);exit(1);Q-mu=M.mu;Q-nu=M.nu;for(p=1,q=1;p=M.tu&qdatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e+N.dataq.e;p+;q+;k+;else if(M.datap.jdatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e;k+;p+;else if(M.datap.jN.dataq.j)Q-datak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=N.dataq.e;k+;p+;else if(M.datap.idatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e;k+;p+;else if(M.datap.iN.dataq.i)Q-datak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=N.dataq.e;k+;q+;if(p!=M.tu+1)for(;pdatak.i=M.datap.i;Q-datak.j=M.datap.j; Q-datak.e=M.datap.e;k+;if(q!=N.tu+1)for(;qdatak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=N.dataq.e;k+;void SubRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /稀疏矩阵相减int p,q,k=1;if(M.mu!=N.mu|M.nu!=N.nu)printf(你的输入不满足矩阵相减的条件!n);exit(1);Q-mu=M.mu;Q-nu=M.nu;for(p=1,q=1;p=M.tu&qdatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e-N.dataq.e;p+;q+;k+;else if(M.datap.jdatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e;k+;p+;else if(M.datap.jN.dataq.j)Q-datak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=-N.dataq.e;k+;p+;else if(M.datap.idatak.i=M.datap.i;Q-datak.j=M.datap.j;Q-datak.e=M.datap.e;k+;p+;else if(M.datap.iN.dataq.i)Q-datak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=-N.dataq.e;k+;q+;if(p!=M.tu+1)for(;pdatak.i=M.datap.i;Q-datak.j=M.datap.j; Q-datak.e=M.datap.e;k+;if(q!=N.tu+1)for(;qdatak.i=N.dataq.i;Q-datak.j=N.dataq.j;Q-datak.e=-N.dataq.e;k+;int MulTSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) /稀疏矩阵相乘int ccol=0,tp,brow,t,arow,p,q,i;int ctempMAXSIZE+1;if(M.nu!=N.mu) printf(你的输入不满足矩阵相乘的条件!n);return 0; Q-mu=M.mu;Q-nu=N.nu;Q-tu=0;if(M.tu*N.tu!=0)for(arow=1;arow=M.mu;+arow)for(i=1;irposarow=Q-tu+1;if(arowM.mu) tp=M.rposarow+1;else tp=M.tu+1;for(p=M.rposarow;ptp;+p)brow=M.datap.j;if(browN.mu) t=N.rposbrow+1;else t=N.tu+1;for(q=N.rposbrow;qt;+q)ccol=N.dataq.j;ctempccol+=M.datap.e*N.dataq.e;for(ccol=1;ccolnu;+ccol)if(ctempccol)if(+Q-tuMAXSIZE) return 0;Q-dataQ-tu.i=arow;Q-dataQ-tu.j=ccol;Q-dataQ-tu.e=ctempccol;return 1;void PrintSMatrix(RLSMatrix Q) /输出稀疏矩阵int k=1,row,line;printf(n运算结果: );if(Q.tu=0) printf(0);elsefor(row=1;row=Q.mu;row+)for(line=1;linetu的值，导致在输出函数里没有执行针对该情况的if判断语句。在加减函数里，每增加一个非零元，Q-tu加一。（3） 问题：输出矩阵时，输出界面不整齐，非标准矩阵形式。解决：利用n t及空格号使界面比较美观。五、用户手册1本程序的运行环境为XP操作系统，执行文件为：shiyan2.exe。2进入演示程序后的界面：
收藏
编号：2607469
类型：共享资源
大小：135.67KB
格式：DOC
上传时间：2020-04-23
8
金币
- 关 键 词：
-
数据结构
课程
教学
设计
稀疏
矩阵
运算器
- 资源描述：
-
-/
实习报告
题目：编制一个稀疏矩阵运算器的程序
班级：智能科学与技术系 姓名：尤雅萍 学号：31520082204064
完成日期：2009-11-27
一•需求分析
1.【问题描述】
稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。
2.【基本要求】
以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加，相减和相乘的运算，稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。
3.【测试数据】
（1）10 0 0 0 0 0 10 0 0
0 0 9 + 0 0 -1 = 0 0 8
-1 0 0 1 0 -3 0 0 -3
（2）10 0 0 0 10 0
0 9 - 0 -1 = 0 10
-1 0 1 -3 -2 3
（3）4 -3 0 0 1 3 0 0 0 -6 0
0 0 0 8 0 4 2 0 8 0 0
0 0 1 0 0 * 0 1 0 = 0 1 0
0 0 0 0 70 1 0 0 0 0 0
0 0 0
4.【实现提示】
（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行，列数对于所要求作的运算是否匹配，可设矩阵的行数和列数均不超过20。
（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。
（3）在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。
二•概要设计
1. 设定数组的抽象数据类型定义：
ADT SparseMatrix{
数据对象：D={ m和n分别称为矩阵的行数和列数}
数据关系：R={Row，Col}
Row={
|1<=i<=m，a<=j<=n-1 }
Col={|1<=i<=m-1，a<=j<=n }
基本操作：
CreateSMatrix(&M);
操作结果：创建稀疏矩阵M。
DestorySMatrix(&M);
初始条件：稀疏矩阵M存在。
操作结果：销毁稀疏矩阵M。
PrintSMatrix(M)；
初始条件：稀疏矩阵M存在。
操作结果: 输出稀疏矩阵M。
CopySMatrix(M,&T)；
初始条件：稀疏矩阵M存在。
操作结果：由稀疏矩阵M复制得到T。
AddSMatrix(M,N,&Q)；
初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵的和Q=M+N。
SubtSMatrix(M,N,&Q);
初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵的差Q=M-N。
MultSMatrix(M,N,&Q);
初始条件：稀疏矩阵M的列数等于N的行数。
操作结果：求稀疏矩阵乘积Q=M*N。
TransposeSMatrix(M,&T);
初始条件：稀疏矩阵M 存在。
操作结果：求稀疏矩阵M的转置矩阵T。
}ADT SparseMatrix
2．本程序包含的模块
（1）void main()
{
初始化；
do{ 接收命令；处理命令；}while(命令！=退出)；
}
（2）稀疏矩阵模块——实现稀疏矩阵抽象数据类型。
（3）稀疏矩阵求值模块——实现稀疏矩阵求值抽象数据类型。
稀疏矩阵求值模块包括：矩阵相加模块AddRLSMatrix()；
矩阵相减模块SubRLSMatrix()；相乘模块MulTSMatrix()；
三•详细设计
typedef struct //稀疏矩阵的三元组顺序表存储表示
int i,j; //该非零元的行下标和列下标
int e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]; //非零元三元组表，data[0]未用
int rpos[MAXRC+1]; //各行第一个非零元的位置表
int mu,nu,tu; //矩阵的行数列数和非零元的个数
}RLSMatrix;
Void CreateSMatrix(RLSMatrix *T) //输入创建稀疏矩阵
{
int k;
printf(" \n请输入矩阵行数、列数及非零元个数: ");
scanf("%d%d%d",&T->mu,&T->nu,&T->tu);
printf("\n");
if(T->tu>MAXSIZE||T->mu>21)
{
printf("非零个数超出定义范围！出错！");
exit(0);
}
for(k=1;k<=T->tu;k++)
{
printf("请输入第%d个非零元素的行数,列数及其值: ",k);
scanf("%d%d%d",&T->data[k].i,&T->data[k].j,&T->data[k].e);
}
}
void AddRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) //稀疏矩阵相加
{
int p,q,k=1;
if(M.mu!=N.mu||M.nu!=N.nu)
{
printf("你的输入不满足矩阵相加的条件!\n");
exit(1);
}
Q->mu=M.mu;Q->nu=M.nu;
for(p=1,q=1;p<=M.tu&&q<=N.tu;)
{
if(M.data[p].i==N.data[q].i)
{
if(M.data[p].j==N.data[q].j)
{
Q->data[k].i=M.data[p].i;
Q->data[k].j=M.data[p].j;
Q->data[k].e=M.data[p].e+N.data[q].e;
p++;q++;k++;
}
else if(M.data[p].jdata[k].i=M.data[p].i;
Q->data[k].j=M.data[p].j;
Q->data[k].e=M.data[p].e;
k++;p++;
}
else if(M.data[p].j>N.data[q].j)
{
Q->data[k].i=N.data[q].i;
Q->data[k].j=N.data[q].j;
Q->data[k].e=N.data[q].e;
k++;p++;
}
}
else if(M.data[p].idata[k].i=M.data[p].i;
Q->data[k].j=M.data[p].j;
Q->data[k].e=M.data[p].e;
k++;p++;
}
else if(M.data[p].i>N.data[q].i)
{
Q->data[k].i=N.data[q].i;
Q->data[k].j=N.data[q].j;
Q->data[k].e=N.data[q].e;
k++;q++;
}
}
if(p!=M.tu+1)
for(;p<=M.tu;p++)
{
Q->data[k].i=M.data[p].i;
Q->data[k].j=M.data[p].j;
Q->data[k].e=M.data[p].e;
k++;
}
if(q!=N.tu+1)
for(;q<=N.tu;q++)
{
Q->data[k].i=N.data[q].i;
Q->data[k].j=N.data[q].j;
Q->data[k].e=N.data[q].e;
k++;
}
}
void SubRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) //稀疏矩阵相减
{
int p,q,k=1;
if(M.mu!=N.mu||M.nu!=N.nu)
{
printf("你的输入不满足矩阵相减的条件!\n");
exit(1);
}
Q->mu=M.mu;Q->nu=M.nu;
for(p=1,q=1;p<=M.tu&&q<=N.tu;)
{
if(M.data[p].i==N.data[q].i)
{
if(M.data[p].j==N.data[q].j)
{
Q->data[k].i=M.data[p].i;
Q->data[k].j=M.data[p].j;
Q->data[k].e=M.data[p].e-N.data[q].e;
p++;q++;k++;
}
else if(M.data[p].jdata[k].i=M.data[p].i;
Q->data[k].j=M.data[p].j;
Q->data[k].e=M.data[p].e;
k++;p++;
}
else if(M.data[p].j>N.data[q].j)
{
Q->data[k].i=N.data[q].i;
Q->data[k].j=N.data[q].j;
Q->data[k].e=-N.data[q].e;
k++;p++;
}
}
else if(M.data[p].idata[k].i=M.data[p].i;
Q->data[k].j=M.data[p].j;
Q->data[k].e=M.data[p].e;
k++;p++;
}
else if(M.data[p].i>N.data[q].i)
{
Q->data[k].i=N.data[q].i;
Q->data[k].j=N.data[q].j;
Q->data[k].e=-N.data[q].e;
k++;q++;
}
}
if(p!=M.tu+1)
for(;p<=M.tu;p++)
{
Q->data[k].i=M.data[p].i;
Q->data[k].j=M.data[p].j;
Q->data[k].e=M.data[p].e;
k++;
}
if(q!=N.tu+1)
for(;q<=N.tu;q++)
{
Q->data[k].i=N.data[q].i;
Q->data[k].j=N.data[q].j;
Q->data[k].e=-N.data[q].e;
k++;
}
}
int MulTSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) //稀疏矩阵相乘
{
int ccol=0,tp,brow,t,arow,p,q,i;
int ctemp[MAXSIZE+1];
if(M.nu!=N.mu)
{
printf("你的输入不满足矩阵相乘的条件!\n");
return 0;
}
Q->mu=M.mu;
Q->nu=N.nu;
Q->tu=0;
if(M.tu*N.tu!=0)
{
for(arow=1;arow<=M.mu;++arow)
{
for(i=1;i<=N.nu;i++)
ctemp[i]=0;
Q->rpos[arow]=Q->tu+1;
if(arownu;++ccol)
{
if(ctemp[ccol])
{
if(++Q->tu>MAXSIZE) return 0;
Q->data[Q->tu].i=arow;
Q->data[Q->tu].j=ccol;
Q->data[Q->tu].e=ctemp[ccol];
}
}
}
}
return 1;
}
void PrintSMatrix(RLSMatrix Q) //输出稀疏矩阵
{
int k=1,row,line;
printf("\n运算结果: ");
if(Q.tu==0) printf("0");
else
{
for(row=1;row<=Q.mu;row++)
{
for(line=1;line<=Q.nu;line++)
{
if(Q.data[k].i==row&&Q.data[k].j==line)printf("%d ",Q.data[k++].e);
else printf("0 ");
}
printf("\n\t ");
}
}
}
void main()
{
RLSMatrix M,N,Q;
int i;
do
{
printf("\t\t***************************\n");
printf("\t\t 稀疏矩阵运算器\n");
printf("\t\t***************************\n\n");
printf("\t\t 1.矩阵相加\n\n");
printf("\t\t 2.矩阵相减\n\n");
printf("\t\t 3.矩阵相乘\n\n");
printf("\t\t 4.退出\n\n");
printf("\t\t 请选择: ");
scanf("%d",&i);
if(i==4) goto end;
else
{
printf("\n请输入第一个矩阵M:\n");
CreateSMatrix(&M);
printf("\n请输入第二个矩阵N:\n");
CreateSMatrix(&N);
switch(i)
{
case 1:AddRLSMatrix(M,N,&Q);break;
case 2:SubRLSMatrix(M,N,&Q);break;
case 3:MulTSMatrix(M,N,&Q);break;
default:break;
}
}
PrintSMatrix(Q);
getchar();
getchar();
end: ;
}while(i!=4);
}
四•调试分析
（1） 问题：运行过程中发现加法减法能正常运行，而乘法却在存储数据步骤就出现问题。
解决：经检查发现，由于在创建稀疏矩阵时没有输入矩阵相应的各行第一非零元的位置，所以在进行乘法运算时找不到矩阵的rpos值。将rpos补上，乘法函数即可正常运行。
（2） 问题：当加减结果为零矩阵时，输出结果是一个由0构成的矩阵，而不是数值0。
解决：经检查发现，加减法函数过程中没有判断Q->tu的值，导致在输出函数里没有执行针对该情况的if判断语句。在加减函数里，每增加一个非零元，Q->tu加一。
（3） 问题：输出矩阵时，输出界面不整齐，非标准矩阵形式。
解决：利用\n \t及空格号使界面比较美观。
五、用户手册
1．本程序的运行环境为XP操作系统，执行文件为：shiyan2.exe。
2．进入演示程序后的界面：
展开阅读全文
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
