l5_3.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;  
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;
}

void main()
{    linknode *p,*q;
	linknode  *hm=NULL;
hm=creatlindmat( );
cout<<" 输出十字链表"<<endl;
p=hm->k.next;
while(p->k.next!=hm->k.next)
{ q=p->rptr;
   while(q->rptr!=p)
	  { cout<<q->i<<" "<<q->j<<" "<<q->k.v<<" ";
         q=q->rptr;
		 }
   cout<<q->i<<" "<<q->j<<" "<<q->k.v<<" ";
   cout<<endl;
   p=p->k.next;
}
}