稀疏矩阵存储与运算的综合程序设计.doc

1、 校园导游咨询数据结构课 程 设 计 任 务 书学院名称： 数学与计算机学院 课程代码：_专业： 年级： 一、设计题目 稀疏矩阵存储与运算的综合程序设计二、主要内容本设计属于十字链表的应用。要求使用十字链表结构存储稀疏矩阵的元素，并实现稀疏矩阵的转置、加法及乘法运算。（链表接点数据域含元素行、列标和元素的值）。三、具体要求及提交的材料1做好设计计划，认真查阅相关资料，完成程序设计及调试；2按课程设计说明书_实例模板完成课程设计说明书的撰写；3设计结束后，必须上交如下材料：（1）课程设计说明书（报告）打印稿一份；（2）课程设计说明书及源代码电子文档四、主要技术路线提示认真分析系统功能需求，拟定设

2、计方案和程序框架，查阅相关资料，完成算法设计和程序调试。五、进度安排共计两周时间，建议进度安排如下：1 选题，应该在上机实验之前完成2 需求分析、方案拟定、程序框架思考可分配4学时3 详细的程序设计可分配8学时4 调试和分析可分配8学时。可以有2学时的机动，即提前完成设计任务的学生可提前安排程序验收和答辩六、 推荐参考资料1. 冯博琴 等编著，软件技术基础（修改版），西安交通大学出版社，19972. 严蔚敏 等著，数据结构，清华大学出版社，20033. 李芸芳 等著，软件技术基础（第二版），清华大学出版社，20004. 徐孝凯 等著，数据结构（C语言描述），清华大学出版社，2004指导教师 签

3、名日期 年 月 日系 主 任 审核日期 年 月 日目 录摘要11 引言21.1问题的提出21.2任务与分析22 概要设计32.1功能需求32.1.1总体要求32.1.2各模块要求52.2数据需求63详细设计与实现73.1 总体设计73.2 各模块设计94 调试分析214.1设计测试数据214.2 测试结果及分析21总结24致谢25参考文献26摘 要本课程设计主要实现在十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。程序通过调试，运行，实现了十字链表对于稀疏矩阵的存储、转置、加和乘运算，初步实现了程序的功能。关键词：十字链表，稀疏矩阵，转置，矩阵运算1

4、 引 言 1. 1问题的提出用三元组数组表示稀疏矩阵，一般可以节省存储空间，同时在执行某种矩阵运算时，其执行时间不会增加太多，但是如果在矩阵运算过程中，非零元素的个数有变化，那么必将引起数组中元素的过多移动。为了克服这个缺点，我们想到了另外一种稀疏矩阵的存储方法，十字链表表示稀疏矩阵应运而生。1.2任务与分析本课程设计主要实现在十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用十字链表表示，并在十字链表存储结构下，实现稀疏矩阵的存储与转置并求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C；求两个稀疏矩阵A和B的相乘矩阵E，并输出E

5、。2 概要设计 2. 1功能需求 2.1.1总体要求本设计属于十字链表的应用，要求使用十字链表结构存储稀疏矩阵的元素，并实现稀疏矩阵的转置、加法及乘法运算。使用十字链表存储稀疏矩阵，可以很好的节省空间，并且在计算过程中，若矩阵非零元素有变化，也可以很好的处理，在这种背景之下，要求应用十字链表，完成对稀疏矩阵的存储，转置，并完成各种运算。要完成这些功能，首先需要我们对于数据结构中的十字链表的理解和关于运用十字链表存储稀疏矩阵的优点。学会运用十字链表完成稀疏矩阵的存储，并且在此基础之上完成稀疏矩阵的转置、加法和乘法运算，掌握了这些基本知识，就可以开始着手与此次课程设计的总体设计要求了，下面开始设计

6、程序的总体设计流程。程序总体设计流程图如图2.1所示：开始输入矩阵A Y N输出矩阵A的转置矩阵输入矩阵B Y N输出矩阵B的转置矩阵A和B能相加？ Y N 输出矩阵C=A+B矩阵A和B不能相加A和B能相乘？ Y N矩阵A和B不能相乘输出矩阵E=A*B结束 图2.1程序流程图2.1很好的反映了此次程序的设计思路，对于稀疏矩阵，若能完成加法和乘法运算，则打印出两个稀疏矩阵的和和乘积，如果不能完成加法或者乘法运算，则打印相应的信息反馈给用户。2.1.2各模块要求 1）初始函数建立稀疏矩阵及初始化稀疏矩阵本模块要求设计函数在十字链表结构下建立稀疏矩阵并初始化。首先要定义十字链表结构体类型，在输入出现

7、错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值，特别需要注意在十字链表存储稀疏矩阵的时候，要对变量进行动态的地址分配。2）转置函数进行稀疏矩阵的转置本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果，由于对稀疏函数的转置只对一个矩阵进行操作，所以实现起来难度不是很大，函数也比较容易编写。在编写函数时，要先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。3）和运算函数进行两个稀疏矩阵相加运算本模块要求设计加法对两个矩阵进行运算，并输出最终运算后的稀疏矩阵，在进行运算前，要对两个矩阵进行检查，看是不是相同类型的矩阵，因为两个矩阵相加要求两个矩阵一定是同一类型的矩阵，定义

8、相应的矩阵类型用于存放两个矩阵相加后的结果矩阵，这个结果矩阵的行数列数需要综合多方面情况来确定。4）积运算函数进行两个稀疏矩阵的乘法运算本模块要求设计乘法对两个矩阵进行运算，并输出最终运算后的稀疏矩阵，在进行运算前，要对两个矩阵进行检查，如果A矩阵的行（列）和B矩阵的列（行）数值相等，则能完成相应的乘法运算，定义相应的矩阵类型用于存放两个稀疏矩阵相乘之后的结果矩阵，并且调用输出函数完成乘积的输出。5）输出函数完成矩阵的输出本模块要求完成对稀疏矩阵的输出功能，实现起来比较简单，完成矩阵的转置输出，矩阵的加法和乘法运算输出相应的和和积，都要调用输出函数。2.2数据需求我们用一个结点表示稀疏矩阵的一

9、个非零元素，在结点中，用row，col和val字段分别存放非零元素的行号、列号和元素的值；用指针right指向表示同一行中下一个非零元素的结点，用指针down指向表示同一列中一下个非零元素的结点，于是，我们用图2.2表示稀疏矩阵非零元素的结点和结构。valcolrowdownright 图2.2十字链表结构体的定义：typedef int Status;/- 稀疏矩阵的十字链表存储表示 -typedef struct OLNode int i,j; /该非零元的行和列下标 int e; /存储矩阵的数据元素 struct OLNode *right, *down; /该非零元所在行表和列表的后

10、继链域 OLNode, *OLink;typedef struct OLink *rhead, *chead; /行和列链表头指针向量基址由CreateSMatrix分配 int mu, nu, tu; /稀疏矩阵的行数、列数和非零元个数 CrossList;3 详细设计与实现3.1总体设计在主函数中调用初始函数完成对稀疏矩阵的初始化，调用转置函数，完成矩阵的转置，然后调用输出函数输出矩阵。调用和运算函数完成两个矩阵的相加，调用积运算函数完成两个矩阵的乘积。主函数调用关系图如下图3.1所示：主函数输出函数积运算函数和运算函数转置函数初始化函数 图3.1 主函数主要代码如下所示：void mai

11、n() CrossList A, B, C;/稀疏矩阵A、B和C均以三元组表作为存储结构，C存放A、B相加相乘的结果 /创建稀疏矩阵A、B cout << "请输入稀疏矩阵A" << endl; CreateSMatrix_OL(A); cout << "稀疏矩阵A为：" << endl; PrintSMatrix_OL(A);PrintSMatrix_temp(A); cout << endl; cout << "请输入稀疏矩阵B" << endl;

12、 CreateSMatrix_OL(B); cout << "稀疏矩阵B为：" << endl; PrintSMatrix_OL(B);PrintSMatrix_temp(B); cout << endl; /求稀疏矩阵的和C = A + B，并输出相加结果矩阵C if(AddSMatrix_OL(A, B, C) cout << "求疏矩阵的和C = A + B，并输出相加结果矩阵C：" << endl; PrintSMatrix_OL(C); cout << endl; /求稀疏

13、矩阵乘积C = A ×B，并输出相乘结果矩阵C if(MultSMatrix_OL(A, B, C) cout << "稀疏矩阵乘积C = A ×B，并输出相乘结果矩阵C：" << endl; PrintSMatrix_OL(C); cout << endl; cout << endl; /销毁稀疏矩阵A、B和C DestroySMatrix_OL(A); DestroySMatrix_OL(B); DestroySMatrix_OL(C); /程序结束 system("pause");

14、 main(); 3.2各模块设计1）初始化函数的详细设计：Status CreateSMatrix_OL(CrossList &M) int m, n, t, e; /行数m，列数n，非零元个数t和非零元值e int i, j, k; /中间变量 OLink p, q; /中间变量 int flag MAXSIZEMAXSIZE; /标记数组：此位置是否已经有非零元素 for(i = 0; i < MAXSIZE; i+) /标记数组的初始化 for(j = 0; j < MAXSIZE; j+) flag ij = 0; /输入M的行数、列数和非零元个数 do cout

15、 << "请分别输入矩阵的行数、列数和非零元个数：" << endl; cout << "行数：" cin >> m; cout << "列数：" cin >> n; cout << "非零元的个数：" cin >> t; if(m <= 0 | n <= 0 | t < 0 | t > m*n) cout << "输入的数据不符合要求！" << end

16、l; while(m <= 0 | n <= 0 | t < 0 | t > m*n); M.mu = m, M.nu = n, M.tu = t;/保存 /分配行和列链表头指针向量基址 if(!(M.rhead = (OLink *)malloc(m + 1) * sizeof(OLink) exit(OVERFLOW); if(!(M.chead = (OLink *)malloc(n + 1) * sizeof(OLink) exit(OVERFLOW); /初始化行列头指针向量，各行列链表为空链表 for(i = 0; i <= m; i+) M.rhea

17、di = NULL; for(i = 0; i <= n; i+) M.cheadi = NULL; /按任意次序输入非零元 if(t = 0) return OK; if(t < 0) return ERROR; for(k = 0; k < t; k+) do cout << "请输入第" << k+1 << "个非零元(总共" << t << "个)的行和列：" << endl; cout << "对应行："

18、 cin >> i; cout << "对应列：" cin >> j; if(i <= 0 | i > m | j <= 0 | j > n) cout << "输入行或列不符合要求！" << endl; if(flag ij != 0) cout << "此处已存在非零元素！" << endl; flag ij = 2; else flag ij = 1; while(i <= 0 | i > m | j <

19、= 0 | j > n | flag ij = 2);/检测输入是否合法 do cout << "非零元：" cin >> e; if(e = 0) cout << "输入为0，请重新输入！" << endl; while(e = 0); /检测输入是否合法 if(!(p = (OLNode *)malloc(sizeof(OLNode) exit(OVERFLOW); /生成结点 p->i = i, p->j = j, p->e = e, p->right = NULL, p

20、->down = NULL; /进行行插入 if(M.rheadi = NULL | M.rheadi->j > j) p->right = M.rheadi; M.rheadi = p; else /巡查在行表中的插入位置 for(q = M.rheadi; (q->right) && q->right->j < j; q = q->right); p->right = q->right, q->right = p; /完成行插入 /进行列插入 if(M.cheadj = NULL | M.cheadj-

21、>i > i) p->down = M.cheadj; M.cheadj = p; else /巡查在列表中的插入位置 for(q = M.cheadj; (q->down) && q->down->i < i; q = q->down); p->down = q->down, q->down = p; /完成列插入 return OK; 2)转置函数的详细设计：Status PrintSMatrix_temp(CrossList M) int i, j;/中间变量 OLink p; /中间变量 int arr1

22、010 =0; /输出 for(i = 1; i <= M.mu; i+) p = M.rheadi; for(j = 1; j <= M.nu; j+) if(p && p->j = j) arrji = p->e; p = p->right; cout << endl; cout<<"此矩阵的转置矩阵为"<<endl; for(j = 1;j<= M.nu; j+) for(i = 1;i<= M.mu;i+) cout<<arrji<<"t&

23、quot;if(i=M.mu)cout<<endl; return OK;3）和运算函数的详细设计：Status AddSMatrix_OL(CrossList M, CrossList N, CrossList &Q) int i; /中间变量 OLink *col; /指向列的最后结点的数组 OLink pm, pn, p, pl;/pm记录M的第i行第一个结点，pn记录N的第i行第一个结点 /检查稀疏矩阵M和N的行数和列数是否对应相等 if(M.mu != N.mu | M.nu != N.nu) /不完全相等，退出 cout << "两个矩阵行

24、列数不完全相等，不是同类矩阵，不能相加。" << endl; return ERROR; /初始化矩阵Q Q.mu = M.mu, Q.nu = M.nu, Q.tu = 0; if(!(Q.rhead = (OLink *)malloc(Q.mu + 1) * sizeof(OLink) exit(OVERFLOW); if(!(Q.chead = (OLink *)malloc(Q.nu + 1) * sizeof(OLink) exit(OVERFLOW); for(i = 0; i <= Q.mu; i+) Q.rheadi = NULL; for(i =

25、0; i <= Q.nu; i+) Q.cheadi = NULL; /执行矩阵相加 if(!(col = (OLink *)malloc(Q.nu + 1) * sizeof(OLink) exit(OVERFLOW); for(i = 0; i <= Q.nu; i+) coli = NULL; /按行的顺序相加，分为四种情况 for(i = 1; i <= Q.mu; i+) /分别记录M、N的第i行第一个结点 pm = M.rheadi, pn = N.rheadi; while(pm && pn)/pm和pn均不为空 if(pm->j <

26、 pn->j)/矩阵M当前结点的列小于矩阵N当前结点的列 if(!(p = (OLink)malloc(sizeof(OLNode) exit(OVERFLOW); Q.tu+;/非零元素增加 p->i = i, p->j = pm->j, p->e = pm->e, p->right = NULL, p->down = NULL, pm = pm->right;/赋值，指针右移 else if(pm->j > pn->j)/矩阵M当前结点的列大于矩阵N当前结点的列 if(!(p = (OLink)malloc(sizeo

27、f(OLNode) exit(OVERFLOW); Q.tu+;/非零元素增加 p->i = i, p->j = pn->j, p->e = pn->e, p->right = NULL, p->down = NULL, pn = pn->right;/赋值，指针右移 else if(pm->e + pn->e)/矩阵M、N当前结点的列相等且两元素之和不为0 if(!(p = (OLink)malloc(sizeof(OLNode) exit(OVERFLOW); Q.tu+;/非零元素增加 p->i = i, p->j

28、= pn->j, p->e = pm->e + pn->e, p->right = NULL, p->down = NULL, pm = pm->right, pn = pn->right;/赋值，指针右移 else /矩阵M、N当前结点的列相等且两元素之和为0 pm = pm->right, pn = pn->right;/指针向右移 continue; /将p插入十字链表 /行插入 if(Q.rheadi = NULL) /若p为该行的第1个结点 Q.rheadi = pl = p; /p插在该行的表头且pl指向p(该行的最后一个

29、结点) else pl->right = p, pl = p; /插在pl所指结点之后，pl右移 /列插入 if(Q.cheadp->j = NULL) /若p为该列的第一个结点 Q.cheadp->j = colp->j = p; /p插在该列的表头且colp->j指向p else colp->j->down = p, colp->j=p; /插在colp->j所指结点之后，colp->j下移 /将矩阵M第i行的剩余元素插入矩阵Q while(pm) if(!(p = (OLink)malloc(sizeof(OLNode) exi

30、t(OVERFLOW); Q.tu+;/非零元素增加 p->i = i, p->j = pm->j, p->e = pm->e, p->right = NULL, p->down = NULL, pm = pm->right;/赋值，指针右移 /将p插入十字链表 /行插入 if(Q.rheadi = NULL) /若p为该行的第1个结点 Q.rheadi = pl = p; /p插在该行的表头且pl指向p(该行的最后一个结点) else pl->right = p, pl = p; /插在pl所指结点之后，pl右移 /列插入 if(Q.ch

31、eadp->j = NULL) /若p为该列的第一个结点 Q.cheadp->j = colp->j = p; /p插在该列的表头且colp->j指向p else colp->j->down = p, colp->j=p; /插在colp->j所指结点之后，colp->j下移 while(pn) if(!(p = (OLink)malloc(sizeof(OLNode) exit(OVERFLOW); Q.tu+;/非零元素增加 p->i = i, p->j = pn->j, p->e = pn->e, p-&

32、gt;right = NULL, p->down = NULL, pn = pn->right;/赋值，指针右移 /将p插入十字链表 /行插入 if(Q.rheadi = NULL) /若p为该行的第1个结点 Q.rheadi = pl = p; /p插在该行的表头且pl指向p(该行的最后一个结点) else pl->right = p, pl = p; /插在pl所指结点之后，pl右移 /列插入 if(Q.cheadp->j = NULL) /若p为该列的第一个结点 Q.cheadp->j = colp->j = p; /p插在该列的表头且colp->

33、;j指向p else colp->j->down = p, colp->j=p; /插在colp->j所指结点之后，colp->j下移 for(i = 0; i <= Q.nu; i+) if(coli) coli->down = NULL; /第i列有结点，令其最后一个结点的down指针为空 free(col); return OK;4）积运算函数详细设计：Status MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q) int i, j, e; /中间变量 OLink p0, q0,

34、 p, pl, pla; /中间变量 /检查稀疏矩阵M的列数和N的行数是否对应相等 if(M.nu != N.mu) /稀疏矩阵M的列数和N的行数不相等，不能相乘，退出 cout << "稀疏矩阵A的列数和B的行数不相等，不能相乘。" << endl; return ERROR; /初始化矩阵Q Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0; if(!(Q.rhead = (OLink *)malloc(Q.mu + 1) * sizeof(OLink) exit(OVERFLOW); if(!(Q.chead = (OLin

35、k *)malloc(Q.nu + 1) * sizeof(OLink) exit(OVERFLOW); for(i = 0; i <= Q.mu; i+) Q.rheadi = NULL; for(i = 0; i <= Q.nu; i+) Q.cheadi = NULL; /相乘 for(i =1; i <= Q.mu; i+) for(j = 1; j <= Q.nu; j+) p0 = M.rheadi, q0 = N.cheadj, e = 0; while(p0&&q0)/M第i行和N第j列有元素 if( p0->j > q0-&

36、gt;i) q0 = q0->down; /M的列大于N的行，则N的列指针后移 else if(p0->j < q0->i) p0 = p0->right;/M的列小于N的行，则M的行指针右移 else /M的行等于N的列 e += p0->e * q0->e; /乘积累加 q0 = q0->down, p0 = p0->right;/移动指针 if(e)/乘积不为0 if(!(p = (OLink)malloc(sizeof(OLNode) exit(OVERFLOW); Q.tu+;/非零元素增加 p->i = i, p->

37、j = j, p->e = e, p->right = NULL, p->down = NULL;/赋值，指针后移 /将p插入十字链表 /行插入 if(Q.rheadi = NULL) /若p为该行的第1个结点 Q.rheadi = pl = p; /p插在该行的表头且pl指向p(该行的最后一个结点) else pl->right = p, pl = p; /插在pl所指结点之后，pl右移 /列插入 if(Q.cheadj = NULL) /若p为该列的第一个结点 Q.cheadj = p; /该列的表头指向p else /插在列表尾 pla = Q.cheadj;/p

38、la指向j行的第1个结点 while(pla->down) pla = pla->down;/pla指向j行最后一个结点 pla->down = p; return OK;5）输出函数详细设计：Status PrintSMatrix_OL(CrossList M) int i, j;/中间变量 OLink p; /中间变量 / int arr1010 =0; /输出 for(i = 1; i <= M.mu; i+) p = M.rheadi; for(j = 1; j <= M.nu; j+) if(p && p->j = j) cout

39、<< p->e << "t" ;/ arrji = p->e; p = p->right; else cout << "0t" cout << endl; cout << "矩阵共有" << M.mu << "行" << M.nu << "列" << M.tu << "个非零元素" << endl;/* for(j

40、= 1;j<= M.nu; j+) for(i = 1;i<= M.mu;i+) cout<<arrji<<"t"if(i=M.mu)cout<<endl; */ return OK;4 调试分析4.1测试数据 此次测试用例，我随便选取了一组测试数据用于程序的测试，按照程序的说明依次输入矩阵A和矩阵B，程序会输出矩阵A和矩阵B的转置矩阵，若矩阵A和矩阵B能相加，则输出它们的和，若矩阵A和矩阵B能相乘，则输出它们的积。如若不能，则打印相关信息。输入矩阵A为 2 0 0 输入矩阵B为 0 0 3 0 0 5 4 0 0 0 3 0

41、 0 0 04.2测试结果及分析输入矩阵A如图4.1所示： 图4.1输入稀疏矩阵B如图4.2所示：图4.2矩阵A的转置矩阵如图4.3所示：图4.3矩阵B的转置矩阵如图4.4所示：图4.4矩阵A和B的和如图4.5所示： 图4.5矩阵A和B的积如图4.6所示： 图4.6根据程序测试结果，和我们计算获得的结果进行比较，我们发现了程序测试结果和计算结果完全一样。但仅仅从这一方面，还不能得出程序获得了成功，如果输入的稀疏矩阵A和矩阵B不能相加或者相乘呢？针对这个问题，我也使用了另外一组测试用例，也获得了相关结果，这也进一步程序运行的正确性。当然也从另外一个方面说明了使用十字链表这一数据结构对于稀疏矩阵存储和运算的简洁性，十字链表这一数据结构用于稀疏矩阵的存储不仅节省了系统的内存空间，对于矩阵的运算也方便快捷。总结本程序要求使用十字链表这种数据结构完成对稀疏矩阵的存储和运算，对于稀疏矩阵这种数据结构需要相当好的掌握，不仅仅是这种数据结