稀疏矩阵的存储实现

1、武汉理工大学数据结构课程设计说明书 课程设计任务书学生姓名： 宋吉松 专业班级： 软件1202班 指导教师： 李晓红 工作单位：计算机科学与技术学院 题 目: 稀疏矩阵的存储实现初始条件：理论：学习了数据结构课程，掌握了一种计算机高级语言。实践：计算机技术系实验中心提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）实现稀疏矩阵的三元组和十字链表两种存储结构（2）实现稀疏矩阵的基本运算（3）输出结果2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关

2、键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设计、算法设计、有关技术的讨论、设计体会等；（4）结束语；（5）参考文献。时间安排： 2013年12月16日-25日指导教师签名： 李晓红 2013年12月14日系主任（或责任教师）签名： 年 月 日摘 要 本课程设计在学习数据结构的前提下，运用c语言，对稀疏矩阵进行三元组存储和十字链表存储，并完成稀疏矩阵的转置，相加，相乘等基本运算。关键词 稀疏矩阵 三元组 十字链表 基本运算Abstract This course is designed on the premise of learning data structures usi

3、ng 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&

4、#160; 1.2稀疏矩阵转置. 2  1.3稀疏矩阵的相加相乘. 2  1.4输出结果 . 2 2 数据结构设计 2.1 三元组的结构体.2 2.2 十字链表的结构体. .3 3算法设计 3.1三元组 3.1.1三元组的创建. 3  3.1.2三元组的转置. 5  3.1.3三元组的相加. 5 3.1.4三元组的相乘. 8 3.1.5三元组的显示.10  3.2十字链表 3.2.1十字链表的创建.11  3.2.2

5、十字链表的显示. 12  3.3 主函数. 134 设计体会.165 结束语.16附1 参考文献.16附2 源代码.17附3 运行结果.382引言什么是稀疏矩阵？人们无法给出确切的定义，它只是一个凭人们的直觉来了解的概念。假设在m×n的矩阵中，有t个元素不为零。令q=t/(m×n),称q为矩阵的稀疏因子。通常认为q<=0.05时称为稀疏矩阵。按照压缩存储的概念，值存稀疏矩阵的非零元。因此，除了寻出非零元的值外，还必须同时记下它所在的行和列的位置。反之，一个三元组唯一确定了矩阵A的一个非零元。由此，稀疏矩阵可由表示非零元的三元组及其行列数唯

6、一确定。其存储方法有三种，分别是三元组顺序表，行逻辑链接的顺序表，十字链表。分别是以顺序存储结构，带行连接信息的三元组表，及链式存储结构进行存储表示。1需求分析1.1稀疏矩阵三元组表和十字链表两种存储的实现 三元组表的实现通过建立两个结构体，分别用来表示三元组的行数、列数、非零元数和元素的行、列坐标、值。然后通过for循环进行赋值。并求出每行含有的非零元个数。十字链表与三元组的不同在于用链表来存储每一行，每一列的元素信息。1.2稀疏矩阵的转置 稀疏矩阵的转置即将行列值进行调换，将元素的行列值进行调换，重排每个元素的次序。如何重排？三元组按照原矩阵M的列序进行转置。为了找到M的每个元素，要对三元

7、组表从第一行开始进行扫描，便可得到转置后矩阵的顺序。十字链表需要将元素的行指针和列指针调换。1.3稀疏矩阵的相加相乘 两个矩阵相加及每个元素分别对应相加。 两个矩阵的相乘M×N=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 rposMAXSIZ

8、E + 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 Creat

9、eSMatrix(TSMatrix &M) /采用三元组顺序表存储表示，创建稀疏矩阵M printf("请输入稀疏矩阵的行数 列数 非零元个数：n");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) /判断行值、列值、元素个数是否合法 printf("输入有误！"); for(int i=1;i<=M.tu;i+) /输入稀疏矩阵元素 printf(&quo

10、t;请输入请输入非零元的行坐标 列坐标 值:"); 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 <

11、= 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

12、=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+; /三元组转置3.1.3三元组的相加int Compare(int a1,int b1,int a2,int b2) /先建立Compare函数if(a1>a2)return 1; else if(a1<a2)return -1;else if(b1>b2)return 1;if(b1<b2)return -1;else

13、 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(Compare(M.datamcount.i,M.datamcount.j,T.d

14、atatcount.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.d

15、atamcount.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矩阵的非零值，行

16、数，列数进行赋值 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;/定义相乘函数中所需要用到的变量

17、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

18、 + 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 <= Q.nu; +ccol) /把运算后的结果存放到Q中 if(ctempccol)

19、 if(+(Q.tu) > 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.d

20、atap.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.chea

21、d=(OLink *)malloc(M.nu+1)*sizeof(OLNode) exit(1);/分配内存空间for( i=1;i<=M.mu;i+)M.rheadi=NULL; /把矩阵每个元素置空值for( i=1;i<=M.nu;i+)M.cheadi=NULL;printf("请输入非零元素的行坐标 列坐标 值：");scanf("%d%d%d",&i,&j,&e);while(i!=0)p=(OLink)malloc(sizeof(OLNode);p->i=i;p->j=j;p->e=e;

22、if(M.rheadi=NULL|M.rheadi->j>j)p->right=M.rheadi;M.rheadi=p;else q=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&&

23、q->down->i<i) q=q->down;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;col<=A->mu;col+)if(A->rheadcol)p=A->rheadcol; while(p)printf("%3d%3d%3dn",p->i,p

24、->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("您输入的稀

25、疏矩阵为：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); Ad

26、dTMatix(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&

27、quot;); 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)

28、; 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 :p

29、rintf("输入错误！");4 设计体会及结束语 通过设计本程序，加深了对矩阵存储的了解，掌握了稀疏矩阵三元组存储和十字链表存储两种存储方法。课本上介绍的较简略，有的地方甚至有个错误，经过不断检查才最终发现，发现课本上的不一定是对的，同样的问题也许有更好的方法。很多不懂的地方通过上网查资料，借鉴别人的设计经验，学习新的函数最终完成了本设计。通过这次课程设计，丰富了自己的专业知识，增强了自己解决问题的能力，有很大帮助。 完成这次设计要感谢指导老师李晓红老师，及室友们的帮助。附1 参考文献【1】数据结构（c语言版） 严蔚敏 吴伟民 清华大学出版社 2007【2】C程序设计教程

30、 张蕊 吕涛 华中科技大学出版社 2012.9【3】C+面向对象程序设计教程 第3版 陈维兴 林小茶 清华大学出版社 2009.6【4】百度文库 稀疏矩阵十字链表运算 附2 源代码#include<stdio.h>#include<stdlib.h>#define MAXSIZE 10000typedef struct OLNodeint i,j;int e; /十字链表每个元素的行坐标，列坐标，值struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu; /矩阵的行数，列数，非零元个数OL

31、ink *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("请输入稀

32、疏矩阵的行数 列数 非零元个数：n");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)/判断行值、列值、元素个数是否合法 printf("输入有误！"); for(int i=1;i<=M.tu;i+) /输入稀疏矩阵元素 printf("请输入请输入非零元的行坐标 列坐标 值:"); scanf("%d%d%d",&M.dat

33、ai.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.

34、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;p<=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.d

35、atap.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 if(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

36、; /对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(Compare(M.datamcount.i,M.datamcount.j,T.datatcount.i,T.datatcount.j) /用switch分支语句，用compare函数对需要相加的两个矩阵的某元素行数列数进行比较 case -1: S.dataq.e=M.datamcoun

37、t.e;/当M.datamcount.i<T.datatcount.i或M.datamcount.j<T.datatcount.j S.dataq.i=M.datamcount.i; S.dataq.j=M.datamcount.j;/把第一个矩阵的行数i，列数j赋值给S矩阵的行数i，列数j q+; mcount+; break;Case 1: S.dataq.e=T.datatcount.e;/当M.datamcount.i>T.datatcount.i或M.datamcount.j>T.datatcount.j S.dataq.i=T.datatcount.i; S

38、.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

39、.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, TSM

40、atrix &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

41、.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.

42、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; return 1;/三元组相乘void ShowTMatrix(TSMatrix M)for(int col=1;col<=M.mu;col+)/通过双重循环，把稀疏矩阵中不为零的元素的行数、列数和值显示出来for(int p=1

43、;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 *)ma

44、lloc(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(t<=M.tu)printf("请输入非零元素的行坐标 列坐标 值：");scanf("%d%d%d",&i,&j,&e);p=(OLink)malloc(sizeof(

45、OLNode);p->i=i;p->j=j;p->e=e;if(M.rheadi=NULL|M.rheadi->j>j)p->right=M.rheadi;M.rheadi=p;else q=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;els

46、eq=M.cheadj;while(q->down&&q->down->i<i) q=q->down;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;j<=M.nu;i+)T.rheadi->i=M.cheadi->j;T.rheadi->j=M.cheadi->i;T.rheadi->e=M.cheadi->e;*/十字链表转置int SMatrix_ADD(CrossList *A,CrossList *B)OLNode *pa,