数据结构课设报告—稀疏矩阵转置和乘法.doc

《数据结构课设报告—稀疏矩阵转置和乘法.doc》由会员分享，可在线阅读，更多相关《数据结构课设报告—稀疏矩阵转置和乘法.doc（11页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、燕山大学课 程 设 计 说 明 书题目：稀疏矩阵的转置和乘法学院（系）： 理学院 年级专业： 12级信息一班、二班 学 号： 2 学生姓名： 吴中原 学 号： 4 学生姓名： 黄志豪 学 号： 0 学生姓名： 李红旭 指导教师：教师职称：燕山大学课程设计（论文）任务书院（系）： 理学院 基层教学单位： 学 号240学生姓名吴中原黄志豪李红旭专业（班级）信息一班信息二班设计题目稀疏矩阵的转置和乘法设计技术参数1、实现稀疏矩阵的压缩存储2、用三元组顺序表表示稀疏矩阵3、实现稀疏矩阵的转置4、建立行逻辑链接顺序表5、实现稀疏矩阵的乘法设计要求1、建立稀疏矩阵的三元组顺序表，实现稀疏矩阵的转置。-建立

2、行逻辑链接顺序表，实现稀疏矩阵乘法。2、要求用到数据结构课本上学到的数组、稀疏矩阵、三元组表的相关知识，要充分清晰的理解这一些基本概念及用法。工作量1、课设的题目与平时上机实验的内容相比有一定的难度，程序更多更复杂。2、使用C+语言编写程序，源程序需加必要的注释。3、三人一组提交一份设计报告书，要求编排格式规范、内容充实。一周之内完 成以上内容，并按小组进行答辩。工作计划1、 复习跟课设题目相关的数据结构知识，进一步查阅资料，完善设计方案2、 编写程序、上机调试与测试 3、 撰写分析报告 4、 制作PPT、进行答辩 参考资料数据结构（C语言版） 严蔚敏 编著 清华大学出版社数据结构习题解 严蔚

3、敏 编著 清华大学出版社课上PPT flash 等指导教师签字基层教学单位主任签字说明：此表一式四份，学生、指导教师、基层教学单位、系部各一份。年 月 日 燕山大学课程设计评审意见表指导教师评语：成绩： 指导教师： 年 月 日答辩小组评语：成绩： 评阅人： 年 月 日课程设计总成绩：答辩小组成员签字：年 月 日一：课设内容建立稀疏矩阵的三元组顺序表，实现稀疏矩阵的转置。-建立行逻辑链接顺序表，实现稀疏矩阵乘法。二：课设步骤小组讨论查阅资料编写代码完成设计报告制作PPT准备答辩三：算法思想转置算法一基本思想：在A的三元组顺序表a.data中依次找第1列、第2列、, 直到最后一列的三元组，并将找到

4、的每个三元组的行、列交换后顺序存储到B的三元组顺序表b.data中。转置算法二基本思想：顺序取，直接存。即在a.data中依次取三元组，交换其行号和列号放到b.data中适当位置。乘法基本思想：修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，指示各行第一个非零元的位置，其值在稀疏矩阵的初始化函数中确定。四：程序代码与结果显示稀疏矩阵转置：#includeusing namespace std; /三元组顺序表的类型定义/#define MAXSIZE 12500 typedef struct int row,col; int item;Triple; typedef struct Tr

5、iple *data;/data0不用 int mu,nu,tu;/分别表示行数、列数和非零元素个数thMatrix; /初始化三元组表/void initMatrix_Th(thMatrix &M) M.data=new TripleMAXSIZE+1; M.mu=0; M.nu=0; M.tu=0;/转置三元组表/一般方法，算法时间复杂度较高void transMatrix_1(thMatrix M,thMatrix &T) initMatrix_Th(T); T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu)int p=1;/用来指M中的元素 int q=

6、1;/用来指T中的元素 int col;/用来遍历列中的元素 for(col=1;col=M.nu;col+)for(p;p=M.tu;p+)if(M.datap.col=col)T.dataq.row=M.datap.col; T.dataq.col=M.datap.row; T.dataq.item=M.datap.item; q+;/改进的方法快速转置/void transMatrix_2(thMatrix M,thMatrix &T)initMatrix_Th(T); T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; int i,j,p,q; int num100; i

7、nt cpot100; if(T.tu)for(i=1;i=M.nu;i+)numi=0;/M中每一列的非零元素个数初始化为0for(i=1;i=M.tu;i+)+numM.datai.col;/M中每一列的非零元素个数存储到一个数组中cpot1=1;for(i=2;i=M.nu;i+)cpoti=cpoti-1+numi-1;/每一列第一个非零元素的位置for(p=1;p=M.tu;p+)j=M.datap.col; q=cpotj;/确定第j列第一个非零元素的位置T.dataq.row=M.datap.col; T.dataq.col=M.datap.row; T.dataq.item=M

8、.datap.item; +cpotj;/指向下一个位置/创建一个三元组表/按行优先存储/int creatMatrix(thMatrix &M)initMatrix_Th(M);int i; cout输入稀疏矩阵的行数、列数以及非零元的个数:M.muM.nuM.tu; if(M.tu=0) cout按行序输入M.tu个非零元素的三元组:endl;for(i=1;i=M.tu;i+)cout输入第i个非零元素的行号、列号和元素值:M.datai.rowM.datai.colM.datai.item;return 0; /输出一个三元组表/void outputMatrix(thMatrix M

9、)int i; coutM.mu M.nu M.tuendl; coutendl; for(i=1;i=M.tu;i+) coutM.datai.row M.datai.col M.datai.itemendl; int main()thMatrix M; thMatrix T;creatMatrix(M);cout原始矩阵M为:endl; outputMatrix(M); transMatrix_2(M,T); cout转置矩阵T为:endl; outputMatrix(T);return 0;稀疏矩阵乘法：#includeusing namespace std; /三元组顺序表的类型定义/

10、#define OK 1#define ERROR 0#define OVERFLOW 0#define MAXSIZE 100 typedef int Status;typedef structint row,col; int e;Triple;#define MAXMN 500 /假设矩阵行数和列数的最大值为500typedef structTriple dataMAXSIZE+1;/非零元三元组表，data0未用 int rposMAXMN + 1;/指示各行第一个非零元的位置 int mu,nu,tu; /矩阵的行数、列数和非零元个数 RLSMatrix; /行逻辑链接顺序表类型Sta

11、tus MultSMatrix(RLSMatrix A,RLSMatrix B,RLSMatrix &C)int ctemp100;int arow,p,brow,t,q,ccol,tp;if(A.nu!=B.mu)return ERROR;C.mu=A.mu;C.nu=B.nu;C.tu=0; if(A.tu*B.tu!=0) /C是非零矩阵for(arow=1;arow=A.mu;+arow)for(int i=0;i=B.nu;i+)ctempi=0; /当前行各元素累加器清零C.rposarow=C.tu+1;if(arowA.mu)tp=A.rposarow+1;elsetp=A.t

12、u+1;for(p=A.rposarow;pA.rposarow+1;+p)/对当前行中每一个非零元brow=A.datap.col; /找到对应元在B中的行号 if(browB.mu)t=B.rposbrow+1;elset=B.tu+1;for(q=B.rposbrow;qt;+q)ccol=B.dataq.col; /乘积元素在C中列号ctempccol+=A.datap.e*B.dataq.e; /for q /for p:求得C中第crow(=arow)行的非零元for(ccol=1;ccolMAXSIZE) return ERROR;elseC.dataC.mu.row=arow;

13、C.dataC.nu.col=ccol;C.dataC.tu.e=ctempccol; return OK;/按行优先存储/int creatRLSMatrix(RLSMatrix &M)int i; cout输入稀疏矩阵的行数、列数以及非零元的个数:M.muM.nuM.tu;if(M.tu!=0) cout按行序输入M.tu个非零元素的三元组:endl;for(i=1;i=M.tu;i+)cout输入第i个非零元素的行号、列号和元素值:M.datai.rowM.datai.colM.datai.e;return 0;/输出一个三元组表/void outputRLSMatrix(RLSMatr

14、ix M)int i; coutM.mu M.nu M.tuendl; coutendl; for(i=1;i=M.tu;i+)coutM.datai.row M.datai.col M.datai.eendl;int main()RLSMatrix A; RLSMatrix B; RLSMatrix C; creatRLSMatrix(A);cout原始矩阵A为:endl; outputRLSMatrix(A); creatRLSMatrix(B);cout原始矩阵B为:endl; outputRLSMatrix(B); MultSMatrix(A,B,C);cout乘积矩阵C为:endl;

15、 outputRLSMatrix(C);return 0;五：成员分工姓名性别任务吴中原男分配任务 编写程序 讲PPT李红旭男 查阅资料 完成报告 协助编写程序黄志豪男 查阅资料 协助编写程序 制作PPT 六：收获体会通过这次课程设计，我们更深层的体会到了数据结构的用处，特别是在现实生活中的用处；更加牢固地掌握了关于数组、三元组以及稀疏矩阵的数据结构知识，并且能够熟练的运用到实际当中；同时，我们也增强了我们三个人彼此的了解，以及之间的熟悉程度、默契程度，我们同心协力，不留余力的一起完成任务。在这次课设中，组员之间互帮互助，像组长吴中原，基础比较好，所以他就担任了绝大部分编程任务并且悉心给组员讲清每一步过程，让其他两个组员都有了深切的认识和了解。当然我们两个用心学习，尽力把这次课设做好。总之，通过这次课程设计，我们对数据结构的有关知识掌握更加的全面和牢固，我相信通过这次课程设计会让我们变得更好，对知识的了解也会进一步加深。