数据结构实验报告(实验五_稀疏矩阵运算器).doc

1、 韶 关 学 院 学 生 实 验 报 告 册实验课程名称：数据结构与算法实验项目名称：实验五 数组及其应用稀疏矩阵运算器 实验类型（打 ）：（基础 、综合 、设计 ）院 系：信息工程学院计算机系 专 业：*姓 名：* 学 号：*指导老师：陈正铭 韶关学院教务处编制一、实验预习报告内容 预习日期：2007年 5 月 29日实验预习报告内容原则上应包括实验目的、实验所用的主要仪器药品、实验原理与公式、实验预习疑问等项目。 【实验目的】深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。【需要分析】稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计

2、算效率。实现一个能进行稀疏矩阵基本运算的运算器。要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。输入以三元组表示，输出以通常的阵列形式列出。【软件平台】Windows 2000，Visual C 6.0或WINTC【概要设计】ADT Array 数据对象: D = aij | 0ib1-1, 0 jb2-1数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2 基本操作：CreateSMatrix(&M); /操作结果:创建稀疏矩阵M.Print SMatrix(M); /初始

3、化条件: 稀疏矩阵M存在./操作结果:输出稀疏矩阵M.AddSMatrix(M,N,&Q);/初始化条件: 稀疏矩阵M与N的行数和列数对应相等./操作结果:求稀疏矩阵的和Q=M+N.SubSMatrix(M,N,&Q);/初始化条件: 稀疏矩阵M与N的行数和列数对应相等./操作结果:求稀疏矩阵的差Q=M-N.MultSMatrix(M,N,&Q);/初始化条件: 稀疏矩阵M的列数等于N的行数./操作结果:求稀疏矩阵的乘积Q=M*N. ADT Array 【疑问】（这部分内容因人而异，也可不写）实验预习评分： 二、实验原始（数据）记录实 验 时 间： 2007 年 5 月 30日（星期 三 第

4、7，8 节）实验同组人 ：如有实验实验数据表格，学生在实验预习时应画好实验数据表格，供实验填写数据。请选择所需要的操作功能(A，B，C，D，E，F)A请输入矩阵的行数和列数:行数2列数2非零元素个数:2请按行,列和值的形式输入该矩阵的非零元.并以全零为结束标记!1 2 92 1 -1请选择所需要的操作功能(A，B，C，D，E，F):B请输入矩阵的行数和列数:行数2列数2非零元素个数:2请按行,列和值的形式输入该矩阵的非零元.并以全零为结束标记!1 1 -12 1 -3请选择所需要的操作功能(A，B，C，D，E，F):C加法结果为:|-1 9|-4 0|请选择所需要的操作功能(A，B，C，D，E

5、，F):D减法结果为:|1 9|2 0|请选择所需要的操作功能(A，B，C，D，E，F):E乘法结果为:|-27 0|1 0|指导教师批阅及签名 三、实验报告内容 2007年 5 月 30 日 实验报告内容原则上应包括主要实验步骤、实验数据计算（实验操作）结果、实验结果（疑问）分析等项目。【主程序模块】：void main() 初始化;do 接受命令; 处理命令;while(命令!=“退出”)；【功能模块调用关系图】主程序模块 创建稀疏矩阵模块 运算稀疏矩阵模块 打印稀疏矩阵模块 【详细设计】稀疏矩阵运算器 矩阵相乘 矩阵相加矩阵相减 退出本系统 输入矩阵1输入矩阵1输入矩阵1输入矩阵2输入矩

6、阵2输入矩阵2计算结果计算结果计算结果typedef structint row; /行数int col; /列数int v; /非零元素值triplenode;typedef structtriplenode datamaxsize+1; /非零元三元组int rowtabmaxrow+1; /各行第一个非零元的位置表int mu,nu,tu; /矩阵的行数、列数和非零元个数rtripletable;void creat(rtripletable &A) /创建稀疏矩阵void print(rtripletable A) /输出稀疏矩阵int addsmatrix(rtripletable

7、M, rtripletable N) /矩阵相加int subsmatrix(rtripletable M, rtripletable N) /稀疏矩阵相减void multsmatrix(rtripletable M, rtripletable N, rtripletable &Q) /稀疏矩阵相乘【调试分析】（这部分内容因人而异）1、由于开始对顺序存储的知识还不熟识，在三元组的存储和运用会导致算法低效。2、做到存储的时候，开始时不知道怎样存储三元组，和不知如何去运用它的行数，列数，非零元素。3、在使用选择和循环时，有时因为自己的粗心，把循环的条件弄错了。4、做本程序用到了数组的知识，有时一

8、有不懂的东西又只能打开书来看。5、开始时没有把矩阵的加法和减法的情况考虑全面，导致输出的时候会出现简单的错误。【用户手册】1、本程序的运行环境为Windows me下的Microsofe VC+ 6.0,执行文件为：xishujuzhen.cpp。2、进入演示程序后即显示文本方式的用户界面：- |*稀疏矩阵运算器*| = |= | A、输入矩阵1 | B、输入矩阵2 | C、矩阵相加 | D、矩阵相减 | | E、矩阵相乘 | F、退出本系统 |- 请选择所需要的操作功能(A，B，C，D，E，F) ：3、进入界面后，只要选择数字命令按“回车键”就行。4、接受其他命令后即执行相应的操作和相应的结

9、果。实验报告评分：注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。 【源程序】#include#include#include#define maxsize 100#define maxrow 100#define OK 1#define ERROR -1typedef structint row; /行数int col; /列数int v; /非零元素值triplenode;typedef structtriplenod

10、e datamaxsize+1; /非零元三元组int rowtabmaxrow+1; /各行第一个非零元的位置表int mu,nu,tu; /矩阵的行数、列数和非零元个数rtripletable;void creat(rtripletable &A) /创建稀疏矩阵int k=1,sum=1,loop,p,t;int nummaxrow+1;cout请输入矩阵的行数和列数:endl;coutA.mu;coutA.nu;coutA.tu;cout请按行,列和值的形式输入该矩阵的非零元.并以全零为结束标记!endl;for(loop=1;loopA.dataloop.rowA.dataloop.

11、colA.dataloop.v; /输入三元组的行数，列数和非零元素值for(p=1;p=A.mu;p+) nump=0; /A三元组每一列的非零元素个数for(t=1;t=A.tu;t+) +numA.datat.row; /求A中每一列含非零元个数A.rowtab1=1; /求第p列中第一个非零元在A.data中的序号for(t=2;t=A.mu;t+) A.rowtabt=A.rowtabt-1+numt-1;return;void print(rtripletable A) /输出稀疏矩阵int resultmaxrow+1maxrow+1; /定义一个二维数组int loop1,lo

12、op2;for(loop1=1;loop1=A.mu;loop1+)for(loop2=1;loop2=A.nu;loop2+)resultloop1loop2=0; /初始化为0for(loop1=1;loop1=A.tu;loop1+)resultA.dataloop1.rowA.dataloop1.col=A.dataloop1.v;for(loop1=1;loop1=A.mu;loop1+)cout|;for(loop2=1;loop2=A.nu;loop2+)coutresultloop1loop2; /输出所做运算的结果cout|endl;int addsmatrix(rtripl

13、etable M, rtripletable N) /矩阵相加 if(M.mu!=N.mu) /行数相等才能相加cout出错;rtripletable Q;Q.mu=M.mu;Q.nu=N.nu;int p,q,k;p=1;q=1;k=1;while(p=M.tu&q=N.tu) /两个稀疏矩阵存在if(M.datap.row=N.dataq.row) /两个稀疏矩阵的行数相等if(M.datap.col=N.dataq.col) /两个稀疏矩阵的列数相等 if(M.datap.v+N.dataq.v!=0) /两个稀疏矩阵相加的结果不为0Q.datak.row=M.datap.row;Q.d

14、atak.col=M.datap.col;Q.datak.v=M.datap.v+N.dataq.v;+k;+q;+p;else if(M.datap.colN.dataq.col) /第一个稀疏矩阵列数小于第二个稀疏矩阵列数Q.datak=M.datap; /把M中的所有信息都赋给Q+p;+k;else /第一个稀疏矩阵列数大于第二个稀疏矩阵的列数Q.datak=N.dataq;+q;+k;else if(M.datap.rowN.dataq.row) /第一个稀疏矩阵行列数小于第二个稀疏矩阵行数Q.datak=M.datap;+p;+k;else /第一个稀疏矩阵行列数小于第二个稀疏矩阵行

15、数Q.datak=N.dataq;+q;+k;while(p=M.tu) /只有M并且符合条件Q.datak=M.datap;+p;+k;while(q=N.tu) /只有N并且符合条件Q.datak=N.dataq;+q;+k;Q.tu=k-1;cout加法结果为:endl;print(Q); /调用print()return OK;int subsmatrix(rtripletable M, rtripletable N) /稀疏矩阵相减if(M.mu!=N.mu) /行数相等才能相加cout出错;rtripletable Q;Q.mu=M.mu;Q.nu=N.nu;int p,q,k;p

16、=1;q=1;k=1;while(p=M.tu&q=N.tu) /两个稀疏矩阵存在if(M.datap.row=N.dataq.row) /两个稀疏矩阵的行数相等if(M.datap.col=N.dataq.col) /两个稀疏矩阵的列数相等if(M.datap.v-N.dataq.v!=0) /两个稀疏矩阵相减的结果不为0Q.datak.row=M.datap.row; Q.datak.col=M.datap.col;Q.datak.v=M.datap.v-N.dataq.v;+k;+q;+p; if(M.datap.colN.dataq.col) /第一个稀疏矩阵列数大于第二个稀疏矩阵的列

17、Q.datak.row=N.dataq.row;Q.datak.col=N.dataq.col;Q.datak.v=-N.dataq.v;+q;+k;if(M.datap.rowN.dataq.row) /第一个稀疏矩阵行列数大于第二个稀疏矩阵行数Q.datak.row=N.dataq.row;Q.datak.col=N.dataq.col;Q.datak.v=-N.dataq.v;+q;+k;while(p=M.tu) /只有M并且符合条件Q.datak=M.datap;+p;+kwhile(q=N.tu) /只有N并且符合条件Q.datak.row=N.dataq.row;Q.datak.

18、col=N.dataq.col;Q.datak.v=-N.dataq.v;+q;+k;Q.tu=k-1;cout减法结果为:endlprint(Q); /调用print()return OK; void multsmatrix(rtripletable M, rtripletable N, rtripletable &Q) /稀疏矩阵相乘int arow,brow;int p,q,tp,t;int ccol;int ctempmaxrow+1; /定义累加器if(M.nu!=N.mu)return;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0; /Q初始化if(M.tu*N.tu!=0

19、) /Q是非零矩阵for(arow=1;arow=M.mu;arow+) /处理M的每一行for(p=1;p=Q.nu;p+) /处理M的每一列ctempp=0; /当前行各元素累加器清零Q.rowtabarow=Q.tu+1;if(arowM.mu) tp=M.rowtabarow+1;else tp=M.tu+1;for(p=M.rowtabarow;ptp;+p) /对当前行中每一个非零元brow=M.datap.col; /找到对应元N中的行号if(browN.nu) t=N.rowtabbrow+1;else t=N.tu+1;for(q=N.rowtabbrow;qt;+q)cco

20、l=N.dataq.col; /乘积元素在Q中列数ctempccol+=M.datap.v*N.dataq.v; /求得Q中第crow(=arow)行的非零元for(ccol=1;ccolmaxsize)return ;Q.dataQ.tu.row=arow; /行数 Q.dataQ.tu.col=ccol; /列数Q.dataQ.tu.v=ctempccol; /累加非零元素值cout乘法结果为:endl;print(Q); /调用print()void main()char choice; rtripletable A,B,Q;cout- n;cout|*欢迎使用稀疏矩阵运算器*| n;c

21、out|=|n;coutn | A、输入矩阵1 | n;coutn | B、输入矩阵2 | n;coutn | C、矩阵相加 | n;coutn | D、矩阵相减 | n;coutn | E、矩阵相乘 | n;coutn | F、退出本系统 | n;coutn|-| n;coutchoice;switch(choice)caseA:creat(A);break;caseB:creat(B);break;caseC:addsmatrix(A,B);break;caseD:subsmatrix(A,B);break;caseE:multsmatrix(A,B,Q);break;caseF:exit(0);cout请选择所需要的操作功能(A，B，C，D，E，F):;while(1);