2022年数据结构——稀疏矩阵运算器可用 .pdf

数据结构课程设计报告设计题目：稀疏矩阵运算器年级班级姓名学号指导教师起止时间2010 年二学期名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 15 页 -一、实验目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。二、问题描述（具体任务）设计、实现两个稀疏矩阵在十字链表表示方法下的相加、相减、相乘。稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行储存和计算可以大大节省储存空间，提高计算效率。实现一个能进行称稀疏矩阵基本运算的运算器。三、需求分析该程序所做的工作的是稀疏矩阵运算器，实现两个稀疏矩阵的基本运算。此程序规定：1、按照压缩存储的概念，只存储稀疏矩阵的非零元，以两个三元组 i,j,e 来表示矩阵的非零元的行，列和数值，就确定了一个非零元由此，稀疏矩阵可由表示非零元的三元数组及行列数确定2、用户输入数据作为三元组的行，列和非零元的个数，用空格隔开并输入非零元的行，列和数值3、本程序只对两个矩阵进行四则运算，所的结果矩阵应该另生成，用十字链表存放，并放入新的矩阵中，只要对矩阵求解就能求出答案四、算法设计思想及流程图用十字链表存储方式实现稀疏矩阵的基本运算，此程序用到以下函数：void CreateSMatrix(CrossList&R)/创建储存稀疏矩阵void PrintSMatrix(CrossList R)/输出十字链表的函数void MultSMatrix(CrossList M,CrossList N,CrossList&Q)/实现矩阵乘法int AddMatrix(CrossList M,CrossList N,CrossList&Q)/实现矩阵加法int SubtSMatrix(CrossList M,CrossList N,CrossList&Q)/实现矩阵减法void main()/主函数调用以上函数来实现其功能：首先调用CreateSMatrix()创建矩阵M和 N，并输入稀疏矩阵的行数，列数，非零元素个数，通过 PrintSMatrix()输出矩阵M和 N，根据提示选择相应的运算，当进行加或减运算时，如果两个矩阵的行和列不相等时，就无法得到结果，并出现提示错误信息，当进行乘法运算时，要求矩阵M的列数必须等于矩阵N的行数，否则无法进行乘法运算，为了进行多种运算通过主函数的Do-While循环来实现，退出循环条件是输入”+”、”-”、”*”以外的任意字符即可退出循环。五、C语言源代码#include#include#define OVERFLOW-1#define OK 1#define NULL 0/建立十字链表typedef struct OLNode int row,col;/该非零元的行和列下标 int e;struct OLNode*right,*down;/该非零元所在行表和列表的后继链域OLNode,*OLink;typedef struct OLink*rhead,*chead;/行和列链表头指针向量基址由CreateSMatrix分配 int mu,nu,tu;/系数矩阵的行数，列数和非零元个数CrossList;/创建储存稀疏矩阵名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 15 页 -void CreateSMatrix(CrossList&R)int m,n,t,i,j,k,a;OLink p,q;if(R.rhead)R.rhead=NULL;R.chead=NULL;R.mu=0;R.nu=0;R.tu=0;printf(n请输入稀疏矩阵的行数列数非零元个数:);scanf(%d%d%d,&m,&n,&t);R.mu=m;R.nu=n;R.tu=t;if(!(R.rhead=(OLink*)malloc(m+1)*sizeof(OLink)exit(OVERFLOW);if(!(R.chead=(OLink*)malloc(n+1)*sizeof(OLink)exit(OVERFLOW);for(i=1;i=R.mu+1;i+)R.rheadi=NULL;for(i=1;i=R.nu+1;i+)R.cheadi=NULL;for(k=1;krow=i;p-col=j;p-e=a;if(R.rheadi=NULL|R.rheadi-colj)p-right=R.rheadi;R.rheadi=p;else for(q=R.rheadi;(q-right)&q-right-colright);p-right=q-right;q-right=p;if(R.cheadj=NULL|R.cheadj-rowi)p-down=R.cheadj;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 15 页 -R.cheadj=p;else for(q=R.cheadj;(q-down)&q-down-rowdown);p-down=q-down;q-down=p;/输出十字链表的函数void PrintSMatrix(CrossList R)int i,j;int b=0;OLink p;for(i=1;i=R.mu;i+)p=R.rheadi;printf(tttt|);for(j=1;jcol)printf(%4d,p-e);p=p-right;else printf(%4d,b);else printf(%4d,b);printf(|n);/实现矩阵乘法void MultSMatrix(CrossList M,CrossList N,CrossList&Q)int i,j,temp=0;OLink q,pm,pn,pq;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.nu!=N.mu)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 15 页 -printf(这两个矩阵不能相乘!);exit(OVERFLOW);/矩阵相乘条件，矩阵1 的行数必须等于矩阵2 的列数if(M.tu*N.tu!=0)for(i=1;i=M.mu;i+)for(j=1;jcolpn-row)if(pn-down!=NULL)pn=pn-down;else pn=NULL;if(pm&pn&pm-col=pn-row)temp+=(pm-e)*(pn-e);if(pm-right!=NULL)pm=pm-right;else pm=NULL;if(pn-down!=NULL)pn=pn-down;else pn=NULL;else if(pm-right!=NULL)pm=pm-right;else pm=NULL;/while(pm)if(temp)if(!(pq=(OLNode*)malloc(sizeof(OLNode)exit(OVERFLOW);pq-row=i;pq-col=j;pq-e=temp;if(Q.rheadi=NULL|Q.rheadi-colj)pq-right=Q.rheadi;Q.rheadi=pq;else for(q=Q.rheadi;(q-right)&q-colright);pq-right=q-right;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 15 页 -q-right=pq;if(Q.cheadj=NULL|Q.cheadj-rowi)pq-down=Q.cheadj;Q.cheadj=pq;else for(q=Q.cheadj;(q-down)&q-rowdown);pq-down=q-down;q-down=pq;(Q.tu)+;/if temp /for j /for i /for if/MultSMatrix()/实现矩阵加法int AddMatrix(CrossList M,CrossList N,CrossList&Q)/*初始条件:稀疏矩阵 M与 N的行数和列数对应相等。*/*操作结果:求稀疏矩阵的差Q=M+N*/int i,k;OLink p,pq,pm,pn;OLink*col;if(M.mu!=N.mu|M.nu!=N.nu)printf(两个矩阵不是同类型的,不能相加 n);exit(OVERFLOW);Q.mu=M.mu;/*初始化 Q矩阵 */Q.nu=M.nu;Q.tu=0;/*元素个数的初值*/Q.rhead=(OLink*)malloc(Q.mu+1)*sizeof(OLink);if(!Q.rhead)exit(OVERFLOW);Q.chead=(OLink*)malloc(Q.nu+1)*sizeof(OLink);if(!Q.chead)exit(OVERFLOW);for(k=1;k=Q.mu;k+)/*初始化 Q的行头指针向量;各行链表为空链表*/Q.rheadk=NULL;for(k=1;k=Q.nu;k+)/*初始化Q 的列头指针向量;各列链表为空链表*/Q.cheadk=NULL;col=(OLink*)malloc(Q.nu+1)*sizeof(OLink);/*生成指向列的最后结点的数组*/if(!col)exit(OVERFLOW);for(k=1;k=Q.nu;k+)/*赋初值 */colk=NULL;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 15 页 -for(i=1;icolcol)/*矩阵 M当前结点的列小于矩阵N 当前结点的列*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/p-row=i;p-col=pm-col;p-e=+pm-e;p-right=NULL;pm=pm-right;/*pm指针向右移 */else if(pm-colpn-col)/*矩阵 M当前结点的列大于矩阵N当前结点的列*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/p-row=i;p-col=pn-col;p-e=+pn-e;p-right=NULL;pn=pn-right;/*pn指针向右移 */else if(pm-e+pn-e)p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-row=i;p-col=pn-col;p-e=pm-e+pn-e;p-right=NULL;pm=pm-right;pn=pn-right;else /*矩阵 M、N当前结点的列相等且两元素之差为0*/pm=pm-right;/*pm指针向右移 */pn=pn-right;/*pn指针向右移 */continue;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 15 页 -if(Q.rheadi=NULL)/*p为该行的第1 个结点 */Q.rheadi=pq=p;/*p 插在该行的表头且pq 指向 p(该行的最后一个结点)*/else /*插在 pq 所指结点之后 */pq-right=p;/*完成行插入 */pq=pq-right;/*pq指向该行的最后一个结点*/if(Q.cheadp-col=NULL)/*p为该列的第1 个结点 */Q.cheadp-col=colp-col=p;/*p插在该列的表头且colp-j指向p*/else /*插在 colp-所指结点之后*/colp-col-down=p;/*完成列插入 */colp-col=colp-col-down;/*colp-j指向该列的最后一个结点*/while(pm)/*将矩阵 M该行的剩余元素插入矩阵Q*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/p-row=i;/*给结点赋值 */p-col=pm-col;p-e=pm-e;p-right=NULL;pm=pm-right;/*pm指针向右移 */if(Q.rheadi=NULL)/*p为该行的第1 个结点 */Q.rheadi=pq=p;/*p 插在该行的表头且pq 指向 p(该行的最后一个结点)*/else /*插在 pq 所指结点之后 */pq-right=p;/*完成行插入 */pq=pq-right;/*pq指向该行的最后一个结点*/if(Q.cheadp-col=NULL)/*p为该列的第1 个结点 */Q.cheadp-col=colp-col=p;/*p插在该列的表头且colp-j指向 p*/else /*插在 colp-j所指结点之后*/colp-col-down=p;/*完成列插入 */colp-col=colp-col-down;/*colp-j指向该列的最后一个结点*/while(pn)/*将矩阵 N该行的剩余元素插入矩阵Q*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 15 页 -p-row=i;/*给结点赋值 */p-col=pn-col;p-e=+pn-e;p-right=NULL;pn=pn-right;/*pm指针向右移 */if(Q.rheadi=NULL)/*p为该行的第1 个结点 */Q.rheadi=pq=p;/*p插在该行的表头且pq 指向 p(该行的最后一个结点)*/else /*插在 pq 所指结点之后*/pq-right=p;/*完成行插入 */pq=pq-right;/*pq指向该行的最后一个结点*/if(Q.cheadp-col=NULL)/*p为该列的第1 个结点 */Q.cheadp-col=colp-col=p;/*p插在该列的表头且colp-j指向p*/else /*插在 colp-j所指结点之后 */colp-col-down=p;/*完成列插入 */colp-col=colp-col-down;/*colp-j指向该列的最后一个结点*/for(k=1;kdown=NULL;/*令该列最后一个结点的down 指针为空 */free(col);return OK;/实现矩阵减法int SubtSMatrix(CrossList M,CrossList N,CrossList&Q)/*初始条件:稀疏矩阵 M与 N的行数和列数对应相等。*/*操作结果:求稀疏矩阵的差Q=M-N*/int i,k;OLink p,pq,pm,pn;OLink*col;if(M.mu!=N.mu|M.nu!=N.nu)printf(两个矩阵不是同类型的,不能相减 n);exit(OVERFLOW);Q.mu=M.mu;/*初始化 Q矩阵 */Q.nu=M.nu;Q.tu=0;/*元素个数的初值*/Q.rhead=(OLink*)malloc(Q.mu+1)*sizeof(OLink);if(!Q.rhead)exit(OVERFLOW);Q.chead=(OLink*)malloc(Q.nu+1)*sizeof(OLink);if(!Q.chead)exit(OVERFLOW);for(k=1;k=Q.mu;k+)/*初始化 Q的行头指针向量;各行链表为空链表*/名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 15 页 -Q.rheadk=NULL;for(k=1;k=Q.nu;k+)/*初始化Q 的列头指针向量;各列链表为空链表*/Q.cheadk=NULL;col=(OLink*)malloc(Q.nu+1)*sizeof(OLink);/*生成指向列的最后结点的数组*/if(!col)exit(OVERFLOW);for(k=1;k=Q.nu;k+)/*赋初值 */colk=NULL;for(i=1;icolcol)/*矩阵 M当前结点的列小于矩阵N 当前结点的列*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/p-row=i;/*给结点赋值 */p-col=pm-col;p-e=pm-e;p-right=NULL;pm=pm-right;/*pm指针向右移 */else if(pm-colpn-col)/*矩阵 M当前结点的列大于矩阵N当前结点的列*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/p-row=i;/*给结点赋值 */p-col=pn-col;p-e=-pn-e;p-right=NULL;pn=pn-right;/*pn指针向右移 */else if(pm-e-pn-e)/*矩阵 M、N当前结点的列相等且两元素之差不为0*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/p-row=i;/*给结点赋值 */p-col=pn-col;p-e=pm-e-pn-e;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 15 页 -p-right=NULL;pm=pm-right;/*pm指针向右移 */pn=pn-right;/*pn指针向右移 */else /*矩阵 M、N当前结点的列相等且两元素之差为0*/pm=pm-right;/*pm指针向右移 */pn=pn-right;/*pn指针向右移 */continue;if(Q.rheadi=NULL)/*p为该行的第1 个结点 */Q.rheadi=pq=p;/*p 插在该行的表头且pq 指向 p(该行的最后一个结点)*/else /*插在 pq 所指结点之后 */pq-right=p;/*完成行插入 */pq=pq-right;/*pq指向该行的最后一个结点*/if(Q.cheadp-col=NULL)/*p为该列的第1 个结点 */Q.cheadp-col=colp-col=p;/*p插在该列的表头且colp-j指向p*/else /*插在 colp-所指结点之后*/colp-col-down=p;/*完成列插入 */colp-col=colp-col-down;/*colp-j指向该列的最后一个结点*/while(pm)/*将矩阵 M该行的剩余元素插入矩阵Q*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/p-row=i;/*给结点赋值 */p-col=pm-col;p-e=pm-e;p-right=NULL;pm=pm-right;/*pm指针向右移 */if(Q.rheadi=NULL)/*p为该行的第1 个结点 */Q.rheadi=pq=p;/*p 插在该行的表头且pq 指向 p(该行的最后一个结点)*/else /*插在 pq 所指结点之后 */pq-right=p;/*完成行插入 */pq=pq-right;/*pq指向该行的最后一个结点*/if(Q.cheadp-col=NULL)/*p为该列的第1 个结点 */Q.cheadp-col=colp-col=p;/*p插在该列的表头且colp-j指向 p*/else /*插在 colp-j所指结点之后*/名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 15 页 -colp-col-down=p;/*完成列插入 */colp-col=colp-col-down;/*colp-j指向该列的最后一个结点*/while(pn)/*将矩阵 N该行的剩余元素插入矩阵Q*/p=(OLink)malloc(sizeof(OLNode);/*生成矩阵Q的结点 */if(!p)exit(OVERFLOW);Q.tu+;/*非零元素数加1*/p-row=i;/*给结点赋值 */p-col=pn-col;p-e=-pn-e;p-right=NULL;pn=pn-right;/*pm指针向右移 */if(Q.rheadi=NULL)/*p为该行的第1 个结点 */Q.rheadi=pq=p;/*p插在该行的表头且pq 指向 p(该行的最后一个结点)*/else /*插在 pq 所指结点之后*/pq-right=p;/*完成行插入 */pq=pq-right;/*pq指向该行的最后一个结点*/if(Q.cheadp-col=NULL)/*p为该列的第1 个结点 */Q.cheadp-col=colp-col=p;/*p插在该列的表头且colp-j指向p*/else /*插在 colp-j所指结点之后 */colp-col-down=p;/*完成列插入 */colp-col=colp-col-down;/*colp-j指向该列的最后一个结点*/for(k=1;kdown=NULL;/*令该列最后一个结点的down 指针为空 */free(col);return OK;/主函数void main()int m,i,n;char c;CrossList M,N,Q;printf(*创建稀疏矩阵 M *n);CreateSMatrix(M);printf(t*稀疏矩阵M的通常阵列形式为:n);PrintSMatrix(M);printf(nt*创建稀疏矩阵 N*nn);CreateSMatrix(N);名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 15 页 -printf(t*稀疏矩阵N的通常阵列形式为:n);PrintSMatrix(N);m=M.mu;n=N.nu;if(!(Q.rhead=(OLink*)malloc(m+1)*sizeof(OLink)exit(OVERFLOW);if(!(Q.chead=(OLink*)malloc(n+1)*sizeof(OLink)exit(OVERFLOW);for(i=1;iN.nu)?(M.mu+1):(N.nu+1);i+)Q.rheadi=NULL;Q.cheadi=NULL;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;do printf(如做加法，请输入+，如做减法，请输入-，如做乘法，请输入*:t);getchar();scanf(%c,&c);if(c=+)AddMatrix(M,N,Q);printf(t*稀疏矩阵 M+N 的通常阵列形式为:n);PrintSMatrix(Q);else if(c=-)SubtSMatrix(M,N,Q);printf(t*稀疏矩阵 M-N的通常阵列形式为:n);PrintSMatrix(Q);else if(c=*)MultSMatrix(M,N,Q);printf(t*稀疏矩阵M*N的通常阵列形式为:n);PrintSMatrix(Q);else break;while(1);名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 15 页 -六、测试分析（运行结果）名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 15 页 -七、总结（收获及体会）通过此次的课程设计对十字链表存储的稀疏矩阵更深一步的理解和认识，一开始我们从参考书上找来了课题，但是毕竟是参考书，做到后来发现很多程序都是不完整的，这让我们伤透了脑筋。看着别的小组都弄得有模有样了，可是我们还没有一点头绪，好不容易又从网络和参考书找到了相关信息，可是结果还是很不尽人意。程序都弄好了，调试也没有问题，可是就是无法达到预期想要的结果。查阅的资料只是一个参考，最后还是要靠自己动脑筋，然后我们大家一起齐心协力，虽然内容并不是很复杂，但是我们觉得设计的过程相当重要，学到了很多，收获了很多。我觉得课程设计反映的是一个从理论到实际应用的过程，但是更远一点可以联系到以后毕业之后从学校转到踏上社会的一个过程。小组人员的配合相处，以及自身的动脑和努力，都是以后工作中需要的。八、参考文献数据结构（C 语言版）严蔚敏吴伟明 编著 清华大学出版社五、调试分析1、本程序中相乘部分较易，但是相加的部分则是让人伤脑筋，但最还仔细分析还是可以实现的。2、在用十字链表表示稀疏矩阵时，相加或相减所得的结果应该另生成，乘积矩阵也可用二维数组表示。3、通过数据的测试，能按要求实现功能。名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 15 页 -