《用十字链表和一般方法分别实现稀疏矩阵的乘法和加法》由会员分享，可在线阅读，更多相关《用十字链表和一般方法分别实现稀疏矩阵的乘法和加法（25页珍藏版）》请在金锄头文库上搜索。
1、#include #include #define Size 2501 # define Size1 51 typedef struct int i; int j; int e;/非零元的值 triple; /定义三元组typedef struct triple dataSize+1;/矩阵中的元素 int ropsSize1+1;/ ropsi为第 i 行元素中的首非零元在 data中的序号 int mu;/行数 int nu;/列数 int tu;/非零元数 juzhen;/定义矩阵typedef struct node/ 定义十字链表元素 int i,j,e;struct node *r
2、ight,*down;/ 该非零元所在行表和列表的后继元素 node,*link;typedef struct / 定义十字链表对象结构体 link *rhead,*chead;/行和列的头指针 int m,n,t;/ 系数矩阵的行数，列数，和非零元素个数 crosslist;void createcross(crosslist node *p,*q; printf(“输入行，列和非零元数，空格隔开：n“); scanf(“%d %d %d“, M.rhead=(link *)malloc(M.m+1)*sizeof(link);/给行和列的头指针分配内存M.chead=(link *)mal
3、loc(M.n+1)*sizeof(link); for(k=1;ki=i; p-j=j; p-e=e; if(M.rheadi=NULL|M.rheadi-jj)/插入元素所在行无非零元或首非零元的列 标大于插入元素的列标 p-right=M.rheadi; M.rheadi=p; else for(q=M.rheadi;(q-right)/空循环找到第一个列 标大于或等于插入元素列标的元素 p-right=q-right; q-right=p; if(M.cheadj=NULL|(M.cheadj-ii)/插入元素所在列无非零元或首非零元的行 标大于插入元素的行标 p-down=M.che
4、adj; M.cheadj=p; else for(q=M.cheadj;(q-down)/空循环找到第一个 行标大于或等于插入元素行标的元素 p-down=q-down; q-down=p; void printcross(crosslist A)/输出十字链表 if(A.m=0) printf(“十字链表为空!n“); else printf(“十字链表为:n“);int i,j; for(i=1;ij) printf(“%5d“,p-e); p=p-right; else printf(“%5d“,0); printf(“n“); printf(“n“);crosslist addcro
5、ss() 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) printf(“格式不对，不能相加!n“); else for(i=1;ii=pb-i; p-j=pb-j; p-e=pb-e; if(pa=NULL|pa-jpb-j)
6、/当 a 此行已经检查完或者 pb 因该放在 pa 前 面 if (pre=NULL) a. rheadp-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 if(pa hpa-j=p
7、a;/移动 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-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
8、=pb-right; return a; void multycross(crosslist 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=(link *)malloc(a.m+1)*sizeof(link);/给行和列的头指针分配内存 c.chead=(link *)malloc(b.n+1)*sizeof(link)
9、; for(k=1;ke=0; u-i=0; u-j=0; for(k=1;ke=0; v-i=i; v-j=j;while(p else if(p-ji) p=p-right; else v-e+=p-e*q-e; p=p-right; q=q-down; if(v-e)/如果不为零，则插入 c 矩阵中 /同建立十字链表if(c.rheadi=NULL|c.rheadi-jj)/插入元素所在行无非零元或首 非零元的列标大于插入元素的列标 v-right=c.rheadi; c.rheadi=v; else for(p2=c.rheadi;(p2-right)/空 循环找到第一个列标大于或等于
10、插入元素列标的元素 v-right=p2-right; p2-right=v; if(c.cheadj=NULL|c.cheadj-ii)/插入元素所在列无非零元或首 非零元的行标大于插入元素的行标 v-down=c.cheadj; c.cheadj=v; else for(p2=c.cheadj;(p2-down)/空循环找到第一个行标大于或等于插入元素行标的元素 v-down=p2-down; p2-down=v; void create(juzhen printf(“输入矩阵行数和列数 and 非零元的个数，以空格隔开:n“); scanf(“%d %d %d“, printf(“输入矩
11、阵非零元的行，列，和数值(中间空格隔开):n“); for(i=1;iB.datak2.i)/同上 C.datak+=B.datak2+; else/datak1,datak2行标相同 if(A.datak1.jB.datak2.j)/datak1列标大于 datak2列标，则把 datak2 的值赋给 datak C.datak+=B.datak2+; else if(A.datak1.j，基本操作： Create（juzhen M） 操作结果：构造了矩阵 M。 Add（juzhen A，juzhen B，juzhen int j; int e;/非零元的值 triple; /定义三元组 2
12、、稀疏矩阵类型typedef struct triple dataSize+1;/矩阵中的元素 int ropsSize1+1;/ ropsi为第 i 行元素中的首非零元在 data中的 序号 int mu;/行数 int nu;/列数 int tu;/非零元数 juzhen;/定义矩阵 3、结点类型 typedef struct node int i,j,e;struct node *right,*down;/ 该非零元所在行表和列表的后继元素 node,*link; 4、十字链表类型 typedef struct / 定义十字链表对象结构体 link *rhead,*chead;/行和列的
13、头指针 int m,n,t;/ 系数矩阵的行数，列数，和非零元素个数 crosslist; 其中部分操作的算法： void printcross(crosslist A)/输出十字链表 printf(“十字链表为:n“); int i,j; for(i=1;ij) printf(“%5d“,p-e); p=p-right; else printf(“%5d“,0); printf(“n“); printf(“n“); crosslist addcross() printf(“十字链表加法:n“); crosslist a,b;/ 创建两个十字链表对象，并初始化 createcross(a);
14、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“); else for(i=1;ii=pb-i; p-j=pb-j; p-e=pb-e; if(pa=NULL|pa-jpb-j)/当 a 此行已经检查完或者 pb 因 该放在 pa 前面 if (pre=NULL) 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;
