稀疏矩阵相关操作的实现

1、数据结构课程设计设计说明书稀疏矩阵相关操作的实现学生姓名 张美燕 学 号 1118014066 班 级 计本1102班 成 绩 指导教师 曹阳 数学与计算机科学学院2013年9月22日 课程设计任务书20132014学年第一学期课程设计名称： 数据结构课程设计 课程设计题目： 稀疏矩阵相关操作的实现 完 成 期 限：自 2013年 9月9日至 2013年 9月 22日共 2 周设计内容：1.任务说明用C/C+编写一个程序实现稀疏矩阵相关操作。2.要求1）阐述设计思想，画出流程图。2）主要功能： （1）输入相关数据建立稀疏矩阵； （2）实现稀疏矩阵转置； （3）实现两个稀疏矩阵相乘。3）从时间、

2、空间对算法分析；4）较好的界面设计；5）编写课程设计报告。指导教师：曹阳 教研室负责人：曹阳课程设计评阅评语： 指导教师签名： 年 月 日摘 要假设在m*n的矩阵中，有t个元素不为零。令a=t/（m*n），称a为矩阵的稀疏因子，通常认为a<=0.05时称为稀疏矩阵。设计了一个稀疏矩阵相关操作实现的软件，具有实现矩阵转置和实现两个矩阵相乘的功能。采用三元组顺序表法来实现稀疏矩阵的存储，操作软件采用VC+6.0作为软件开发的环境。界面清晰易懂，操作简单易学，便于为用户所接受。关键词：稀疏矩阵；三元组；VC+6.0；转置；函数目 录1 课题描述.12 算法描述.23程序源代码.4 程序调试与测

3、试.115 结果分析.146 总结.15 参考文献.161 课题描述 设计了一个稀疏矩阵相关操作实现的软件。稀疏矩阵是指假设在m*n的矩阵中，有t个元素不为零。令a=t/（m*n），称a为矩阵的稀疏因子，通常认为a<=0.05时称为稀疏矩阵。软件具有实现矩阵转置和实现两个矩相乘的功能，采用三元组顺序表法来实现稀疏矩阵的存储。操作软件采用VC+6.0作为软件开发的环境。2 算法描述1) 算法思想 利用稀疏矩阵的非零元少的特点，采用三元组顺序表进行压缩存储。实现转置是将矩阵的行列值相互交换，将每个三元组中的i和j相互调换，重排三元组之间的次序即可实现矩阵的转置。两个矩阵相乘是对于M中每个元素

4、M.datap(p=1,2,.M.tu)，找到N中所有满足条件M.datap.j=N.dataq.i的元素N.dataq，求得M.datap.v和N.dataq.v的乘积，乘积矩阵Q中每个元素的值是个累积和，为了便于操作，应对每个元素设一累积和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计的变量上。测试矩阵M、N如图2-1所示： M N 0 2 0 0 0 5 0 1 2 0 0 3 图2-1 测试矩阵 2） 算法流程图 主函数流程图如图2-2所示： 开始调用菜单函数输入mm?调用Print()调用转置函数调用相乘函数有误 1 2 3 4 default 转下页调用

5、Print()调用Print() 结束 接上页 图 2-2 主函数流程图稀疏矩阵转置流程图如图2-3所示：Col<=M.nu?Numcol=0+Col t=1开始T.mu=M.nuT.nu=M.muT.tu=M.tuT.tu=0?Col=1是 否否 是 接下页 接上页t<=M.tu?否 +t+numM.datat.j 是Cpot1=1Col=2Col<=M.nu?否 +Col 是 Cpotcol=Cpotcol-1+numcol-1 P=1P<=M.tu?否 +p 是Col=M.datap.j;q=Cpotcol;T.dataq.i=M.datap.j;T.dataq.

6、j=M.datap.i;T.dataq.e=M.datap.e;+Cpotcol; 结束 图 2-3 矩阵转置流程图矩阵相乘流程图如图2-4所示：3程序源代码#include<stdio.h>#define MAXSIZE 100typedef structint i,j; int e;Triple;typedef structTriple dataMAXSIZE+1; int mu,nu,tu;TSMatrix;int GreatSMatrix(TSMatrix &M)int MaMAXSIZE/2MAXSIZE/2; int i,j;M.tu=0;printf(&quo

7、t;请输入矩阵的行、列数（中间用逗号隔开）：");scanf("%d,%d",&M.mu,&M.nu);printf("请输入数据:");for(i=1;i<=M.mu;i+)for(j=1;j<=M.nu;j+)scanf("%d",&Maij);for(i=1;i<=M.mu;i+)for(j=1;j<=M.nu;j+)if(Maij!=0) M.tu+;M.dataM.tu.i=i;M.dataM.tu.j=j;M.dataM.tu.e=Maij;if(M.tu/(M.m

8、u*M.nu)>0.05) return 0;return 1;int FastTransposeSMatrix(TSMatrix M,TSMatrix &T)/转置int p,q,col,t,numMAXSIZE+1,cpotMAXSIZE+1;T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu)for(col=1;col<=M.nu;+col)numcol=0;for(t=1;t<=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col<=M.nu;+col)cpotcol=cpotcol-1+nu

9、mcol-1;for(p=1;p<=M.tu;+p)col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol;return 1;void print(TSMatrix M)/显示int i,j,k=1;printf("该稀疏矩阵为n");for(i=1;i<=M.mu;i+)for(j=1;j<=M.nu;j+)if(i=M.datak.i&&j=M.datak.j) printf("%3d &

10、quot;,M.datak.e);+k;else printf("%3d ",0);printf("n");printf("矩阵中存储的数据为: ");for(i=1;i<=M.tu;+i)printf("(%d,%d,%d)",M.datai.i,M.datai.j,M.datai.e);if(i<M.tu) printf(",");printf("n");int MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q

11、)int i,j,k=1,q=1;int MaMAXSIZE/2MAXSIZE/2=0;int NaMAXSIZE/2MAXSIZE/2=0;int QaMAXSIZE/2MAXSIZE/2;if(M.nu!=N.mu)printf("这两个矩阵不能相乘!n");return 0; Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;for(i=1;i<=MAXSIZE/2;i+)for(j=1;j<=MAXSIZE/2;j+)if(i=M.datak.i&&j=M.datak.j) Maij=M.datak.e;+k;/else Maij

12、=0; if(i=N.dataq.i&&j=N.dataq.j) Naij=N.dataq.e;+q;/else Naij=0;for(i=1;i<=M.mu;+i)for(j=1;j<=N.nu;+j)Qaij=0;for(k=1;k<=M.nu;+k)Qaij+=Maik*Nakj;for(i=1;i<=Q.mu;i+)for(j=1;j<=Q.nu;j+)if(Qaij!=0) Q.tu+;Q.dataQ.tu.i=i;Q.dataQ.tu.j=j;Q.dataQ.tu.e=Qaij;return 1;void caidan()printf(

13、"<1>、创建矩阵n");printf("<2>、矩阵转置n");printf("<3>、矩阵相乘n");printf("<4>、退出n");void main()TSMatrix M,N,P,Q;int m;M.tu=0;caidan();while(1)printf("请选择：");fflush(stdin);scanf("%d",&m);switch(m)case 1:if(GreatSMatrix(M)=0) p

14、rintf("该矩阵不是稀疏矩阵！n"); break; printf("已成功创建矩阵！n");print(M);break;case 2:if(M.tu=0) printf("矩阵不存在！n"); break; FastTransposeSMatrix(M,N);printf("转置矩阵为：n");print(N);break;case 3:if(M.tu=0) GreatSMatrix(M);GreatSMatrix(P);MultSMatrix(M,P,Q);printf("相乘后的矩阵为：n&q

15、uot;);print(Q);break;case 4:return;default:printf("输入有误，请重新输入：");4 调试与测试1）运行初始界面如图4-1所示： 图4-1 初始界面2）选择1，创建矩阵M，运行界面如图4-2所示：图4-2 M矩阵创建界面2） 选择2，实现矩阵M的转置，运行界面如图4-3所示：图4-3 M矩阵转置界面3） 选择3，实现矩阵M和矩阵N的相乘，运行界面如图4-4所示： 图4-4 M*N矩阵界面4） 选择4，程序结束退出，运行界面如图4-5所示： 图4-5 退出程序界面 5 结果分析 在输入的过程中，如果输入的不是稀疏矩阵，则系统就会提示：该矩阵不是稀疏矩阵！则需要重新输入。在选择两个矩阵相乘时，有一个输入的不是稀疏矩阵，系统会提示：该矩阵不能相乘！不满足两矩阵相乘条件是也会提示：该矩阵不能相乘！ 6 总结 设计了一个稀疏矩阵相关操作实现的软件。软件具有实现矩阵转置和实现两个矩相乘的功能， 利用稀疏矩阵的非零元少的特点，采用三元组顺序表进行压缩存储。操作软件采用VC+6.0作为软件开发的环境。在运行调试过程中，出现了个各种问题，对于函数调用不够运用熟悉，对于相乘矩阵实现过程不够了解，编