1、数据结构 课程设计设计性综合性实验实验课题名称: 稀疏矩阵运算器 院系：计算机科学与技术学院 专业：计算机科学与技术 课程： 数据结构 教师: 学号: 姓名: 学号: 姓名: 学号: 姓名: 学号: 姓名: 学号: 姓名: 2010 至 2011 学年度 上 学期实验名称：稀疏矩阵运算器实验性质：设计性实验器材：PC机并装有VC+6.0环境实验目的：深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性实验任务：实现一个能进行稀疏矩阵基本运算的运算器，要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。输入以三元组表示，输出以通常的阵列形式列出。实验内
2、容、过程及结果：一 问题描述稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行储存和计算可以大大节省储存空间，提高计算效率。实现能进行称稀疏矩阵基本运算的运算器。基本要求：以带逻辑链接信息的三元组顺序表表示稀疏矩阵，实现矩阵相加，相减，相乘的运算。稀疏矩阵的输入形式采用三元组表示。而运算结果的矩阵则用通常的阵列形式列出。测试数据：+ = + = * = 二 设计思路A. 行逻辑链接的顺序表 为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中B. 数据结构的选用 为了实现稀疏矩阵的各种运算，采用
3、三元组的方式储存矩阵 C. 矩阵的各种运算 为了求2和矩阵的各类运算，只需要在相乘2个矩阵中相对应的各个元素的j值和i值相运算即可三 解决问题【主程序模块】：void main() 初始化;do 接受命令; 处理命令;while(命令!=“退出”)；【功能模块调用关系图】主程序模块 创建稀疏矩阵模块 运算稀疏矩阵模块 打印稀疏矩阵模块 【详细设计】稀疏矩阵运算器 矩阵相乘 矩阵相加矩阵相减 退出本系统 输入矩阵1输入矩阵1输入矩阵1输入矩阵2输入矩阵2输入矩阵2计算结果计算结果计算结果 typedef structint row; /行数int col; /列数int v; /非零元素值tri
4、plenode;typedef structtriplenode datamaxsize+1; /非零元三元组int rowtabmaxrow+1; /各行第一个非零元的位置表int mu,nu,tu; /矩阵的行数、列数和非零元个数rtripletable;void creat(rtripletable &A) /创建稀疏矩阵void print(rtripletable A) /输出稀疏矩阵int addsmatrix(rtripletable M, rtripletable N) /矩阵相加int subsmatrix(rtripletable M, rtripletable N) /稀
5、疏矩阵相减void multsmatrix(rtripletable M, rtripletable N, rtripletable &Q) /稀疏矩阵相乘四实现1 功能函数设计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); /初始化条件: 稀疏矩阵M存在./操作结果:输出稀疏矩阵M.AddSMatrix(M,N,&Q)
6、;/初始化条件: 稀疏矩阵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 【源程序】 #include#include#include#define maxsize 100#define maxrow 100#define OK 1#define ERROR -1typedef struct int ro
7、w; /行数 int col; /列数 int v; /非零元素值triplenode;typedef struct triplenode 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; co
8、ut请以空格隔开的形式输入非零元的行、列、值.endl; for(loop=1;loopA.dataloop.rowA.dataloop.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) /
9、输出稀疏矩阵 int resultmaxrow+1maxrow+1; int loop1,loop2; for(loop1=1;loop1=A.mu;loop1+) for(loop2=1;loop2=A.nu;loop2+) resultloop1loop2=0; /初始化为0 for(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+) coutres
10、ultloop1loop2; /输出所做运算的结果 cout|endl; int addsmatrix(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=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
11、.datap.v+N.dataq.v!=0) /两个稀疏矩阵相加的结果不为0 Q.datak.row=M.datap.row; Q.datak.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.
12、row) /第一个稀疏矩阵行列数小于第二个稀疏矩阵行数 Q.datak=M.datap;+p;+k; else /第一个稀疏矩阵行列数小于第二个稀疏矩阵行数 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
13、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) /两个稀疏矩阵相减的结果不为0 Q.datak.row=M.datap.row; Q.datak.col=M
14、.datap.col; Q.datak.v=M.datap.v-N.dataq.v; +k; +q;+p; if(M.datap.colN.dataq.col) /第一个稀疏矩阵列数大于第二个稀疏矩阵的列 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
15、.v;+q;+k; while(p=M.tu) /只有M并且符合条件 Q.datak=M.datap;+p;+k; while(q=N.tu) /只有N并且符合条件 Q.datak.row=N.dataq.row; Q.datak.col=N.dataq.col; Q.datak.v=-N.dataq.v; +q;+k; Q.tu=k-1; cout减法结果为:endl; print(Q); /调用print() return OK; void multsmatrix(rtripletable M, rtripletable N, rtripletable &Q) /稀疏矩阵相乘 int ar
16、ow,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) /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
17、(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) ccol=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;
18、 /列数 Q.dataQ.tu.v=ctempccol; /累加非零元素值 cout乘法结果为:endl; print(Q); /调用print() void main() char choice; rtripletable A,B,Q; cout- n; cout|*欢迎使用稀疏矩阵运算器*| n; cout|=|n; coutn | A、输入矩阵1 | n; coutn | B、输入矩阵2 | n; coutn | C、矩阵相加 | n; coutn | D、矩阵相减 | n; coutn | E、矩阵相乘 | n; coutn | F、退出本系统 | n; coutn|-| n; cou
19、tchoice; 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);运行与测试实验总结：调试程序时，应注意矩阵的调用。比如，开始时没有注意将程序调用！尽管实现了矩阵的转置和相加，但没有符合题意。在调试时，才意识到是以前经常发的一个错误，就是在最后加了一个return 0，这是错误的！在编写程序时体会到了团队合作的精神，这是将来走进社会不可缺少的！实验成绩学 号 姓 名课题小组自评分数最后得分093821029093821033093821034093821036
