课程设计报告材料—稀疏矩阵地完全链表表示及其运算

1、实用标准文档合肥学院计算机科学与技术系课程设计报告20222022学年第2学期课程数据结构与算法稀疏矩阵的完全链表表示及其运算课程设计名称学生姓名学号专业班级13软件工程2班指导教师陈老师2015年1月文案大全实用标准文档稀疏矩阵的完全链表表示及其运算【问题描述】稀疏矩阵的每个结点包含down,right,row,col和value五个域.用单独一个结点表示一个非零项,并将所有结点连接在一起,形成两个循环链表.使得第一个表即行表,把所有结点根据行序同一行内按列序用right域链接起来.使得第二个表即列表,把所有结点根据列序同一列内按行序用down链接起来.这两个表共用一个头结点.另外,增加一个

2、包含矩阵维数的结点.稀疏矩阵的这种存储表示称为完全链表表式.实现一个完全链表系统进行稀疏矩阵运算,并分析以下操作函数的计算时间和额外存储空间的开销.【设计目的】熟悉和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构【根本要求】建立一个用户友好、菜单式系统进行以下操作,并使用合当的测试数据测试该系统.读取一个稀疏矩阵建立其完全链表表示输出一个稀疏矩阵的内容删除一个稀疏矩阵两个稀疏矩阵相加两个稀疏矩阵相减两个稀疏矩阵相乘稀疏矩阵的转置【实现提示链表上的操作.二、数据结构的选择和概要设计一、问题分析1、功能要求：根据用户输入的矩阵,实现稀疏矩阵的求和运算,并输出结果.2、输入要求：矩阵的数据在

3、程序运行的时候由用户提供,先由用户输入稀疏矩阵的行数、列数和非零元个数.再根据非零元个数,输入这些非零元,还需要用户为这些非零元输入行、列和非零元的值.这样,一个稀疏矩阵就输入完成.3、用单链表存储非零元素的结点信息,并且将之用矩阵的形式打印出来二、概要设计1、结构体的定义typedefintElemType;structOLNodeinti,j;/非零元所在行、歹ElemTypee;/非零元值 OLNode*right,*down;typedefOLNode*OLink;structCrossListOLink*rhead,*chead;/行、列表头的头节点intmu,nu,tu;/矩阵的行

4、、列和非零元个数文案大全实用标准文档);2、存储结构选择采用十字链表存储稀疏矩阵,它是稀疏矩阵链式表示的一种较好的表示方法.在十字链表中,每一个非零矩阵元素存储在一个结点内.每一个节点除了存储非零元素的三元组以外,还设置了right 和down 两个指针,分别指向同一行的下一个非零元素结点和同一列的下一个非零元的结点.3、主函数主函数包括相加、相减、相乘的各个子函数.4、菜单具有选择功能的用户友好、菜单式系统,可以选择相应的功能来处理输入的数据.三、详细设计和编码1.设计表示(2)算法思想稀疏矩阵的每个结点包含down,right,row,col和value五个域.用单独一个结点表示一个非零项

5、,并将所有结点连接在一起,形成两个循环链表.使得第一个表即行表,把所有结点根据行序(同一行内按列序)用right域链接起来.使得第二个表即列表,把所有结点根据列序(同一列内按行序)用down链接起来.这两个表共用一个头结点.另外,增加一个包含矩阵维数的结点.稀疏矩阵的这种存储表示称为完全链表表式.(3)主要编码intCreate(CrossList&M)inti,j,k,m,n,t;ElemTypee;OLNode*p,*q;printf(请输入稀疏距阵的行数列数非零元的个数：);scanf(%d%d%d,&m,&n,&t);M.mu=m;M.nu=n;M.tu

6、=t;文案大全实用标准文档M.rhead=(OLink*)malloc(m+1)*sizeof(OLink);if(!M.rhead)exit(OVERFLOW);M.chead=(OLink*)malloc(n+1)*sizeof(OLink);if(!M.chead)exit(OVERFLOW);for(k=0;k!=m;k+)初始化行头指针M.rheadk=NULL;for(k=0;k!=n;k+)初始化列头指针M.cheadk=NULL;printf(请按任意次序输入d个非零元的行列元素值:n,M.tu);for(k=0;km|jn)printf(你输入的元素不在矩阵中请检查重输：n)

7、;exit(OVERFLOW);elsep=(OLNode*)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);p-i=i;P-j=j;p-e=e;if(M.rheadi=NULL|M.rheadi-jj)/p插入该行第一节点处p-right=M.rheadi;M.rheadi=p;else/寻找行表插入位置for(q=M.rheadi;q-right&q-right-jright);p-right=q-right;/完成行插入q-right=p;if(M.cheadj=NULL|M.cheadj-ii)/p插入该列第一节点处p-down=M.che

8、adj;M.cheadj=p;else/寻找列表插入位置文案大全实用标准文档(for(q=M.cheadj;q-down&q-down-idown);p-down=q-down;/完成歹U插入q-down=p;returnOK;intPrint(CrossListM)(returnOK;inti,j,k;OLinkp;intarray100100;for(i=0;i!=M.mu;i+)(for(j=0;j!=M.nu;j+)(arrayij=0;/for(k=0;k!=M.nu;k+)(p=M.cheadk;while(p)(arrayp-ip-j=p-e;/p=p-down;for(

9、i=0;i!=M.mu;i+)(for(j=0;j!=M.nu;j+)(if(j=M.nu-1)coutarrayijendl;elsecoutarrayijjj)/矩阵M当情前结点的列小于矩阵N当前结点的列(p=(OLink)malloc(sizeof(OLNode);/生成Q的结点if(!p)exit(OVERFLOW);Q.tu+;/非零元个数+1p-i=i;/赋值p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;/pm右移elseif(pm-jpn-j)(文案大全实用标准文档p=(OLink)malloc(sizeof(OLNode);if(!p)e

10、xit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pn-e;p-right=NULL;pn=pn-right;elseif(pm-e+pn-e)/M,N当前结点的列相同并且两元素之和非零p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pm-e+pn-e;p-right=NULL;pm=pm-right;/pm右移pn=pn-right;pn右移else/两元素相加为零pm=pm-right;pn=pn-right;continue;if(Q.rheadi=NUL

11、L)Q.rheadi=pq=p;elsepq-right=p;/完成行插入pq=pq-right;if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;elsecolp-j-down=p;/完成列插入colp-j=colp-j-down;文案大全实用标准文档while(pm)/将矩阵M该行的剩余元素插入矩阵Q(p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;if(Q.rheadi=NULL)Q.rheadi

12、=pq=p;else(pq-right=p;pq=pq-right;if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;else(colp-j-down=p;colp-j=colp-j-down;while(pn)/将矩阵N该行的剩余元素插入矩阵Q(p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pn-e;p-right=NULL;pn=pn-right;if(Q.rheadi=NULL)Q.rheadi=pq=p;else(pq-right=p;pq=pq-ri

13、ght;文案大全实用标准文档if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;elsecolp-j-down=p;colp-j=colp-j-down;for(k=0;k!=Q.nu;k+)if(colk)colk-down=NULL;free(col);returnOK;CrossListNegative(CrossListM)OLinkp;for(intj=0;j!=M.mu;j+)p=M.rheadj;while(p)p-e=-p-e;/将非零兀的值反号p=p-right;return(M);文案大全实用标准文档r.utdfiLueityintyudytrut

14、ruuyyuiileny.trAtr.utdfiLueityintyudytrutruuyyuiileny.trAtIUIrt,rt,i ii i 【I Ii iiuiui iu u尊k k匕m m廿yuyu _ii_iii iKM保输入的是h-essanykeytocontinueh-essanykeytocontinueintMult(CrossListM,CrossListN,CrossList&Q)(inti,j,e;OLinkq,p0,q0,q1,q2;if(M.nu!=N.mu)(printf(你输入的两个距阵不能进行此操作n);exit(OVERFLOW);else(Q.

15、mu=M.mu;Q.nu=N.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(i=0;i!=Q.mu;i+)/初始化行Q.rheadi=NULL;文案大全实用标准文档for(i=0;i!=Q.nu;i+)初始化列Q.cheadi=NULL;for(i=0;i!=Q.mu;i+)for(j=0;j!=Q.nu;j+)p0=M.rhe

16、adi;q0=N.cheadj;e=0;while(p0&q0)if(q0-ij)q0=q0-down;/列后移elseif(q0-ip0-j)p0=p0-right;行后移elsee=e+p0-e*q0-e;/乘积累加q0=q0-down;p0=p0-right;/行列后移if(e)/e不为零那么插入QQ.tu+;q=(OLink)malloc(sizeof(OLNode);if(!q)exit(OVERFLOW);q-i=i;q-j=j;q-e=e;q-right=NULL;q-down=NULL;if(!Q.rheadi)Q.rheadi=q1=q;elseq1=q1-right

17、=q;if(!Q.cheadj)Q.cheadj=q;elseq2=Q.cheadj;while(q2-down)q2=q2-down;q2-down=q;文案大全实用标准文档)returnOK;)四、上机调试过程1 .调试过程中遇到的主要问题是如何解决的：由于代码是仿照网上代码参照而写出来的,网上代码是C+编写的,所以局部代码需要改写成C语言,由于C+钺们没学过,所以还要通过查询书籍和网络了解C+诩言如何改写成C语言,1、coutendl;语句等价于printf例：cout你输入的是Select;等价于scanf(%d,&Select);其中Select是int型3、c语言中变量的定

18、义必须在函数的首部：for(int尸1六;Mmu：J+W像这种的要把intj;提出来2.对设计和编码的回忆讨论和分析：在设计方面,主要就是算法思想的设计,以及具体函数的设计运行.在这方面,主要的算法设计思想倒不是特别的难想,主要是具体函数例如加法的函数的具体设计)数非零元的个零元的行列元潸醯搦款鬣褊歌嗡02021111祢缺的是2 2以P1 1：6 6干果是31310 0比拟繁琐,消耗了较多时间.而在编码方面,由于c语言的学习还是在大一下学期,所以对于相关知识已经有所遗忘,所以在编码的过程遇到了不少问题需要查阅书籍,文案大全实用标准文档尤其涉及到具体代码的编写,更是花费了不少时间来修正调试.五、

19、测试结果及其分析1、改良设想：对于运算的界面可以更加精美有条理性一些；除此以外,可以给运算设计一个选择界面,用户可以选择进行计算和退出；由于局部代码是参考网上案列C+编码的,我想把它改成C语言代码,丹改正来后,他总是报错,调试也找不来原因,null指没有声明,但在头文件stdio.h中已有null值得申明,最后自定义个null值得声明,还是不行,所以导致我的局部代码有些不理解,这好似一局部遗憾,希望通过以后的学习和学习中明白这些原因.2、经验和体会：十字链表作为存储结构表示随机稀疏矩阵,进行两矩阵的相加运算,所以首先要定义一个十字链表作为存储结构.仅有此还是不够的,还需要定义指针来指向链表中的

20、元素.在开始的时候,老是得不到想象中的结果,通过几次的检查才发现问题出在对矩阵中的元素指向没有弄清楚,所以即使是相位置上的元素也没有处理好它们的相加问题.这个实验从最初的设计到完成,出现了很多错误,通过最终的修正发现,其实犯的都是小错误,都是些指针的问题.由于指针是我比拟薄弱的环节.我发现了这些问题,所以我就要进行弥补、查缺补漏.通过这次课程设计,敦促我将过去学习过的知识进行了温习,知识只有多稳固,才能真正的理解与领悟.六、用户使用说明按提示进行相关操作.3、先运行出来：出现主界面2、先选择你将要运算的功能,列如1、相加,然后输入你第一个稀疏矩阵的行、歹 h 非零元的个数,接着输入非零元素的行

21、、列和值；输入第二个稀疏矩阵的行、歹 h 非零元的个数,接着输入非零元素的行、列和值；3、输入完成后,点击回车,它会显示出你所输入的第一个稀疏矩阵、第二个稀疏矩阵,以及它们相加后得到的稀疏矩阵.源程序#include#include#include#include#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;structOLNode文案大全实用标准文档inti,j;/非零元所在行、列ElemTypee;/非零元值OLNode*right,*down;)；typedefOLNode*OLink;structCrossList

22、OLink*rhead,*chead;/行、列表头的头节点intmu,nu,tu;/矩阵的行、列和非零元个数);intCreate(CrossList&M)inti,j,k,m,n,t;ElemTypee;OLNode*p,*q;printf(请输入稀疏距阵的行数列数非零元的个数：);scanf(%d%d%d,&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;M.rhead=(OLink*)malloc(m+1)*sizeof(OLink);if(!M.rhead)exit(OVERFLOW);M.chead=(OLink*)malloc(n+1)*

23、sizeof(OLink);if(!M.chead)exit(OVERFLOW);for(k=0;k!=m;k+)/初始化行头指针M.rheadk=NULL;for(k=0;k!=n;k+)/初始化列头指针M.cheadk=NULL;printf(请按任意次序输入d个非零元的行列元素值:n,M.tu);for(k=0;km|jn)printf(你输入的元素不在矩阵中请检查重输：n);exit(OVERFLOW);)else文案大全实用标准文档(p=(OLNode*)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);p-i=i；P-j=j;p-e=e;if(M

24、.rheadi=NULL|M.rheadi-jj)/p插入该行第一节点处(p-right=M.rheadi;M.rheadi=p;else/寻找行表插入位置(for(q=M.rheadi;q-right&q-right-jright);p-right=q-right;/完成行插入q-right=p;if(M.cheadj=NULL|M.cheadj-ii)/p插入该列第一节点处(p-down=M.cheadj;M.cheadj=p;else/寻找列表插入位置(for(q=M.cheadj;q-down&q-down-idown);p-down=q-down;/完成歹U插入q-d

25、own=p;returnOK;intPrint(CrossListM)(inti,j,k;OLinkp;intarray100100;for(i=0;i!=M.mu;i+)(for(j=0;j!=M.nu;j+)(文案大全arrayij=0;/初始化数组所需局部实用标准文档)for(k=0;k!=M.nu;k+)(p=M.cheadk;while(p)(arrayp-ip-j=p-e;将非零元存入数组中p=p-down;)for(i=0;i!=M.mu;i+)(for(j=0;j!=M.nu;j+)(if(j=M.nu-1)coutarrayijendl;elsecoutarrayijjj)/

26、矩B$M当情前结点的列小于矩阵N当前结点的列p=(OLink)malloc(sizeof(OLNode);/生成Q的结点if(!p)exit(OVERFLOW);Q.tu+;/非零元个数+1p-i=i;/赋值p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;pm右移elseif(pm-jpn-j)p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pn-e;p-right=NULL;pn=pn-right;elseif(pm-e+pn-e)/M,N当前结点的

27、列相同并且两元素之和非零p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pm-e+pn-e;p-right=NULL;pm=pm-right;/pm右移文案大全实用标准文档pn=pn-right;/pn右移)else/两元素相加为零(pm=pm-right;pn=pn-right;continue;)if(Q.rheadi=NULL)Q.rheadi=pq=p;else(pq-right=p;/完成行插入pq=pq-right;)if(Q.cheadp-j=NULL)Q.cheadp-j=

28、colp-j=p;else(colp-j-down=p;/完成列插入colp-j=colp-j-down;)while(pm)/将矩阵M该行的剩余元素插入矩阵Q(p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;if(Q.rheadi=NULL)Q.rheadi=pq=p;else(pq-right=p;pq=pq-right;)if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;else文案大全实用标准文

29、档(colp-j-down=p;colp-j=colp-j-down;)while(pn)/将矩阵N该行的剩余元素插入矩阵Q(p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pn-e;p-right=NULL;pn=pn-right;if(Q.rheadi=NULL)Q.rheadi=pq=p;else(pq-right=p;pq=pq-right;)if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;else(colp-j-down=p;colp-j=colp-

30、j-down;)for(k=0;k!=Q.nu;k+)if(colk)colk-down=NULL;free(col);returnOK;)CrossListNegative(CrossListM)(OLinkp;for(intj=0;j!=M.mu;j+)(文案大全实用标准文档p=M.rheadj;while(p)(p-e=-p-e;将非零兀的值反号p=p-right;)return(M);)intMult(CrossListM,CrossListN,CrossList&Q)(inti,j,e;OLinkq,p0,q0,q1,q2;if(M.nu!=N.mu)(printf(你输入的两个距阵不能进行此操作n);exit(OVERFLOW);)else(Q.mu=M.mu;Q.nu=N.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(OVERFLO