用十字链表和一般方法分别实现稀疏矩阵的乘法和加法

1、#include<stdio.h>#include<malloc.h>#define Size 2501# define Size1 51typedef structint i;int j;int e;/非零元的值triple; /定义三元组typedef structtriple dataSize+1;/矩阵中的元素int ropsSize1+1;/ ropsi为第i行元素中的首非零元在data中的序号int mu;/行数int nu;/列数int tu;/非零元数 juzhen;/定义矩阵typedef struct node/ 定义十字链表元素int i,j,e;

2、 struct node *right,*down;/ 该非零元所在行表和列表的后继元素 node,*link;typedef struct / 定义十字链表对象结构体 link *rhead,*chead;/行和列的头指针int m,n,t;/ 系数矩阵的行数，列数，和非零元素个数 crosslist;void createcross(crosslist &M)/建立十字链表int i,j,e,k;node *p,*q;printf("输入行，列和非零元数，空格隔开：n");scanf("%d %d %d",&M.m,&M.n,

3、&M.t);M.rhead=(link *)malloc(M.m+1)*sizeof(link);/给行和列的头指针分配内存 M.chead=(link *)malloc(M.n+1)*sizeof(link);for(k=1;k<=M.m;k+)/初始化行，列的头指针M.rheadk=NULL;for(k=1;k<=M.n;k+)M.cheadk=NULL;printf("输入非零元的行，列和值，空格隔开：n");for(k=1;k<=M.t;k+)/输入非零元scanf("%d %d %d",&i,&j,&a

4、mp;e);p=(node *)malloc(sizeof(node);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 for(q=M.rheadi;(q->right)&&q->right->j<j;q=q->right);/空循环找到第一个列标大于或等于插入元素列标的元素p->right=q->right;q->

5、right=p;if(M.cheadj=NULL|(M.cheadj->i>i)/插入元素所在列无非零元或首非零元的行标大于插入元素的行标p->down=M.cheadj;M.cheadj=p;elsefor(q=M.cheadj;(q->down)&&q->down->i<i;q=q->down);/空循环找到第一个行标大于或等于插入元素行标的元素p->down=q->down;q->down=p;void printcross(crosslist A)/输出十字链表if(A.m=0)printf("

6、十字链表为空!n");elseprintf("十字链表为:n");int i,j;for(i=1;i<=A.m;i+) link p=A.rheadi; for(j=1;j<=A.n;j+)if(p)&&(j=p->j) printf("%5d",p->e);p=p->right; elseprintf("%5d",0); printf("n");printf("n");crosslist addcross()printf("十字

7、链表加法:n");crosslist a,b;/ 创建两个十字链表对象，并初始化createcross(a);createcross(b);node *pre,*h51,*pa,*pb,*q;/定义辅助指针，pa，pb分别为a,b当前比较的元素，pre为pa的前驱元素 int i,j,k=0,m,n; /hj指向j列的当前插入位置 if(a.m!=b.m|a.n!=b.n)printf("格式不对，不能相加!n");elsefor(i=1;i<=a.m;i+) pa=a.rheadi;pb=b.rheadi;pre=NULL;for(j=1;j<=a.

8、n;j+) hj=NULL;while(pb)link p;p=(node *)malloc(sizeof(node); / 开辟新节点，存储b中取出的元素 p->i=pb->i;p->j=pb->j;p->e=pb->e;if(pa=NULL|pa->j>pb->j)/当a此行已经检查完或者pb因该放在pa前面if (pre=NULL)a. rheadp->i=p;else pre->right=p;p->right=pa;pre=p;if (hp->j=NULL)/当前插入位置下面无非零元/因为是逐行处理，so,

9、hp->j，依次下移/因此每次都是指向插入的位置 a. chead p->j= p; p->down = NULL;else p->down = hp->j->down;hp->j->down = p;hp->j=p;/*hp->j下移指向下次插入的位置pb=pb->right;/pb指向该行下个元素else if(pa&&pa->j<pb->j)/只要移动pa的指针*先不加|(pb=NULL&&pa)pre = pa;hpa->j=pa;/移动h，使其指向下次插入的位置p

10、a = pa->right;else if(pa->j=pb->j)pa->e+=pb->e;if(pa->e)/不为零pre=pa;hpa->j=pa;pb=pb->right;/加else/pa->e为零，删除节点if (pre =NULL)a.rhead pa->i=pa->right;else pre->right=pa->right;p=pa;/p指向pa，用来在下面修改列指针pa=pa->right;if (h p->j=NULL) a.chead p->j=p->down;els

11、e hp->j->down=p->down;free(p);pb=pb->right;return a;void multycross(crosslist &c)/十字链表乘法node *p,*q,*u,*v,*p1,*p2;crosslist a,b;link *r;int i,j,k,e;printf("十字链表乘法:n");createcross(a);createcross(b);if(a.n!=b.m)printf("格式错误，不能相乘！n");else c.m=a.m;c.n=b.n;c.t=0;c.rhead

12、=(link *)malloc(a.m+1)*sizeof(link);/给行和列的头指针分配内存c.chead=(link *)malloc(b.n+1)*sizeof(link);for(k=1;k<=a.m;k+)/初始化行，列的头指针c.rheadk=NULL;for(k=1;k<=b.n;k+)c.cheadk=NULL;r=(link *)malloc(b.n+1)*sizeof(link);for(i=1;i<=a.m;i+)u=(node *)malloc(sizeof(node);u->e=0;u->i=0;u->j=0;for(k=1;k

13、<=b.n;k+)/初始化rrk=u;p1=p=a.rheadi;for(j=1;j<=b.n;j+) p=p1;q=b.cheadj;v=(node *)malloc(sizeof(node);/初始化v，v为将插入c矩阵的元素v->e=0;v->i=i;v->j=j;while(p&&q)if(p->j>q->i)q=q->down;else if(p->j<q->i)p=p->right;elsev->e+=p->e*q->e;p=p->right;q=q->dow

14、n;if(v->e)/如果不为零，则插入c矩阵中/同建立十字链表if(c.rheadi=NULL|c.rheadi->j>j)/插入元素所在行无非零元或首非零元的列标大于插入元素的列标v->right=c.rheadi;c.rheadi=v;else for(p2=c.rheadi;(p2->right)&&(p2->right->j<j);p2=p2->right);/空循环找到第一个列标大于或等于插入元素列标的元素v->right=p2->right;p2->right=v;if(c.cheadj=NU

15、LL|c.cheadj->i>i)/插入元素所在列无非零元或首非零元的行标大于插入元素的行标v->down=c.cheadj;c.cheadj=v;elsefor(p2=c.cheadj;(p2->down)&&(p2->down->i<i);p2=p2->down);/空循环找到第一个行标大于或等于插入元素行标的元素v->down=p2->down;p2->down=v;void create(juzhen & M) /创建稀疏矩阵int i,t=0;printf("输入矩阵行数和列数and非

16、零元的个数，以空格隔开:n");scanf("%d %d %d",&M.mu,&M.nu,&M.tu);printf("输入矩阵非零元的行，列，和数值(中间空格隔开):n");for(i=1;i<=M.tu;i+)scanf("%d %d %d",&M.datai.i,&M.datai.j,&M.datai.e); /输入三元组的元素for(i=1;i<=Size1;i+)/初始化rops【】M.ropsi=0;for(i=1,t=1;i<=M.mu;i+)/

17、得到各行第一个元素的序号M.ropsi=t;while(M.datat.i<=i&&t<=M.tu)/遇到i行非零元，则t累加t+;void add(juzhen A,juzhen B,juzhen & C)/稀疏矩阵加法int k=1,temp=0,k1=1, k2=1;/k1,k2,k分别控制A，B，C中非零元的序号变化printf("稀疏矩阵加法:n");create(A);create(B);if(A.mu!=B.mu|A.nu!=B.nu)printf("格式不对，不能相加!n");elsewhile(k1&

18、lt;=A.tu&&k2<=B.tu)/当A，B中的非零元都没用完if(A.datak1.i<B.datak2.i)/A当前k1指向的元素的行标小于列标直接把data【k1】的值赋给c中data【k】C.datak+=A.datak1+;else if(A.datak1.i>B.datak2.i)/同上C.datak+=B.datak2+;else/datak1,datak2行标相同if(A.datak1.j>B.datak2.j)/datak1列标大于datak2列标，则把datak2的值赋给datakC.datak+=B.datak2+;else i

19、f(A.datak1.j<B.datak2.j)/同上C.datak+=A.datak1+;else /行，列标都相同temp=0;temp=A.datak1.e+B.datak2.e;if(temp)/相加后不为零C.datak.i=A.datak1.i;C.datak.j=A.datak1.j;C.datak.e=temp;k+;k1+;k2+; while(k1<=A.tu)/B中非零元已用完，A中还有非零元C.datak+=A.datak1+;while(k2<=B.tu)/A中非零元已用完，B中还有非零元C.datak+=B.datak2+;C.mu=A.mu;/确

20、定C的行列数和非零元个数C.nu=A.nu;C.tu=k-1; void print(juzhen A)/输出稀疏矩阵printf("n矩阵为:n");int i,j,k=1;if(A.mu=0)printf("矩阵为空！n");else if(A.tu=0)/矩阵元素为空printf("零矩阵！n");else for(i=1;i<=A.mu;i+)/逐行输出for(j=1;j<=A.nu;j+) if(A.datak.i=i&&A.datak.j=j)/行和列分别对应相等则输出相应非零元，否则输出零pr

21、intf("%5d",A.datak+.e);else printf("%5d",0);printf("n");/该行输出结束，空行输出下一行printf("n");void multy(juzhen A,juzhen B,juzhen &C)/稀疏矩阵乘法int arow,brow,ccol,temp51,p,q,t,tp,i;/各变量代表含义见下面printf("稀疏矩阵乘法:n");create(A);create(B);if(A.nu!=B.mu)printf("格式错

22、误，不能相乘！n");elseC.mu=A.mu;/初始化c的行列及非零元个数C.nu=B.nu;C.tu=0;if(A.nu!=B.mu)printf("A,B格式不对不能相乘!n");else /for(arow=1;arow<=A.mu;arow+)/arow为当前A矩阵的行标for(i=0;i<51;i+)/初始化temptempi=0;if(arow<A.mu)tp=A.ropsarow+1;/tp为arow+1行的首非零元在data【】中的序号else /arow为最后一行tp=A.tu+1;for(p=A.ropsarow;p<

23、;tp;p+)/p为A中当前元素在data中的序号brow=A.datap.j;/brow为 与B矩阵中的相应行对应的 A中当前元素的列标if(brow<B.mu)t=B.ropsbrow+1;/t为brow+1行的首非零元在B中data【】中的序号else /brow大小等于B.mut=B.tu+1;for(q=B.ropsbrow;q<t;q+)/q为B中当前元素在B.data中的序号ccol=B.dataq.j;/ccol：datap*dataq所得结果所在的列tempccol+=A.datap.e*B.dataq.e;/temp【ccol】：相乘所得的C矩阵中第arow行c

24、ool列元素的值for(ccol=1;ccol<=B.nu;ccol+)/if(tempccol)/temp【ccol】不为零，则把值赋到c中，c.tu加1。C.data+C.tu.e=tempccol;C.dataC.tu.i=arow;C.dataC.tu.j=ccol;void clear(juzhen & A)/清空稀疏矩阵int i; A.mu=0;A.nu=0;A.tu=0; for(i=0;i<Size1+1;i+)A.ropsi=0;for(i=0;i<Size+1;i+)A.datai.i=0;A.datai.j=0;A.datai.e=0;void

25、 main()juzhen A,B,C,D;crosslist a,b,c,d;lable: printf("*n"); printf("请选择：1、稀疏矩阵的加法，并输出结果，2、稀疏矩阵乘法，并输出结果n"); printf("n3、十字链表加法,并输出，4、十字链表乘法并输出，5、结束：n"); printf("*n"); int x; scanf("%d",&x); switch(x) case 1: add(A,B,C); print(C); printf("n&qu

26、ot;); goto lable; case 2: multy(A,B,C); print(C); printf("n"); goto lable; case 3: a=addcross(); printcross(a); printf("n"); goto lable; case 4: multycross(b); printcross(b); printf("n"); goto lable; case 5: break; printf("n"); /*乘法测试数据：矩阵原型：4 -3 0 0 1 3 0 0 2

27、4 -6 00 0 0 8 0 * -4 2 0 8 0 00 0 1 0 0 0 1 0 = 0 1 00 0 0 0 70 1 0 0 0 0 00 0 0 4 5 6 1 1 4 1 2 -3 1 5 1 2 4 8 3 3 1 4 5 70 5 3 5 1 1 3 2 1 -4 2 2 2 3 2 1 4 1 1 4 5 201 1 11 2 11 3 11 4 11 5 12 1 12 2 12 3 12 4 12 513 1 13 2 13 3 13 4 13 5 14 1 14 2 14 3 14 4 14 5 15 3 151 1 -21 2 -21 3 -22 1 -22 2

28、 -22 3 -23 1 -23 2 -23 3 -24 1 -24 2 -24 3 -25 1 -25 2 -25 3 -2 矩阵加法：原型：4 0 0 -8 0 0 0 0 1 4 0 -70 0 9 0 0 1 10 0 8 -6 0 00 -3 7 6 0 -2 + 1 0 0 0 0 0 = 1 5 0 0 0 0 0 3 0 0 0 0-4 0 0 -2 0 9 0 0 0 -1 0 0 4 0 1 -4 0 -7 10 0 17 -6 0 1 1 -3 7 6 0 -2 1 8 0 0 0 0 -4 0 0 -3 0 9 5 6 13 1 1 4 1 4 -8 2 3 9 2 6

29、 1 3 2 -3 3 3 7 3 4 6 3 6 -2 4 1 1 4 2 5 5 1 -4 5 4 -2 5 6 9 5 6 9 1 3 1 1 4 4 1 6 -7 2 1 10 2 3 8 2 4 -6 3 1 1 4 2 3 5 4 -1 */一、 需求分析1、 分别用一般方法和和十字链表法，存储稀疏矩阵，并实现矩阵的加法和乘法运算。用一般方法时，用M.ropsi保存矩阵M中第i行的首非零元在矩阵所有非零元中的顺序，并用M.data保存矩阵M的非零元，矩阵最多有2500个非零元，最大有50行。用十字链表法时，用right和down分别指示非零元的行后继和列后继元素，rhead和che

30、ad分别指向行表和列表的头，头结点都没有用到。2、 演示程序程序以用户和计算机的对话方式进行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。3、 程序执行的命令包括：请选择：1、稀疏矩阵的加法，并输出结果，2、稀疏矩阵乘法，并输出结果十字链表加法,并输出，4、十字链表乘法并输出，5、结束：4、 测试数据（1）、乘法矩阵原型：4 -3 0 0 1 3 0 0 24 -6 00 0 0 8 0 * -4 2 0 8 0 00 0 1 0 0 0 1 0 = 0 1 00 0 0 0 70 1 0 0 0 0 0 4 5 6 1 1

31、 4 1 2 -3 1 5 1 2 4 8 3 3 1 4 5 70 5 3 5 1 1 3 2 1 -4 2 2 2 3 2 1 4 1 1 （2）、加法矩阵原型：4 0 0 -8 0 0 0 0 1 4 0 -70 0 9 0 0 1 10 0 8 -6 0 00 -3 7 6 0 -2 + 1 0 0 0 0 0 = 1 5 0 0 0 0 0 3 0 0 0 0-4 0 0 -2 0 9 0 0 0 -1 0 04 0 1 -4 0 -7 10 0 17 -6 0 1 1 -3 7 6 0 -2 1 8 0 0 0 0 -4 0 0 -3 0 95 6 13 1 1 4 1 4 -8

32、2 3 9 2 6 1 3 2 -3 3 3 7 3 4 6 3 6 -2 4 1 1 4 2 5 5 1 -4 5 4 -2 5 6 9 5 6 9 1 3 1 1 4 4 1 6 -7 2 1 10 2 3 8 2 4 -6 3 1 1 4 2 3 5 4 -1二、概要设计1.稀疏矩阵的抽象数据类型定义为：ADT juzhen 数据对象：D= m，n，t，data |m，n，t，data 属于 Elemset 数据关系：R=<m，n>，<n，t>，<data，t> 基本操作：Create（juzhen M）操作结果：构造了矩阵M。Add（juzhen A

33、，juzhen B，juzhen &C）初始条件：矩阵A，B已存在。操作结果：使A，B矩阵相加并把结果赋到C矩阵。Multy（juzhen A，juzhen B，juzhen &C）初始条件：矩阵A，B已存在。操作结果：使A，B矩阵相乘并把结果赋到C矩阵。Print(juzhen A)初始条件：矩阵A已存在。操作结果：输出稀疏矩阵A。ADT juzhen2、十字链表的抽象数据类型定义为：ADT crosslist 数据对象：rhead，chead，m，n，t | rhead，chead，m，n，t 属于Elementset数据关系：R1=基本操作：Createcross（cro

34、sslist &M）创建十字链表矩阵M。Addcross（）操作结果：创建两个十字链表a，b，使a+b的值赋给a，并返回a。Multycross（crosslist &c）操作结果：创建两个十字链表a，b，使a*b的值赋给c。 Printcross（crosslist A） 初始条件：矩阵A已经存在。 操作结果：输出十字链表。ADT crosslist3、本程序包括三个模块（1）、主程序模块Void main（） Switch（）（2）、稀疏矩阵模块-实现稀疏矩阵的加法，乘法，及输出操作（3）、十字链表模块-实现稀疏矩阵的加法，乘法，及输出操作三、详细设计1、三元组类型type

35、def structint i;int j;int e;/非零元的值triple; /定义三元组2、稀疏矩阵类型typedef structtriple dataSize+1;/矩阵中的元素int ropsSize1+1;/ ropsi为第i行元素中的首非零元在data中的序号int mu;/行数int nu;/列数int tu;/非零元数 juzhen;/定义矩阵3、结点类型typedef struct nodeint i,j,e; struct node *right,*down;/ 该非零元所在行表和列表的后继元素 node,*link;4、十字链表类型typedef struct /

36、定义十字链表对象结构体 link *rhead,*chead;/行和列的头指针int m,n,t;/ 系数矩阵的行数，列数，和非零元素个数 crosslist;其中部分操作的算法：void printcross(crosslist A)/输出十字链表printf("十字链表为:n");int i,j;for(i=1;i<=A.m;i+) link p=A.rheadi; for(j=1;j<=A.n;j+)if(p)&&(j=p->j) printf("%5d",p->e);p=p->right; elsep

37、rintf("%5d",0); printf("n");printf("n");crosslist addcross()printf("十字链表加法:n");crosslist a,b;/ 创建两个十字链表对象，并初始化createcross(a);createcross(b);node *pre,*h51,*pa,*pb,*q;/定义辅助指针，pa，pb分别为a,b当前比较的元素，pre为pa的前驱元素 int i,j,k=0,m,n; /hj指向j列的当前插入位置 if(a.m!=b.m|a.n!=b.n)pr

38、intf("格式不对，不能相加!n");elsefor(i=1;i<=a.m;i+) pa=a.rheadi;pb=b.rheadi;pre=NULL;for(j=1;j<=a.n;j+) hj=NULL;while(pb)link p;p=(node *)malloc(sizeof(node); / 开辟新节点，存储b中取出的元素 p->i=pb->i;p->j=pb->j;p->e=pb->e;if(pa=NULL|pa->j>pb->j)/当a此行已经检查完或者pb因该放在pa前面if (pre=NUL

39、L)a. rhead p->i=p;else pre->right=p;p->right=pa;pre = p;if (hp->j=NULL)/当前插入位置下面无非零元 /因为是逐行处理，so,hp->j，依次下移 /因此每次都是指向插入的位置 a. chead p->j= p; p->down = NULL;else p->down = hp->j->down;hp->j->down = p;hp->j=p;/*hp->j下移指向下次插入的位置pb=pb->right;/pb指向该行下个元素else i

40、f(pa&&pa->j<pb->j)/只要移动pa的指针*先不加|(pb=NULL&&pa)pre = pa;hpa->j=pa;/移动h，使其指向下次插入的位置pa = pa->right;else if(pa->j=pb->j)pa->e+=pb->e;if(pa->e)/不为零pre=pa;hpa->j=pa;pb=pb->right;/加else/pa->e为零，删除节点if (pre =NULL)a.rhead pa->i=pa->right;else pre-&

41、gt;right=pa->right;p=pa;/p指向pa，用来在下面修改列指针pa=pa->right;if (h p->j=NULL) a.chead p->j=p->down;else hp->j->down=p->down;free(p);pb=pb->right;return a;void multycross(crosslist &c)/十字链表乘法node *p,*q,*u,*v,*p1,*p2;crosslist a,b;link *r;int i,j,k,e;printf("十字链表乘法:n"

42、);createcross(a);createcross(b);c.m=a.m;c.n=b.n;c.t=0;c.rhead=(link *)malloc(a.m+1)*sizeof(link);/给行和列的头指针分配内存 c.chead=(link *)malloc(b.n+1)*sizeof(link);for(k=1;k<=a.m;k+)/初始化行，列的头指针c.rheadk=NULL;for(k=1;k<=b.n;k+)c.cheadk=NULL;r=(link *)malloc(b.n+1)*sizeof(link);for(i=1;i<=a.m;i+)u=(node

43、 *)malloc(sizeof(node);u->e=0;u->i=0;u->j=0;for(k=1;k<=b.n;k+)/初始化rrk=u;p1=p=a.rheadi;for(j=1;j<=b.n;j+) p=p1;q=b.cheadj;v=(node *)malloc(sizeof(node);/初始化v，v为将插入c矩阵的元素v->e=0;v->i=i;v->j=j;while(p&&q)if(p->j>q->i)q=q->down;else if(p->j<q->i)p=p-&g

44、t;right;elsev->e+=p->e*q->e;p=p->right;q=q->down;if(v->e)/如果不为零，则插入c矩阵中/同建立十字链表if(c.rheadi=NULL|c.rheadi->j>j)/插入元素所在行无非零元或首非零元的列标大于插入元素的列标v->right=c.rheadi;c.rheadi=v;else for(p2=c.rheadi;(p2->right)&&(p2->right->j<j);p2=p2->right);/空循环找到第一个列标大于或等于插入元素列标的元素v->right=p2->right;p2->right=v;if(c.cheadj=NULL|c.cheadj->i>i)/插入元素所在列无非零元或首非零元的行标大于插入元素的行标v->down=c.cheadj;c.cheadj=v;elsefor(p2=c.cheadj;(p2->down)&&(p2->down->i<i);p2=p2->down);/空循环找到第一个行标大于或等于插入元素行标的元素v->down=p2->do