l5_4.cpp

《数据结构（C++描述）》-李根强-源代码

//稀疏矩阵的十字链表相加
#include <iostream.h> 
struct  linknode
{ int    i, j;
linknode  *cptr, *rptr;
union  
{   int   v;                  //*表结点使用V域,表示非零元值*/
linknode   *next;             //表头结点使用next域*/ 
}k;
};

 linknode  *creatlindmat ( )//建立十字链表
{   int     m, n, t, s, i, j, k;
linknode   *p , *q, *cp[100],*hm;  //*max
cout<<"请输入稀疏矩阵的行、列数及非零元个数"<<endl;
cin>>m>>n>>t;
if (m>m)  s=m;  else  s=n;
hm=new linknode ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{  p=new linknode;
   p->i=0;  p->j=0;
p->rptr=p;  p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for(int x=1;x<=t;x++)
{    cout<<"请输入一个三元组(i,j,v)"<<endl;
	cin>>i>>j>>k;           //输入一个非零元的三元组
p=new linknode;
p->i=i; p->j=j;  p->k.v=k;      //生成一个三元组的结点
//以下是将p扦入第i个链表中
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
//以下是将P扦入第j列链表中
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
  
 linknode *matadd(linknode *ha, linknode *hb)//十字链表相加

{  linknode  *pa, *pb, *qa, *ca,*cb,*p,*q;
  linknode  *hl[100];
int    i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
cout<<"矩阵不匹配,不能相加"<<endl;
else
{   p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{  hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr;  pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{   if((pa->j<pb->j)&&(pa->j!=0))
{    qa=pa;  pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0))     //扦入一个结点
{  p=new linknode;
p->i=pb->i;  p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p;  p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{  hl[j]=q;  q=hl[j]->cptr;}
hl[j]->cptr=p;  p->cptr=q;
hl[j]=p;
}
else 
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0)            //删除一个结点
{ qa->rptr=pa->rptr;   
j=pa->j;  q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q;  q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr;   pb=pb->rptr;
delete q;
}
else
{  qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next;  cb=cb->k.next;
}
}
return ha;
}

void print(linknode *ha)  //输出十字链表
{ linknode *p,*q,*r;
	p=ha->k.next;r=p;
while(p->k.next!=r)
{ q=p->rptr;
   while(q->rptr!=p)
	  { cout<<q->i<<" "<<q->j<<" "<<q->k.v<<" ";
         q=q->rptr;
		 }
   if(p!=q)
   cout<<q->i<<" "<<q->j<<" "<<q->k.v<<" ";
   cout<<endl;
   p=p->k.next;
}
}
void main()
{   
	linknode  *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( );
hb=creatlindmat( );
cout<<"第一个十字链表的结果"<<endl;
print(ha);cout<<endl;
cout<<"第二个十字链表的结果"<<endl;
print(hb);cout<<endl;
hc=matadd(ha,hb);
cout<<"相加后的十字链表的结果"<<endl;
print(hc);cout<<endl;
}