稀疏矩阵的存储实现

课程设计任务书学生姓名： 宋吉松 专业班级： 软件1202班 指引教师： 李晓红 工作单位：计算机科学与技术学院 题 目: 稀疏矩阵的存储实现初始条件：理论：学习了数据构造课程，掌握了一种计算机高档语言。实践：计算机技术系实验中心提供计算机及软件开发环境。规定完毕的重要任务: （涉及课程设计工作量及其技术规定，以及阐明书撰写等具体规定）1、系统应具有的功能：（1）实现稀疏矩阵的三元组和十字链表两种存储构造（2）实现稀疏矩阵的基本运算（3）输出成果2、数据构造设计；3、重要算法设计；4、编程及上机实现；5、撰写课程设计报告，涉及：（1）设计题目；（2）摘要和核心字（中文和英文）；（3）正文，涉及引言、需求分析、数据构造设计、算法设计、有关技术的讨论、设计体会等；（4）结束语；（5）参照文献。时间安排： 12月16日-25日指引教师签名： 李晓红 12月14日系主任（或责任教师）签名： 年 月 日摘 要 本课程设计在学习数据构造的前提下，运用c语言，对稀疏矩阵进行三元组存储和十字链表存储，并完毕稀疏矩阵的转置，相加，相乘等基本运算。核心词 稀疏矩阵 三元组 十字链表 基本运算Abstract This course is designed on the premise of learning data structures using c language, for sparse matrix triple store to store and cross-linked, and were achieved under the two storage sparse matrix transpose, add, multiply, and other basic operations.Keywords sparse matrix triples Crusaders basic operations目录引言.11 需求分析 1.1稀疏矩阵三元组表和十字链表两种存储的实现.2 1.2稀疏矩阵转置.2 1.3稀疏矩阵的相加相乘.2 1.4输出成果.22 数据构造设计 2.1 三元组的构造体.2 2.2 十字链表的构造体.33算法设计 3.1三元组 3.1.1三元组的创立.3 3.1.2三元组的转置.5 3.1.3三元组的相加.5 3.1.4三元组的相乘.83.1.5三元组的显示.10 3.2十字链表 3.2.1十字链表的创立.11 3.2.2十字链表的显示.12 3.3 主函数.134 设计体会.165 结束语.16附1 参照文献.16附2 源代码.17附3 运营成果.38引言什么是稀疏矩阵？人们无法给出确切的定义，它只是一种凭人们的直觉来理解的概念。假设在mn的矩阵中，有t个元素不为零。令q=t/(mn),称q为矩阵的稀疏因子。一般觉得q=0.05时称为稀疏矩阵。按照压缩存储的概念，值存稀疏矩阵的非零元。因此，除了寻出非零元的值外，还必须同步记下它所在的行和列的位置。反之，一种三元组唯一拟定了矩阵A的一种非零元。由此，稀疏矩阵可由表达非零元的三元组及其行列数唯一拟定。其存储措施有三种，分别是三元组顺序表，行逻辑链接的顺序表，十字链表。分别是以顺序存储构造，带行连接信息的三元组表，及链式存储构造进行存储表达。1需求分析1.1稀疏矩阵三元组表和十字链表两种存储的实现 三元组表的实现通过建立两个构造体，分别用来表达三元组的行数、列数、非零元数和元素的行、列坐标、值。然后通过for循环进行赋值。并求出每行具有的非零元个数。十字链表与三元组的不同在于用链表来存储每一行，每一列的元素信息。1.2稀疏矩阵的转置 稀疏矩阵的转置即将行列值进行调换，将元素的行列值进行调换，重排每个元素的顺序。如何重排？三元组按照原矩阵M的列序进行转置。为了找到M的每个元素，要对三元组表从第一行开始进行扫描，便可得到转置后矩阵的顺序。十字链表需要将元素的行指针和列指针调换。1.3稀疏矩阵的相加相乘 两个矩阵相加及每个元素分别相应相加。 两个矩阵的相乘MN=S，即M的行元素与N的列元素分别相应乘积的累加，得到的即为S以M的行，N的列为坐标的元素的值。1.4输出成果 可以用for或while循环，输出两种表达下的稀疏矩阵。2 数据构造设计2.1 三元组的构造体typedef structint i,j; /三元组每个元素的行坐标，列坐标，值int e;Triple;typedef structTriple dataMAXSIZE+1; int rposMAXSIZE + 1; /三元组各行第一种元素的位置int mu,nu,tu; /三元组矩阵的行数，列数，非零元个数TSMatrix; /三元组构造体定义；2.2 十字链表的构造体typedef struct OLNodeint i,j;int e; /十字链表每个元素的行坐标，列坐标，值struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu; /矩阵的行数，列数，非零元个数OLink *rhead,*chead; /行和列头指针CrossList; /十字链表构造体定义3算法设计3.1.1三元组的创立void CreateSMatrix(TSMatrix &M) /采用三元组顺序表存储表达，创立稀疏矩阵M printf(请输入稀疏矩阵的行数 列数 非零元个数：n);scanf(%d%d%d,&M.mu,&M.nu,&M.tu);if(M.mu=0)|(M.nu=0)|(M.tuM.mu*M.nu) /判断行值、列值、元素个数与否合法 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,&M.datai.e); /if /for int 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中每一行含非零元素个数 /求rpos M.rpos1 = 1; for(i = 2; i = M.mu; i+) M.rposi = M.rposi-1 + numi-1; /创立三元组3.1.2三元组的转置void TransposeSMatrix(TSMatrix M,TSMatrix &T)T.nu=M.mu; /通过三元组表达，将M转置为TT.mu=M.nu;T.tu=M.tu;int q=1;for(int col=1;col=M.nu;col+)for(int p=1;pa2)return 1; else if(a1b2)return 1;if(b1T.mu?M.mu:T.mu; /对S矩阵的行数赋值 S.nu=M.nuT.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(Compare(M.datamcount.i,M.datamcount.j,T.datatcount.i,T.datatcount.j) /用switch分支语句，用compare函数对需要相加的两个矩阵的某元素行数列数进行比较 case -1: S.dataq.e=M.datamcount.e; S.dataq.i=M.datamcount.i;S.dataq.j=M.datamcount.j; q+; mcount+; break; case 1: S.dataq.e=T.datatcount.e; S.dataq.i=T.datatcount.i; S.dataq.j=T.datatcount.j; q+; tcount+; break; case 0: ce=M.datamcount.e+T.datatcount.e;/其她状况下把两个矩阵的值相加 if(ce) S.dataq.e=ce; S.dataq.i=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;S.dataq.j=T.datatcount.j; q+; tcount+; /在case=1的状况下对S矩阵的非零值，行数，列数进行赋值 S.tu=q-1;/三元组相加3.1.4三元组的相乘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寄存相乘后的成果 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.mu) 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 MAXSIZE) return 1; Q.dataQ.tu.i = arow, Q.dataQ.tu.j = ccol, Q.dataQ.tu.e = ctempccol; return 1;/三元组相乘3.1.5三元组的显示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);/三元组显示3.2.1十字链表的创立void CreateSMatix_OL(CrossList &M) int i,j,e; OLink p,q;printf(请输入稀疏矩阵的行数 列数 非零元素的个数:n); /矩阵行数，列数下标均从开始；scanf(%d%d%d,&M.mu,&M.nu,&M.tu);if(!(M.rhead=(OLink *)malloc(M.mu+1)*sizeof(OLNode) exit(1);/分派内存空间if(!(M.chead=(OLink *)malloc(M.nu+1)*sizeof(OLNode) exit(1);/分派内存空间for( i=1;i=M.mu;i+)M.rheadi=NULL; /把矩阵每个元素置空值for( i=1;ii=i;p-j=j;p-e=e;if(M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p;else q=M.rheadi; while(q-right&q-right-jright; p-right=q-right; q-right=p;if(M.cheadj=NULL|M.cheadj-ii)p-down=M.cheadj;M.cheadj=p;elseq=M.cheadj;while(q-down&q-down-idown;p-down=q-down;q-down=p;scanf(%d%d%d,&i,&j,&e); /创立十字链表3.2.2十字链表的显示int ShowMAtrix(CrossList *A) int col; OLink p; for(col=1;colmu;col+)if(A-rheadcol)p=A-rheadcol; while(p)printf(%3d%3d%3dn,p-i,p-j,p-e);p=p-right; return 1; /十字链表显示3.3 主函数/主函数void main()int n,i;TSMatrix M,T,S;CrossList MM,TT,SS;printf(*稀疏矩阵的应用*n);printf(n1：用三元组创立稀疏矩阵n2:用十字链表创立稀疏矩阵n3:退出程序);printf(n);scanf(%d,&n);switch(n)case 1:CreateSMatrix(M);printf(您输入的稀疏矩阵为：n 行 列 大小n);ShowTMatrix(M);printf(已经选择三元组创立稀疏矩阵,请继续选择：n1：稀疏矩阵转置n2：稀疏矩阵相加n3：稀疏矩阵相乘n4：退出程序n);scanf(%d,&i);switch(i)case 1:TransposeSMatrix(M,T);printf(转置后的矩阵为：n 行 列 大小n);ShowTMatrix(T);break;case 2:printf(请你输入另一种稀疏矩阵:); CreateSMatrix(T); AddTMatix(M,T,S);printf(相加后的矩阵为 ：n 行 列 大小n); ShowTMatrix(S);break;case 3:printf(请你输入另一种稀疏矩阵:); CreateSMatrix(T); MultSMatrix(M,T,S); printf(相乘后的矩阵为 ：n 行 列 大小n); ShowTMatrix(S); break;case 4:exit(0);break;case 2:CreateSMatix_OL(MM); printf(您输入的稀疏矩阵为 ：n 行 列 大小n); ShowMAtrix(&MM); printf(已经选择十字链表创立稀疏矩阵，请选择操作:n1：稀疏矩阵转置n2：稀疏矩阵相加n3：稀疏矩阵相乘n4：退出程序n);scanf(%d,&i);switch(i)case 1: TurnSMatrix_OL(MM); printf(转置后的矩阵为 ：n 行 列 大小n); ShowMAtrix(&MM); break;case 2: printf(请你输入另一种稀疏矩阵:); CreateSMatix_OL(TT); SMatrix_ADD(&MM,&TT); printf(相加后的矩阵为 ：n 行 列 大小n); ShowMAtrix(&MM);break;case 3:printf(请你输入另一种稀疏矩阵:); CreateSMatix_OL(TT); MultSMatrix_OL(MM,TT,SS); printf(相乘后的矩阵为 ：n 行 列 大小n); ShowMAtrix(&SS);break;case 4:exit(0); ;break;case 3:exit(0);default :printf(输入错误！);4 设计体会及结束语 通过设计本程序，加深了对矩阵存储的理解，掌握了稀疏矩阵三元组存储和十字链表存储两种存储措施。课本上简介的较简略，有的地方甚至有个错误，通过不断检查才最后发现，发现课本上的不一定是对的，同样的问题也许有更好的措施。诸多不懂的地方通过上网查资料，借鉴别人的设计经验，学习新的函数最后完毕了本设计。通过这次课程设计，丰富了自己的专业知识，增强了自己解决问题的能力，有很大协助。 完毕这次设计要感谢指引教师李晓红教师，及室友们的协助。附1 参照文献【1】数据构造（c语言版） 严蔚敏 吴伟民 清华大学出版社 【2】C程序设计教程 张蕊 吕涛 华中科技大学出版社 .9【3】C+面向对象程序设计教程 第3版 陈维兴 林小茶 清华大学出版社 .6【4】百度文库 稀疏矩阵十字链表运算 附2 源代码#include#include#define MAXSIZE 10000typedef 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+1; int rposMAXSIZE + 1; /三元组各行第一种元素的位置int mu,nu,tu; /三元组矩阵的行数，列数，非零元个数TSMatrix; /三元组构造体定义；void CreateSMatrix(TSMatrix &M) /采用三元组顺序表存储表达，创立稀疏矩阵M printf(请输入稀疏矩阵的行数 列数 非零元个数：n);scanf(%d%d%d,&M.mu,&M.nu,&M.tu);if(M.mu=0)|(M.nu=0)|(M.tuM.mu*M.nu)/判断行值、列值、元素个数与否合法 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,&M.datai.e); /if /for int 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中每一行含非零元素个数 /求rpos M.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; /通过三元组表达，将M转置为TT.mu=M.nu;T.tu=M.tu;int q=1;for(int col=1;col=M.nu;col+)for(int p=1;pa2)return 1;else if(a1b2)return 1;if(b1T.mu?M.mu:T.mu; /对S矩阵的行数赋值 S.nu=M.nuT.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(Compare(M.datamcount.i,M.datamcount.j,T.datatcount.i,T.datatcount.j) /用switch分支语句，用compare函数对需要相加的两个矩阵的某元素行数列数进行比较 case -1: S.dataq.e=M.datamcount.e;/当M.datamcount.iT.datatcount.i或M.datamcount.jT.datatcount.i或M.datamcount.jT.datatcount.j S.dataq.i=T.datatcount.i; S.dataq.j=T.datatcount.j;/把第二个矩阵的行数i，列数j赋值给S矩阵的行数i，列数j q+; tcount+; break; case 0: ce=M.datamcount.e+T.datatcount.e;/其她状况下把两个矩阵的值相加 if(ce) S.dataq.e=ce; S.dataq.i=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; 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寄存相乘后的成果 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.mu) 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 MAXSIZE) return 1; Q.dataQ.tu.i = arow, Q.dataQ.tu.j = ccol, Q.dataQ.tu.e = ctempccol; return 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 CreateSMatix_OL(CrossList &M) int i,j,e,t=1; OLink p,q;printf(请输入稀疏矩阵的行数 列数 非零元素的个数:n); /矩阵行数，列数下标均从开始；scanf(%d%d%d,&M.mu,&M.nu,&M.tu);M.rhead=(OLink *)malloc(M.mu+1)*sizeof(OLink); /分派内存空间M.chead=(OLink *)malloc(M.nu+1)*sizeof(OLink);/分派内存空间for( i=1;i=M.mu;i+)M.rheadi=NULL; /把矩阵每个元素置空值for( i=1;i=M.nu;i+)M.cheadi=NULL;while(ti=i;p-j=j;p-e=e;if(M.rheadi=NULL|M.rheadi-jj)p-right=M.rheadi;M.rheadi=p;else q=M.rheadi; while(q-right&q-right-jright; p-right=q-right; q-right=p;if(M.cheadj=NULL|M.cheadj-ii)p-down=M.cheadj;M.cheadj=p;elseq=M.cheadj;while(q-down&q-down-idown;p-down=q-down;q-down=p;t+; /创立十字链表void TurnSMatrix_OL(CrossList M,CrossList &T)/*int i,j; T.nu=M.mu; T.mu=M.nu;T.tu=M.tu;T.rhead=(OLink *)malloc(T.mu+1)*sizeof(OLink); /分派内存空间T.chead=(OLink *)malloc(T.nu+1)*sizeof(OLink);/分派内存空间for(int i=1;i=T.mu;i+) T.rheadi=NULL;for(int j=1;j=T.nu;j+) T.cheadj=NULL; for(j=1;i=M.mu;j+) for(i=1;ji=M.cheadi-j;T.rheadi-j=M.cheadi-i;T.rheadi-e=M.cheadi-e;*/十字链表转置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;jnu;j+)cpj=A-cheadj;/将A矩阵的列表头指针赋给cp数组for(i=1;imu;i+)pa=A-rheadi; pb=B-rheadi; /将A，B矩阵的行表头指针分别赋给pa，pbpre=NULL;while(pb)/当pb不等于零 if(pa=NULL|pa-jpb-j)p=(OLink)malloc(sizeof(OLNode);/给p动态分派空间if(!pre)A-rheadi=p;else pre-right=p;p-right=pa;pre=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-jj)pre=pa; pa=pa-right; else if(pa-e+pb-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-muB-mu?A-mu:B-mu;A-nu=A-nuB-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的行数不相等，不能相乘。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.mu; i+)