#include <stdio.h>
#include <stdlib.h>
#define EleTyp int
typedef struct OLnode
{
int i,j;
EleTyp e;
struct OLnode *right,*down;
}OLnode,*Node;
typedef struct OLink
{
Node *rhead,*chead;
int mu,nu,tu;
}OLink;
void CreateOLink(OLink *M);
void AddOLink(OLink *M,OLink N);
void PrintOLink(OLink M);
void main()
{
OLink M,N;
printf("请输入第一个稀疏矩阵的行数、列数、非零元素的个数 
用逗号分隔)!\n");
CreateOLink(&M);
printf("\n\n该稀疏矩阵为:\n");
PrintOLink(M);
printf("\n请输入第二个稀疏矩阵的行数、列数、非零元素的个数 用逗号分隔)!\n");
CreateOLink(&N);
printf("\n\n该稀疏矩阵为:\n");
PrintOLink(N);
AddOLink(&M,N);
printf("\n相加结果为：\n");
PrintOLink(M);
}
void CreateOLink(OLink *M)
{
int k;
int m,n,t;
int i,j,e;
OLnode *p,*r,*c;
if(!M)
{
printf("Error0!\n");
exit(0);
}
scanf("%d,%d,%d",&m,&n,&t);
M->mu=m;
M->nu=n;
M->tu=t;
if(!(M->rhead=(Node*)malloc(sizeof(Node)*(m+1))))
{
printf("Error1!\n");
exit(0);
}
if(!(M->chead=(Node*)malloc(sizeof(Node)*(n+1))))
{
printf("Error2!\n");
exit(0);
}
for(k=0;k<=m;k++) //将行头结点置空；
{
if(!(M->rhead[k]=(OLnode*)malloc(sizeof(OLnode))))
{
printf("Error3!\n");
exit(0);
}
M->rhead[k]->down=NULL;
M->rhead[k]->right=NULL;
M->rhead[k]->i=0;
M->rhead[k]->j=0;
M->rhead[k]->e=0;
}
for(k=0;k<=n;k++) //将列头结点只空；
{
if(!(M->chead[k]=(OLnode*)malloc(sizeof(OLnode))))
{
printf("Error4!\n");
exit(0);
}
M->chead[k]->down=NULL;
M->chead[k]->right=NULL;
M->chead[k]->i=0;
M->chead[k]->j=0;
M->chead[k]->e=0;
}
for(k=1;k<=t;k++)
{
printf("请输入第%d个元素的行号，列号，及元素值（用逗号分隔）:\n",k);
scanf("%d,%d,%d",&i,&j,&e);
if(!(p=(OLnode*)malloc(sizeof(OLnode))))
{
printf("Error4!\n");
exit(0);
}
p->i=i;
p->j=j;
p->e=e;
r=M->rhead[i]->right;
c=M->chead[j]->down;
if(r==NULL||r->j>j) //插入对应行链表中；
{
p->right=r;
M->rhead[i]->right=p;
}
else
{
while(r->right&&r->right->j<j)
r=r->right;
p->right=r->right;
r->right=p;
}
if(c==NULL||c->i>i) //插入对应列链表中；
{
p->down=c;
M->chead[j]->down=p;
}
else
{
while(c->down&&c->down->i<i)
c=c->down;
p->down=c->down;
c->down=p;
}
}
}
void PrintOLink(OLink M)
{
int k;
OLnode *p;
printf("\n*****************************\n");
for(k=1;k<=M.mu;k++)
{
p=M.rhead[k]->right;
while(p)
{
printf("%5d,%5d,%5d\n",p->i,p->j,p->e);
p=p->right;
}
}
printf("\n*****************************\n");
}
void AddOLink(OLink *M,OLink N)
{
int k,cj,x;
OLnode *p,*q,*t,*f,*s;
if(M->mu!=N.mu||M->nu!=N.nu)
{
printf("您给出的两个矩阵不能相加！\k");
exit(0);
}
for(k=1;k<=N.mu;k++)
{
p=M->rhead[k];
q=M->rhead[k]->right;
t=N.rhead[k]->right;
while(t)
{
if(q&&q->j<t->j)
{
p=q;
q=q->right;
}
else if(q==NULL||q->j>t->j)
{
f=(OLnode*)malloc(sizeof(OLnode));
f->i=t->i;
f->j=t->j;
f->e=t->e;
f->right=q;
p->right=f;
p=f;
cj=f->j;
s=M->chead[cj]->down;
if(s==NULL||s->i>f->i)
{
f->down=s;
M->chead[cj]->down=f;
}
else
{
while(s->down&&s->down->i<f->i)
s=s->down;
f->down=s->down;
s->down=f;
}
t=t->right;
}
else
{
x=q->e+t->e;
if(x!=0)
{
p=q;
q->e=x;
}
else
{
p->right=q->right;
cj=t->j;
s=M->chead[cj];
while(s->down->i<t->i)
s=s->down;
s->down=q->down;
free(q);
q=p;
}
q=q->right;
t=t->right;
}
}
}
}