稀疏矩阵应用

1、稀疏矩阵应用课题简介1.1课题及要求稀疏矩阵应用(限1人完成)设计要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。(1) 稀疏矩阵的存储(2) 稀疏矩阵加法(3) 矩阵乘法(4) 矩阵转置1.2课程任务分析本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表示， 并在两种不同的存储结构下， 求两个具有相同行列数的稀疏矩阵 A和B的相加矩阵C,并输出C;求 出A的转置矩阵D,输出D;求两个稀疏矩阵A和B勺相乘矩阵E,并输出E。1.3课程的意义其意义是让我们在学习完 G数据结构等课程

2、基础上，掌握多维数组的逻辑结构和存储结 构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等基本操作，并用不同的方法输出结果，进 一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分 析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。程序分析2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。首先要定义两种不同的结构体类型，在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组 和十字链表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵 都为

3、空值，特别注意在十字链表下，对变量进行动态的地址分配。在设计输出稀疏矩阵的值的 函数时，也要针对两种不同的情况，分别编制函数，才能准确的输出稀疏矩阵。在对稀疏矩阵 进行初始化及输出值时，均只输出非零元素的值和它所在的所在行及所在列。2.2构造函数进行稀疏矩阵的转置并输出结果本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果，由于对稀疏函数的转置只对一个矩阵进行操作，所以实现起来难度不是很大，函数也比较容易编写。在编写函数时，要 先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。2.3构造函数进行两个稀疏矩阵相加及相乘并输出最终的稀疏矩阵本模块要求设计相加和相乘函数对两个矩阵

4、进行运算，并输出最终的稀疏矩阵，在进行运 算前，要对两个矩阵进行检查，看是不是相同类型的矩阵，因为两个矩阵相加要求两个矩阵一 定是同一类型的矩阵，定义相应的矩阵类型用于存放两个矩阵相加相乘后的结果矩阵，这个结 果矩阵的行数列数需要综合多方面情况来确定。这四个函数也是整个程序的难点，需要灵活运 用数组及指针的特点。2.4退出系统本模块要求设置选项能随时结束程序的运行，本程序中采用exit (0)函数。程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。概要设计3.1主界面设计为了实现在两种存储结构下对稀疏矩阵的多种算法功能的管理

5、，首先设计一含有多个菜单 项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图 1所示。图1主界面图3.2存储结构设计本系统采用三元组结构和十字链表结构存储稀疏矩阵的具体信息。其中：在三元组中，所 有元素的信息用数组表示，每个数组元素中包含有行下标(i),列下标(j)和对应的数值(e),它们是整型数据，全部的信息用在十字链表中，全部结点的信息用结构体(TSMatrix )包含，包括用数组(Triple data MAXSIZE )和总共的行数(mu)，列数(nu)以及非零元素的 个数(tu)。在十字链表下，头结点为指针数组的十字链表存储；每个结点里面包

6、含行下标(i),列下标(j)和对应的数值(e)，它们是整型数据，还有两个指针 (right)、(down),属于OLNode结 构体。全部的信息用结构体 (crosslist)包含，包括指针数组(OLink* rhead和*chead)和总共的行 数(mu)，列数(nu)以及非零元素的个数(tu)。三元组结构体定义typedef struct(int i,j;int e;Triple;typedef struct(Triple dataMAXSIZE;int rposMAXSIZE + 1;int nu, mu,tu; TSMatrix ;十字链表结构体定义：typedef struct OL

7、Nodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu;OLink *rhead,*chead;CrossList;3.3系统功能设计本系统除了要完成分别在三元组存储结构以及在十字链表下实现稀疏矩阵的初始化功能外还设置了 4个子功能菜单。稀疏矩阵的建立及初始化在三元组存储结构下，由函数voidCreateSMatrix (TSMatrix &M)实现， 在十字链表存储结构下， 由函数void CreateSMatix_OL (CrossList & M)依据读入

8、的行数和列数以及非零元素的个数，分别设定每个非 零元素的信息。4个子功能的设计描述如下。(1) 稀疏矩阵的转置：此功能在三元组存储结构下，由函数 void TransposeSMatrix(TSMatrix M,TSMatrix &T)实 现，在十字链表存储结构下，由函数 void TurnSMatrix_OL(CrossList &M)实现。当用户选择 该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。(2) 稀疏矩阵的加法：此功能在三元组存储结构下，由函数 void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S

9、)实现，在十字链表存储结构下，由函数 int SMatrix_ADD(CrossList *A,CrossList *B)实现。当用 户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输 出结果。(3) 稀疏矩阵的乘法：此功能在三元组存储结构下，由函数 int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)实现。在十字链表存储结构下，由函数 int MultSMatrix_OL(CrossList M, CrossList N, CrossList&Q)实现。当用户选择该功能，系统提示输入要进行相乘

10、的两个矩阵的详细信息。然后进行相 乘，最后得到结果。(4)退出：即退出稀疏矩阵的应用系统，由 exit(0)函数实现。当用户选择该功能，则退出该稀疏矩 阵的应用系统。调试分析4.1系统运行主界面系统运行主界面如图2所示:-13 -图2主界面图4.2各子功能测试运行结果(以三元组为例)(1) 稀疏矩阵的创建及初始化:在主菜单下，用户输入1回车，是用三元组创建稀疏矩阵，根据屏幕提示初始化一个稀疏矩阵，按enter键，运行结果如图3所示。璧口非零元个裁 在歹!)星大八： 在歹!)辰太卜;j孳普IJ建稀疏矩阵，请选择操作=青你选寸巡健稀疏 L用三元组仓 表=魂出程序柠列美小1262 343 1B经选择

11、三疏矩性和加 .日辞距住相乘 k：退出程序图3三元组仓!j建并初始化矩阵(2) 稀疏矩阵的转置:用三元组创建稀疏矩阵后，用户输入 1回车，便显示该矩阵的转置矩阵，运行结果如图4所图4三元组稀疏矩阵转置结果示意图(3) 稀疏矩阵的相加：用三元组创建并初始化一个稀疏矩阵后，输入2回车，按屏幕提示输入第二个同类型的稀疏矩阵，按enter键，运行结果如图5所示。请选择操作:-羞坐阵： 另WWU 入元元元的厂 叟入会丁 88112 3 312 3 12歹二主krTTTF74 9 数2 3 2 行1 2 3 的 矩大大大 疏魇及.列数和非零元个数:图5三元组稀疏矩阵相加结果示意图(4) 稀疏矩阵的相乘：用

12、三元组创建并初始化一个稀疏矩阵后，输入3回车，按屏幕提示输入第二个同类型的稀疏矩阵，按enter键，运行结果如图6所示。甬兰弓主目上 , I 1 I 请选择操作:行列序 E-ps_nE组创建稀疏矩阵, 专置M辄另一个稀疏矩阵:请输入稀疏矩阵的行数、列数和非零元个教眯2瑾芈雷买素坐桥（ 寻后的矩阵为（只列出非蓼完素）.行麹关小1 3352 3283 148意键继续枷八陶骊枳阡t塞歹!）及大七、116 ，在歹!）及大U 23? 吞歹心及大小* 3 1?（5）退出：在主菜单下，用户输入图8。图6三元组稀疏矩阵相乘结果示意图3回车，或者在下级菜单中输入 4回车，退出程序。运行结果如图7,图7主菜单退出

13、程序图图8下级菜单退出程序图总结由于本程序要求用两种办法对稀疏矩阵进行运算，特别是用十字链表这种形式来对稀疏矩 阵进行运算，是实现起来有很多困难，主要包括：1、书上这种方面的东西不多，资料少，可以参考的东西不是很多；2、用十字链表进行运算比较复杂，难度较大，需要对指针掌握较好；3、在书写课程设计报告时，没有具体的模板，感觉无从下手。针对上述困难，我通过网络，图书馆找资料，借鉴别人的以往的优秀的课程设计报告，和 同学们一起讨论，逐步地解决自己的问题。通过此次课程设计，使我对本学期学的数据结构有了更深的了解，也使自己的所学更加 牢固，并能够把更方面的知识综合起来运用。附录：程序源代码#includ

14、e<stdio.h>#include<stdlib.h>#define MAXSIZE 100int num100;typedef struct OLNodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu;OLink *rhead,*chead;CrossList;十字链表结构体定义typedef structint i,j;int e;Triple;typedef structTriple dataMAXSIZE;int rposMAXSIZE + 1

15、;int nu,mu,tu;TSMatrix;三元组结构体定义；int CreateSMatix_OL(CrossList &M)int i,j,e;OLink q;OLink p;printf("请输入稀疏矩阵的行数，列数，非零元素的个数:");矩阵行数，列数下标均从开始；scanf("%d%d%d",&M.mu,&M.nu,&M.tu);M.rhead=(OLink *)malloc(M.mu+1)*sizeof(OLNode);/分配内存空间M.chead=(OLink *)malloc(M.nu+1)*sizeof

16、(OLNode);/分配内存空间for( i=1;i<=M.mu;i+)M.rheadi=NULL;/把矩阵每个元素置空值for( i=1;i<=M.nu;i+)M.cheadi=NULL;printf("请输入稀疏矩阵，如果行为 0,则退出n");scanf("%d%d%d”,&i,&j,&e);while(i!=0)p=(OLink)malloc(sizeof(OLNode);p->i=i;p->j=j;p->e=e;if(M.rheadi=NULL|M.rheadi->j>j)p->ri

17、ght=M.rheadi;M.rheadi=p;elseq=M.rheadi;while(q->right&&q->right->j<j)q=q->right;p->right=q->right;q->right=p;if(M.cheadj=NULL|M.cheadj->i>i)p->down=M.cheadj;M.cheadj=p;elseq=M.cheadj;while(q->down&&q->down->i<i)q=q->down;p->down=q-&g

18、t;down;q->down=p;scanf("%d%d%d",&i,&j,&e);return 1;/创建十字链表void CreateSMatrix(TSMatrix &M)/米用三兀组顺序表存储表示，创建稀疏矩阵Mprintf("请输入稀疏矩阵的行数、列数和非零元个数：");scanf("%d%d%d",&M.mu,&M.nu,&M.tu);if(M.mu<=0)|(M.nu<=0)|(M.tu<=0)|(M.tu>M.mu*M.nu)判断行值

19、、列值、元素个数是否合法printf("输入有误！");for(int i=1;i<=M.tu;i+)/输入稀疏矩阵元素printf("请输入元素坐标(所在行，所在列)及大小：");scanf("%d%d%d”,&M.datai.i,&M.datai.j,&M.datai.e);if(M.datai.i<=0)|(M.datai.j<=0)printf(-输入错误，请重新输入");scanf("%d%d%d",&M.datai.i,&M.datai.j,&a

20、mp;M.datai.e);/if/for iint num100;if(M.tu)int i;for(i = 1; i <= M.mu; i+) numi = 0;/ 初始化for(int t = 1; t <= M.tu; t+) +numM.datat.i;/求M 中每一行含非零元素个数/ 求 rposM.rpos1 = 1;for(i = 2; i <= M.mu; i+) M.rposi = M.rposi-1 + numi-1;/创建三元组void TransposeSMatrix(TSMatrix M,TSMatrix &T)T.nu=M.mu;/T矩阵

21、存放转置后的矩阵T.mu=M.nu;T.tu=M.tu;int q=1;for(int col=1;col<=M.nu;col+)/通过循环，把非零元素的行数与列数进行交换，实现转置for(int p=1;p<=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;q+;/三元组转置int Compare(int a1,int b1,int a2,int b2)if(a1>a2)return 1;else if(a1<a2)return -1;else i

22、f(b1>b2)return 1;if(b1<b2)return -1;else return 0;void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S)/矩阵 S 存放相加后的矩阵S.mu=M.mu>T.mu?M.mu:T.mu;/ 对S矩阵的行数赋值S.nu=M.nu>T.nu?M.nu:T.nu;/ 对S矩阵的列数赋值S.tu=0;int ce;int q=1;int mcount=1,tcount=1;while(mcount<=M.tu&&tcount<=T.tu)switch(C

23、ompare(M.datamcount.i,M.datamcount.j,T.datatcount.i,T.datatcount.j)/用switch分支语句，用compare函数对需要相加的两个矩阵的某元素行数列数进行比较case -1: S.dataq.e=M.datamcount.e;/ 当 M.datamcount.i<T.datatcount.i 或 M.datamcount.j<T.datatcount.jS.dataq.i=M.datamcount.i;S.dataq.j=M.datamcount.j;/把第一个矩阵的行数i,列数j赋值给S矩阵的行数i,列数j q+;

24、mcount+;break;case 1: S.dataq.e=T.datatcount.e;/ 当 M.datamcount.i>T.datatcount.i 或M.datamcount.j>T.datatcount.jS.dataq.i=T.datatcount.i;S.dataq.j=T.datatcount.j;/把第二个矩阵的行数i,列数j赋值给S矩阵的行数i,列数jq+;tcount+;break;case 0: ce=M.datamcount.e+T.datatcount.e;/ 其他情况下把两个矩阵的值相加if(ce) S.dataq.e=ce;S.dataq.i=

25、M.datamcount.i;S.dataq.j=M.datamcount.j;q+;mcount+;tcount+;else mcount+;tcount+;break;while(mcount<=M.tu)(S.dataq.e=M.datamcount.e;S.dataq.i=M.datamcount.i;S.dataq.j=M.datamcount.j;q+;mcount+; /在case=-1的情况下对S矩阵的非零值，行数，列数进行赋值while(tcount<=M.tu)(S.dataq.e=T.datatcount.e;S.dataq.i=T.datatcount.i;

26、S.dataq.j=T.datatcount.j;q+;tcount+;/在case=1的情况下对S矩阵的非零值，行数，列数进行赋值S.tu=q-1;/三元组相加int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)( int arow, brow, ccol, i, t, ctemp100, p, q, tp;/ 定义相乘函数中所需要用到的变量if(M.nu != N.mu) return 0;/如果第一个矩阵的行数不等于第二个矩阵的列数，则退出Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0;/三元组结构类型 Q

27、存放相乘后的结果if(M.tu * N.tu != 0)/如果两个矩阵元素相乘不为零，则进行运算for(arow = 1; arow <= M.mu; +arow)/最外侧循环以矩阵行数作为循环变量( for(i = 0; i <= N.nu; +i) ctempi = 0;Q.rposarow = Q.tu + 1;if(arow < M.mu) tp = M.rposarow + 1;else tp = M.tu +1;for(p = M.rposarow; p < tp; +p)/ 把每行与每列相乘brow = M.datap.j;if(brow < N.m

28、u) t = N.rposbrow+1;else t = N.tu + 1;for(q = N.rposbrow; q < t; +q)ccol = N.dataq.j;ctempccol += M.datap.e * N.dataq.e;/ 值相乘for(ccol = 1; ccol <= Q.nu; +ccol) /把运算后的结果存放到 Q中 if(ctempccol)if(+(Q.tu) > MAXSIZE) return 1;Q.dataQ.tu.i = arow, Q.dataQ.tu.j = ccol, Q.dataQ.tu.e = ctempccol;retur

29、n 1;/三元组相乘void ShowTMatrix(TSMatrix M)for(int col=1;col<=M.mu;col+)/通过双重循环，把稀疏矩阵中不为零的元素的行数、列数和值显不'出来for(int p=1;p<=M.tu;p+)if(M.datap.i=col)printf("%4d %4d %4dn”,M.datap.i,M.datap.j,M.datap.e);/三元组显示void TurnSMatrix_OL(CrossList &M)int col,row;/定义循环变量OLink p,q;/定义OLink结构类型变量for(co

30、l=1;col<=M.mu;col+) /通过循环，把非零元素的行数与列数进行交换，实现转置 q=p=M.rheadcol;while(q)row=p->i;p->i=p->j;p->j=row;q=p->right;p->right=p->down;p->down=q;/十字链表转置int SMatrix_ADD(CrossList *A,CrossList *B)OLNode *pa,*pb,*pre,*p,*cp100; / 定义 OLNode 类型的变量 int i,j,t; t=A->tu+B->tu;for(j=1;

31、j<=A->nu;j+)cpj=A->cheadj;/将 A 矩阵的列表头指针赋给c政组for(i=1;i<=A->mu;i+)pa=A->rheadi;pb=B->rheadi;/将A, B矩阵的行表头指针分别赋给pa, pbpre=NULL;while(pb)/当pb不等于零if(pa=NULL|pa->j>pb->j)p=(OLink)malloc(sizeof(OLNode);/ 给 p 动态分配空间 if(!pre)A->rheadi=p;else pre->right=p;p->right=pa;pre=

32、p;p->i=i;p->j=pb->j;p->e=pb->e;if(!A->cheadp->j)A->cheadp->j=cpp->j=p;p->down=NULL;/如果A->cheadp->j不等于零，则把p赋给它及cpp->jelsecpp->j->down=p;cpp->j=p;pb=pb->right;/否则把p赋给cpp->jelse if(pa->j<pb->j)pre=pa;pa=pa->right;else if(pa->e+pb-&

33、gt;e) t-;pa->e+=pb->e;pre=pa;pa=pa->right;pb=pb->right;else (t=t-2;if(!pre)A->rheadi=pa->right;else pre->right=pa->right;p=pa;pa=pa->right;if(A->cheadp->j=p)A->cheadp->j=cpp->j=p->down;else cpp->j->down=p->down;free(p);pb=pb->right;A->mu=A-

34、>mu>B->mu?A->mu:B->mu;A->nu=A->nu>B->nu?A->nu:B->nu;/A的行与列为 A及B当中较大的一个return 1;/十字链表相加int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q)(一int i, j, e;中间变量OLink p0, q0, p, pl, pla;中间变量if(M.nu != N.mu)/检查稀疏矩阵M的列数和N的行数是否对应相等(printf ("稀疏矩阵A的列数和B的行数不相等，不能

35、相乘。n");return 0;Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0;if(!(Q.rhead = (OLink *)malloc(Q.mu + 1) * sizeof(OLink) exit(-2);if(!(Q.chead = (OLink *)malloc(Q.nu + 1) * sizeof(OLink) exit(-2);for(i = 1; i <= Q.mu; i+) Q.rheadi = NULL;for(i = 1; i <= Q.nu; i+) Q.cheadi = NULL;/相乘for(i =1; i <= Q

36、.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->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->dow

37、n, p0 = p0->right;移动指针 if(e)乘积不为(if(!(p = (OLink)malloc(sizeof(OLNode) exit(-2);Q.tu+;/非零元素增加p->i = i, p->j = j, p->e = e, p->right = NULL, p->down = NULL;/ 赋值，指针后移 将p®入十字链表，行插入if(Q.rheadi = NULL)若p为该行的第个结点Q.rheadi = pl = p;/p插在该行的表头且pl指向p(该行的最后一个结点)else pl->right = p, pl =

38、 p;插在pl所指结点之后，pl右移列插入if(Q.cheadj = NULL)/若p为该列的第一个结点Q.cheadj = p;该列的表头指向pelse 插在列表尾pla = Q.cheadj;/pla指向j行的第个结点 while(pla->down) pla = pla->down;/pla 指向 j 行最后一个结点 pla->down = p; return 1;/十字链表相乘 int ShowMAtrix(CrossList *A)int col;OLink p;for(col=1;col<=A->mu;col+)if(A->rheadcol)p=

39、A->rheadcol;while(p)printf("%3d%3d%3dn”,p->i,p->j,p->e);p=p->right;return 1;/十字链表显示void main()int n,i;TSMatrix M,T,S;CrossList MM,TT,SS;printf(" *稀疏矩阵应用*");printf("n请你选择创建稀疏矩阵的方法：n1 ：用三元组创建稀疏矩阵n2:用十字链表创建稀疏矩 阵n3:退出程序");printf("n");scanf("%d",&