#include<iostream>
#include<iomanip>
using namespace std;
#define ERROR -1
typedef struct OLNode{
int i,j,e;
struct OLNode *right,*down;
}OLNode,*OLink;
typedef struct{
OLink *rhead,*chead;
int mu,nu,tu;
}CrossList;
int CreatMartix(CrossList &L){
int m,n,t;
cout<<"请输入矩阵行数，列数，非零个数";
cin>>m>>n>>t;
L.mu=m;
L.nu=n;
L.tu=t;
L.rhead=(OLink*)malloc((m+1)*sizeof(OLink));
if(!L.rhead)return ERROR;
for(m=0;m<L.mu+1;m++) L.rhead[m]=NULL;
L.chead=(OLink*)malloc((n+1)*sizeof(OLink));
if(!L.rhead)return ERROR;
for(m=0;m<L.nu+1;m++) L.chead[m]=NULL;
cout<<"请输入费单元的下标与数值";
for(m=0;m<L.tu;m++){
int x,y,z;
cin>>x>>y>>z;
OLink p;
p=(OLink)malloc(sizeof(OLNode));
if(!p)return 0;
p->i=x;
p->j=y;
p->e=z;
p->right=NULL;
p->down=NULL;
if(L.rhead[x]==NULL||L.rhead[x]->j>p->j)
{
p->right=L.rhead[x];
L.rhead[x]=p;
}
else if(L.rhead[x]->j<p->j)
{
OLink A;
for(A=L.rhead[x];A->right&&A->right->j<p->j;A=A->right);
p->right=A->right;
A->right=p;
}
if(L.chead[y]==NULL||L.chead[y]->i>p->i){
p->down=L.chead[y];
L.chead[y]=p;
}
else if(L.chead[y]->i<p->i){
OLink B;
for(B=L.chead[y];B->down&&B->down->i<p->i;B=B->down);
p->down=B->down;
B->down=p;
}
}
return 0;
}
int add(CrossList &A,CrossList&B){
int v=1;OLink *hl;hl=(OLink*)malloc(A.nu*sizeof(OLink));
while(v<=A.nu){hl[v]=A.chead[v];v++;}
for(v=1;v<=A.mu;v++){
OLink pa,pb,p,pre;
pre=NULL;
pa=A.rhead[v];
pb=B.rhead[v];
while(pb){
p=(OLink)malloc(sizeof(OLNode));
p=pb;
if(pa==NULL||pa->j>pb->j)
{pb=pb->right;
if(pre==NULL){
p->right=pa;
A.rhead[v]=p;
pre=p;
}
else{
p->right=pre->right;
pre->right=p;
pre=p;
}
if(A.chead[p->j]==NULL||A.chead[p->j]->i>p->i)
{
p->down=A.chead[p->j];
A.chead[p->j]=p;
hl[p->j]=p;
}
else
{
p->down=hl[p->j]->down;
hl[p->j]->down=p;
hl[p->j]=p;
}
}
else
if(pa!=NULL&&pa->j<pb->j)
{
hl[pa->j]=pa;
pre=pa;
pa=pa->right;
}
else if(pa->j==pb->j&&pa->e+pb->e==0)
{
if(pre==NULL){
A.rhead[v]=pa->right;
pa=pa->right;
pb=pb->right;
}
else{
pre->right=pa->right;
pa=pa->right;
pb=pb->right;
}
if(A.chead[p->j]->i==p->i)
{
A.chead[p->j]=A.chead[p->j]->down;
hl[p->j]=A.chead[p->j];}
else{
hl[p->j]->down=pa->down;}
}
else if (pa->j==pb->j&&pa->e+pb->e!=0)
{
hl[p->j]=pa;
pa->e+=pb->e;
pre=pa;
pa=pa->right;
pb=pb->right;
}
}
}
return 0;
}
int shuchu(CrossList& L){
for(int i=1;i<=L.mu;i++){
if(!L.rhead[i]){
for( int v=1;v<=L.nu;v++)
cout<<setw(4)<<0;
}
OLink pa=L.rhead[i];
if(pa&&pa->j>1)
{
int j=pa->j-1;
while(j--)cout<<setw(4)<<0;
}
while(pa)
{
if(!pa->right)
{
cout<<setw(4)<<pa->e;
if(pa->j<L.nu)
{int m=L.nu-pa->j;
while(m--)
cout<<setw(4)<<0;
}break;
}
else
{
cout<<setw(4)<<pa->e;
if(pa->right->j-pa->j>1)
{
int n=pa->right->j-pa->j-1;
while(n--)cout<<setw(4)<<0;
}
pa=pa->right;
}
}
cout<<endl;
}
return 0;
}
int jianfa(CrossList &A,CrossList&B){
int v=1;OLink *hl;hl=(OLink*)malloc(A.nu*sizeof(OLink));
while(v<=A.nu){hl[v]=A.chead[v];v++;}
for(v=1;v<=A.mu;v++){
OLink pa,pb,p,pre;
pre=NULL;
pa=A.rhead[v];
pb=B.rhead[v];
while(pb){
p=(OLink)malloc(sizeof(OLNode));
p=pb;
p->e=-(pb->e);
if(pa==NULL||pa->j>pb->j)
{pb=pb->right;
if(pre==NULL){
p->right=pa;
A.rhead[v]=p;
pre=p;
}
else{
p->right=pre->right;
pre->right=p;
pre=p;
}
if(A.chead[p->j]==NULL||A.chead[p->j]->i>p->i)
{
p->down=A.chead[p->j];
A.chead[p->j]=p;
hl[p->j]=p;
}
else
{
p->down=hl[p->j]->down;
hl[p->j]->down=p;
hl[p->j]=p;
}
}
else
if(pa!=NULL&&pa->j<pb->j)
{
hl[pa->j]=pa;
pre=pa;
pa=pa->right;
}
else if(pa->j==pb->j&&pa->e+pb->e==0)
{
if(pre==NULL){
A.rhead[v]=pa->right;
pa=pa->right;
pb=pb->right;
}
else{
pre->right=pa->right;
pa=pa->right;
pb=pb->right;
}
if(A.chead[p->j]->i==p->i)
{
A.chead[p->j]=A.chead[p->j]->down;
hl[p->j]=A.chead[p->j];}
else{
hl[p->j]->down=pa->down;}
}
else if (pa->j==pb->j&&pa->e+pb->e!=0)
{
hl[p->j]=pa;
pa->e+=pb->e;
pre=pa;
pa=pa->right;
pb=pb->right;
}
}
}
return 0;
}
int main(){
cout<<"------------矩阵加法-----------"<<endl;
CrossList P,Q;
CreatMartix(P);
cout<<"矩阵P"<<endl;
shuchu(P);
CreatMartix(Q);
cout<<"矩阵Q"<<endl;
shuchu(Q);
cout<<endl<<endl;
add(P,Q);
cout<<"矩阵P+Q:";
cout<<endl;
shuchu(P);
cout<<endl;
cout<<"------------矩阵减法-----------"<<endl;
CrossList C,D;
CreatMartix(C);
cout<<"矩阵C:"<<endl;
shuchu(C);
CreatMartix(D);
cout<<"矩阵D:"<<endl;
shuchu(D);
cout<<endl<<endl;
jianfa(C,D);
cout<<"矩阵C-D:";
cout<<endl;
shuchu(C);
return 0;
}