数据结构——稀疏矩阵运算器

数据结构课程设计报告设计题目稀疏矩阵运算器年级_______________________班级_______________________姓名_____________________学号_____________________指导教师____________________起止时间____________________年二学期2022Q.rhead[k]=NULL;Q.chead[k]=NULL;fork=1;k=Q.nu;k++col=OLink*/*初始化Q的列头指针向量;各列链表为空链表mallocQ.*exitO VERFLOW;生成指向列nu+1*sizeofOLink;/fork=1;k=Q.nu;k++的最后结点的数组*/if!colcol[k]=NULL;fori=l;i=M.mu;i++/*赋初值*/pm=M.rhead[i];pn=N.rhead[i];/*按行的顺序相减*/whilepmpn浮指向矩阵的第行的第个结点刃户pm Mi1pnifpm-colpn-col*/指向矩阵的第行的第个结点*//*和N i1pm均不空*/pn/*矩阵当前结点的列小于矩阵当前结点的列M N生成矩阵的结点*/p=OLinkmallocsizeofOLNode;/*Q if!p exitO VERFLOW;/*非零元素数加Q・m++;i*/〉/*给结点赋值*/P row=i；p-col=pm-col;p-e=pm-e;p-right=NULL;pm=pm-ri2ht;指针向右移*/}/*pmelse ifpm-colpn-col列*//*矩阵当前结点的列大于矩阵当前结点的M N生成矩阵的结点*/p=OLinkmallocsizeofOLNode;/*Q if!p exitOVERFLOW;/*非零元素数加Q.tu++;1*//*给结点赋值*/p-row=i;p-col=pn-col;p-e=-pn-e;p-right=NULL;指针向右移*/pn=pn-right;/*pn/*矩阵、当前结点的列相等且两元素之差不为else ifpm-e-pn-e M N0*/exitOVERFLOW;Q.tu++;/*非零元素数加1*/p-row=i;/*给结点赋值*/p-col=pn-col;生成矩阵的结点*/p=OLinkmallocsizeofOLNode;Q if!pp-e=pm-e-pn-e;ifQ.rhead[i]==NULLp-right=NULL;指针向右移*//*pmpm=pm-right;pn=pn-right;/*pn指针向右移*/else/*矩阵、当前结点的列相等且两元素之差为M N0*/pm=pm-right;指针向右移*//*pmpn=pn-right;指针向右移*//*pncontinue;为该行的第个结点*//*p1Q.rhead[i]=pq=p;else插在该行的表头且指向（该行的最后一个结点）*//*pq-right=p;/*p pqppq=pq-right;}插在所指结点之后*/pq为该列的第个结点*//*p1ifQ.chead[p-col]==NULL插在该列的表头且指向/*/*p col[p-j]Q.cheadlp-colJ=col[p-colJ=p;p*/插在所指结点之后*/else col[p-]col[p-colj-down=p;col[p-col]=col[p-col]-down;*//*完成列插入*/whilepm指向该列的最后一个结点/*col[p-j]p=OLinkmallocsizeofOLNode;if!p/*完成行插入*/指向该行的最后一个结点*//*pq/*将矩阵该行的剩余元素插入矩阵M Q*//*生成矩阵的结点*/QexitOVERFLOW;Q.tu++;/*非零元素数加1*/p-row=i;/*给结点赋值*/p-col=pm-col;p-e=pm-e;p-right=NULL;pm=pm-right;指针向右移*/ifQ.rhead[i]==NULL/*pmQ.rhead[i]=pq=p;为该行的第个结点*//*p1插在该行的表头且指向（该行的最后一个结点）/*p pqp/*else{pq-nght=p;pq=pq-right;/*完成行插入*/指向该行的最后一个结点*//*pqifQ.chead[p-col]==NULL/*p为该列的第1个结点*/Q.chead[p-col]=col[p-col]=p;*/else/*p插在该列的表头且col[p-j]指向p插在所指结点之后*/pq/*插在所指结点之后*/col[p-j]col[p-col]-down=p;/*完成列插入*/col[p-col]=col[p-col]-down;}指向该列的最后一个结点*//*col[p-j]whilepn/*将矩阵该行的剩余元素插入矩阵N Q*/p=OLinkmallocsizeofOLNode;i为该列的第个结/*p1fif!p/*生成矩阵的结点*/点*/QQ.chead[p-c/*p插在该列的表头且exitOVERFLOWol]==NULL；指向/*Q.tu++;/*非零元素数加col[p-j]1*/Q.chead[p-cp-row=i;/*给结点赋值*/ol]=col[p-cop-col=pn-col;插在所指结点之col[p-j]l]=p;p-e=-pn-e;后*/p*/p-right=NULL;pn=pn-right;指针向右移*//*pmifQ.rhead[i]==NULL为该行的第个结点*/Q.rhead[i]=pq=p;/*p1点*/插在该行的表头且指向该行的最后一个结/*/*p pqpelse插在所指结点之后*/pqpq-right=p;pq=pq-right;/*完成行插入*/else指向该行的最后一个结点*//*pqcol[p-col]-down=p;/*完成列插入*/colfp-col]=colfp-col]-down;}指向该列的最后一个结点*//*col[p-j]fork=1;kv=Q.nu;k++ifcol[k]col[k]-down=NULL;/*k列有结点*/freecol;/*令该列最后一个结点的指针为空*/downreturn OK;〃主函数void mainint m,i,n;char c;CrossList M,N,Q;创建稀疏矩阵CreateSMatrix M;稀疏矩阵的通常阵列形式为MPrintSMatrix M;创建稀疏矩阵CreateSMatrixN;

六、测试分析（运行结果）印市京诺^丰目［^MMM aMMXMM请输入稀疏矩阵的行数列数非零元个数444请输入笫个非零元的行号列号非零元素值清输入笫1112个非零元的行号列号非零元素值式」输入第个非零元23的行号列号非零元素值;3清输入第工m e元素值x24流为H129e ee e eee-3e24ee e制灌稀疏坦阵，N臂清输入稀疏矩阵的行数列数非零元个数:44请输入笫个非零元的行号列号非零元素值1:1清输入笫个非零元的行号列号非零元素值请输入第2:212个非零元的行号列号非零元素值门3请输入笫4个三乒元素值门24乡式为，X j|xo8-38120g09e8g24080如做加法,请■帝霸勺渊做乘法请输入…e1260I120000I60024Ie240I请输入・•I H1212-12005-1200-24!I e0240I.口做加法，请输入.和做减法，请蜀人”疏.请输入*:资矩南喇的通常阵冽i1I22B1212216I-12000000-24I-12!加做加法，请输入如您减法，请输入-,245762163Press如做乘法,请输入*:any keyto continue.»»

七、总结（收获及体味）通过此次的课程设计对十字链表存储的稀疏矩阵更深一步的理解和认识，一开始我们从参考书上找来了课题，但是毕竟是参考书，做到后来发现不少程序都是不完整的，这让我们伤透了脑筋看着别的小组都弄得有模有样了，可是我们还没有一点头绪，好不容易又从网络和参考书找到了相关信息，可是结果还是很不尽人意程序都弄好了，调试也没有问题，可是就是无法达到预期想要的结果查阅的资料只是一个参考，最后还是要靠自己动脑筋，然后我们大家一起齐心协力，虽然内容并非很复杂，但是我们觉得设计的过程相当重要，学到了不少，收获了不少我觉得课程设计反映的是一个从理论到实际应用的过程，但是更远一点可以联系到以后毕业之后从学校转到踏上社会的一个过程小组人员的配合相处，以及自身的动脑和努力，都是以后工作中需要的

八、参考文献数据结构（语言版）严蔚敏吴伟明编著清华大学出版社C

五、调试分析、本程序中相乘部份较易，但是相加的部份则是让人伤脑筋，但最还子细分析1还是可以实现的、在用十字链表表示稀疏矩2阵时，相加或者相减所得的结果应该另生成，乘积矩阵也可用二维数组表示、通过数据的测试，能按要求实现功能3

一、实验目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开辟打好基础

二、问题描述具体任务设计、实现两个稀疏矩阵在十字链表表示方法下的相加、相减、相乘稀疏矩阵是指那些多数元素为零的矩阵利用稀疏特点进行储存和计算可以大大节省储存空间，提高计算效率实现一个能进行称稀疏矩阵基本运算的运算器

三、需求分析该程序所做的工作的是稀疏矩阵运算器，实现两个稀疏矩阵的基本运算此程序规定、1按照压缩存储的概念，只存储稀疏矩阵的非零元，以两个三元组｛来｝表示矩阵的非i,j,零元的行，列和数值，就确定了一个非零元.由此，稀疏矩阵可由表示非零元的三元数组及行列数确定、用户输入数据作为三元组的行，列和非零元的个数，用空格隔开.并输入非零元的行，2列和数值、本程序只对两个矩阵进行四则运算，所的结果矩阵应该另生成，用十字链表存放，并3放入新的矩阵中，只要对矩阵求解就能求出答案.

四、算法设计思想及流程图用十字链表存储方式实现稀疏矩阵的基本运算，此程序用到以下函数〃创建储存稀疏矩阵void CreateSMatrixCrossListR//输出十字链表的函数void PrintSMatrixCrossListR〃实现矩阵乘法void MultSMatrixCrossListM,CrossList N,CrossList Qint AddMatrixCrossList〃实现矩阵加法M,CrossList N,CrossList Qint SubtSMatrixCrossListM,CrossList N,CrossList〃实现矩阵减法主函数调用以上函数来实现其功能Q voidmain//首先调用创建矩阵和并输入稀疏矩阵的行数，列数，非零元素个数，通过CreateSMatrix M N,输出矩阵和根据提示选择相应的运算，当进行加或者减运算时，如果两个PrintSMatrix M N,矩阵的行和列不相等时，就无法得到结果，并浮现提示错误信息，当进行乘法运算时，要求矩阵的列数必须等于矩阵的行数，否则无法进行乘法运算，为了进行多种运算通过主函M N数的循环来实现，退出循环条件是输入“以外的任意字符即可退出循环Do-—While

五、语言源代码C#includestdio.h#includestdlib.h#define OVERFLOW-1#define OK1#define NULL0〃建立十字链表typedef struct OLNode〃该非零元的行和列下标int row,col;int e;//该非零元所在行表和列表structOLNoderight,*down;的后继链域｝OLNode,*OLink;typedef struct{OLink*rhead,*chead;〃行和列链表头指针向量基址由CreateSMatrix//分配int mu,nu,tu;系数矩阵的行数，列数和非零元个数「l rnecTicf*void CreateSMatrixCrossListR//创建储看稀疏矩阵intm,n,t,i,j,k,a;OLink p,q;ifR.rhead R.rhead=NULL;R.chead=NULL;R.mu=0;R.nu=0;R.tu=0;请输入稀疏矩阵的行数列数非零元个数R.mu=m;R.nu=n;R.tu=t;if!R.rhead=OLink*mallocm+l*sizeofOLinkexitOVERFLOW;if!R.chead=OLink二*mallocn+1*sizeofOLinkexitOVERFLOW;fori=l;i R.mu+1;i++R.rhead[i]=NULL;fori=l;i=R.nu+1;i++R.chead[i]=NULL;fork=l;k=R.tu;k++请输入第％^个非零元的行号列号非零元素值1if!p=OLNode*mallocsizeofOLNodeexitOVERFLOW;p-row=i;p-col=j;p-e=a;ifR.rhead[i]==NULL||R.rhead[i]-coljp-right=R.rhead[i];R.rhead[i]=p;elseforq=R.rhead[i];q-rightq-right-colj;q=q-right;p-right=q-right;q-right=p;ifR.chead[j]==NULL||R.chead[j]-rowip-down=R.chead[j J;R.chead[j]=p;elseforq=R.chead[j];q-downq-down-rowi;q=q-down;p-down=q-down;q-down=p;〃输出十字链表的函数void PrintSMatrixCrossListRintij；int b=0;OLink p;fori=1;i=R.mu;i++p=R.rhead[i];forj=l;j=R.nu;j++ifp!=NULLifj==p-colp=p-right;elseelse〃实现矩阵乘法void MultSMatrixCrossListM,CrossList N,CrossList Qint i,j,temp=0;OLink q,pm,pn,pq;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;ifM.nu!=N.mu这两个矩阵不能相乘exitOVERFLOW;〃矩阵相乘条件，矩阵的行数必须等于矩阵的列数12ifM.tu*N.tu!=Ofori=1;i=M.mu;i++forj=1;j v=N.nu;j++{temp=;pm=M.rhead[i];pn=N.chead[jl;whilepm whilepnpmpm-colpn-row{ifpn-down!=NULL pn=pn-down;else pn=NULL;ifpmpnpm-col==pn-row temp+=pm-e*pn-e;ifpm-right!=NULL pm=pm-right;else pm=NULL;ifpn-down!=NULL pn=pn-down;else pn=NULL;else{ifpm-right!=NULL pm=pm-right;else pm=NULL;}}//whilepm iftemp{if!pq=OLNode*mallocsizeofOLNodeexitOVERFLOW;pq-row=i;pq-col=j;pq-e=temp;ifQ.rhead[i]==NULL||Q.rhead[i]-colj pq-right=Q.rhead[i];Q.rhead[i]=pq;else forq=Q.rhead[iJ;q-rightq-colj;q=q-right;pq-right=q-right;q-right=pq;}ifQ.chead[j]==NULL||Q.chead[j]-rowi pq-down=Q.chead[j];Q.chead[j]=pq;elseforq=Q.chead|j];q-downq-rowi;q=q-down;pq-down=q-down;q-down=pq;Q.tu++;}//if temp}//forj}//for i}//for if}//MultSMatrix〃实现矩阵加法int AddMatrixCrossListM,CrossList N,CrossList Q{/*初始条件:稀疏矩阵与的行数和列数对应相等*/M N/*操作结果求稀疏矩阵的差Q=M+N*/int i,k;OLink p,pq,pm,pn;OLink*col;ifM.mu!=N.mu||M.nu!=N.nufori=1;i=M.mu;i++/*按行的顺序相加*/两个矩阵不是同类型的，不能相加pm=M.rhead[i];exitOVERFLOW;pn=N.rhead[i];whilepmpn/*初始化矩阵*/Q.mu=M.mu;QQ.nu=M.nu;ifpm-colpn-col/*元素个数的初值*/Q.tu=0;Q.rhead=OLink*mallocQ.mu+1*sizeofOLink;if!Q.rheadexitO VERFLOW;exitOVERFLOW;Q.chead=OLink*mallocQ.nu+l^sizeof OLink;Q.tu++;if!Q.cheadp-row=i;exitOVERFLOW;p-col=pm-col;/*初始化的行头指p-e=+pm-e;fork=l;k=Q.mu;k++Qp-right=NULL;针向量;各行链表为空链表*/pm=pm-right;Q.rhead[k]=NULL;/*初始化的列头指fork=l;k=Q・nu;k++Qelse ifpm-colpn-col针向量;各列链表为空链表列*/*/Q.cheadLk]=NULL;生成指向列的最后结点的数组*/col=OLink*mallocQ.nu+1*sizeofOLink;/*if!colexilOVERFLOW;/*赋初值*/fork=l;k=Q.nu;k++col[k]=NULL;浮指向矩阵的第行的第个结点*/浮pm Mi1pn指向矩阵的第行的第个结点*//*和N i1pm均不空*/pn/*矩阵当前结点的列小于矩阵当前结点的列MN生成矩阵的结点*/p=OLinkmallocsizeofOLNode;Q if!p/*非零元素数加1*/指针向右移*//*pm/*矩阵当前结点的列大于矩阵当前结点的MN生成矩阵的结点*/p=OLinkmallocsizeofOLNode;/*Q if!p exitOVERFLOW;/*非零元素数加Q.tu++;1*/p-row=i;p-col=pn-col;p-e=+pn-e;p-right=NULL;指针向右移*/pn=pn-right;/*pnelse ifpm-e+pn-ep=OLinkmallocsizeofOLNode;if!pexitOVERFLOW;Q.tu++;p-row=i;p-col=pn-col;p-e=pm-e+pn-e;p-right=NULL;pm=pm-right;pn=pn-right;}elsepm=pm-right;pn=pn-right;continue;（）为该行的第个结点*/if Q.rhead[i]==NULL/*p1插在该行的表头且指向（该行的最后一个结点）*//*插在Q.rhead[i]=pq=p;/*p pqp所指结点之后*/pqpq-right=p;/*完成行插入*/pq=pq-right;}指向该行的最后一个结点*//*pqifQ.chead[p-col]==NULL为该列的第个结点*//*p1Q.chead[p-col]=col[p-colJ=p;p*/插在该列的表头且指向/*/*p col[p-j]else{col[p-col]-down=p;col[p-col]=col[p-col]-down;*/插在所指结点之后*/col[p-]/*完成列插入*/whilepm指向该列的最后一个结点/*col[p-j]p=OLinkmallocsizeofOLNode;if!p/*生成矩阵Q的结/*将矩阵M该行的剩余元素插入矩阵Q*/exitOVERFLOW;点*/Q.tu++;p-row=i;p-col=pm-col;/*非零元素数加1*/p-e=pm-e;p-right=NULL;/*矩阵、当前结点的列相等且两元素之差为*/M Npm=pm-right;ifQ.rhead[i]==NULLQ.rhead[iJ=pq=p;/*pm指针向右移*/指针向右移*//*pnelsepq-right=p;pq=pq-right;/*给结点赋值*/指针向右移*//*pm为该行的第个结点*//*p1插在该行的表头且指向（该行的最后一个结点）/*/*p pqp插在所指结点之后*/pq/*完成行插入*/指向该行的最后一个结点刃/*pqifQ.chead[p-col]==NULL为该列的第个结点*//*p1Q.chead[p-colJ=col[p-col]=p;*/插在该列的表头且指向/*p col[p-j]pelse/*collp-col]-down=p;插在所指结点之后*/col[p-j]col[p-col]=col[p-col]-down;}/*完成列插入*/whilepn指向该列的最后一个结点/*col[p-j]I*/p=OLinkmallocsizeofOLNode;if!pexitOVERFLOW;Q.tu++;/*将矩阵该行的剩余元素插入矩阵N Q*//*生成矩阵的结点*/Q非零元素数加1*/p-row=i;/*给结点赋值*/p-col=pn-col;p-e=+pn-e;p-right=NULL;pn=pn-right;指针向右移*//*pmifQ.rhead[i]==NULL为该行的第个结点*//*p1Q.rhead[i]=pq=p;插在该行的表头且指向（该行的最后一个结/*点*//*p pqpelse插在所指结点之后*/pqpq-right=p;pq=pq-right;/*完成行插入*/指向该行的最后一个结点*//*pqifQ.chead[p-col]==NULL为该列的第个结点*//*p1Q.cheadfp-col]=colfp-col]=p;插在该列的表头且〉指向/*p col[p-j]p*/else插在〉所指结点之后*/col[p-j]{col[p-col]-down=p;col[p-col]=col[p-col]-down;}/*完成列插入*//*col[p-j]指向该列的最后一个结点*/fork=1;k=Q.nu;k++ifcol[k]列有结点*//*kcol[k]-down=NULL;/*令该列最后一个结点的指针为空*/downfreecol;return OK;〃实现矩阵减法int SubtSMatrixCrossListM,CrossList N,CrossList Q{/*初始条件:稀疏矩阵与的行数和列数对应相等刃MN/*操作结果求稀疏矩阵的差Q=M-N*/int i,k;OLink p,pq,pm,pn;OLink*col;ifM.mu!=N.mu||M.nu!=N.nu两个矩阵不是同类型的，不能相减exitOVERFLOW;/*初始化矩阵*/Q.mu=M.mu;QQ.nu=M.nu;二°；/*元素个数的初值*/Q・mQ.rhead=OLink*mallocQ.mu+l*sizeofOLink;if!Q.rheadexitOVERFLOW;Q.chead=OLink*mallocQ.nu+1*sizeofOLink;if!Q.cheadexitOVERFLOW;/*初始化的行头指针向量;各行链表为空链表*/fork=l;k=Q.mu;k++Q。