这个程序主要是建立一个十子链表来存储稀疏矩阵，并在此结构上计算两个稀疏矩阵的和 #define OVERFLOW 0 #define max 5 #include<stdio.h> typedef struct olnode {int i,j; int e; struct olnode *right,*down; }olnode,*olink; typedef struct node {olink *rhead,*chead; int mu,nu,tu; }crosslist; crosslist create()//建立十子链表 {crosslist m; int a,b,c; int i,j,e,r; olink p,q; olink ptr[max]; printf("please enter m,n,t:"); scanf("%d%d%d",&a,&b,&c); m.mu=a;m.nu=b;m.tu=c; m.rhead=(olink*)malloc((a+1)*sizeof(olink)); if(!m.rhead) exit(OVERFLOW); m.chead=(olink*)malloc((b+1)*sizeof(olink)); if(!m.chead) exit(OVERFLOW); for(i=1;i<=m.mu;i++) m.rhead[i]=NULL; for(i=1;i<=m.nu;i++) m.chead[i]=NULL; q=m.rhead[1]; printf("please enter i,j,e:"); scanf("%d%d%d",&q->i,&q->j,&q->e); q->right=NULL; for(r=1;r<=m.tu-1;r++) {/*if(m.rhead[1]==NULL) q=m.chead[1];*/ printf("please enter i,j,e:"); p=(olink)malloc(sizeof(olnode)); if(!p) exit(OVERFLOW); scanf("%d%d%d",&p->i,&p->j,&p->e); if(p->i==q->i) {/*p->right=q->right;*/ q->right=p; q=p; if(m.chead[p->j]==NULL) {m.chead[p->j]=p;ptr[p->j]=p;} else {ptr[p->j]->down=p;ptr[p->j]=p;} } else if(p->i>q->i) {q->right=NULL; q=m.rhead[p->i]; q->right=p; q=p; if(m.chead[p->j]==NULL){m.chead[p->j]=p;ptr[p->j]=p;} else {ptr[p->j]->down=p;ptr[p->j]=p;} } } return m; } void print(crosslist m)//统一的输出函数用来输出十子链表 {olink p; int i,j; i=0;j=0; printf("**********************************************************************\n"); while(i<m.tu) {p=m.rhead[++j]; while(p->right!=NULL) { printf("(%d,%d,%d)\n",p->i,p->j,p->e); i++; p=p->right; } } printf("***********************************************************************\n"); } crosslist add(crosslist a,crosslist b)//矩阵的加法 {olink pa,pb; olink pre,p; olnode *hl[max]; int i,j; for(i=1;i<=a.mu;i++) {pa=a.rhead[i];pb=b.rhead[i];pre=NULL; if(pa==NULL) break; if(pb->j<pa->j|| pa==NULL) {p=(olink)malloc(sizeof(olink)); if(!p) exit(OVERFLOW); p->i=pb->i; p->j=pb->j; p->e=pb->e; if(pre==NULL) a.rhead[i]=p; else pre->right=p; p->right=pa; pre=p; pb=pb->right; if(p->i<a.rhead[p->j]->i) {p->down=a.chead[p->j]; a.chead[p->j]=p;} else { hl[p->j]=a.rhead[p->j]; while(hl[p->j]->down!=NULL && hl[p->j]->i<p->i) hl[p->j]=hl[p->j]->down; } if(a.chead[p->j]==NULL) {a.chead[p->j]=p; p->down=NULL;} else {p->down=hl[p->j]->down; hl[p->j]->down=p;} } if(pa->j<pb->j && pa!=NULL) {pre=pa;pa=pa->right;} if(pa->j==pb->j) {pa->e+=pb->e; if(pa->e!=0) {pre=pa; pa=pa->right;pb=pb->right;} else {if(pre==NULL) a.chead[pa->j]=pa->right; else pre->right=pa->right; pa=pa->right; pb=pb->right; if(pa->i<a.chead[pa->j]->i) {pa->down=a.chead[pa->j]; a.chead[p->j]=pa;} else {hl[pa->j]=a.chead[pa->j]; while(hl[pa->j]->down && hl[pa->j]->i<pa->i) hl[pa->j]=hl[pa->j]->down; } if(a.chead[pa->j]==pa) a.chead[pa->j]=pa; else {hl[pa->j]->down=pa->down;free(pa);} } } } return a; }

main() {crosslist a,b; a=create();print(a); /*b=create(); print(b); a=add(a,b);print(a);*/

}