稀疏矩阵十字链表基本函数.doc

稀疏矩阵十字链表基本函数
1.宏定义
#include<stdio.h>
#include<stdlib.h>
#definedatatypeint
#defineMAXROW100
#defineMAXCOL100
2.结构体
typedefstructmnode
{
introw,col;
datatypev;
structmnode*down,*right;
}Mnode,*Mlink;
typedefstruct
{
intmu,nu,tu;
Mnode*rlink[MAXROW],*clink[MAXCOL];
}Crosslink;
3.稀疏矩阵十字链表基本函数
Crosslink*Creat_Crosslink()
/*建立十字链表函数1.先决条件:2.函数作用:创建十字链表存储的稀疏矩阵*/
{
Crosslink*H;
Mnode*p,*q;
inti,j,k,v;
H=(Crosslink*)malloc(sizeof(Crosslink));
printf("请输入矩阵的行列及非零元素的个数:\n");
scanf("%d%d%d",&H->mu,&H->nu,&H->tu);
for(k=1;k<=H->mu;k++)
H->rlink[k]=NULL;
for(k=1;k<=H->nu;k++)
H->clink[k]=NULL;
printf("请输入%d个三元组:\n",H->tu);
for(k=1;k<=H->tu;k++)
{
scanf("%d%d%d",&i,&j,&v);
p=(Mnode*)malloc(sizeof(Mnode));
p->row=i;
p->col=j;
p->v=v;
q=H->rlink[i];
if(q==NULL||q->col>j)
{
p->right=q;
H->rlink[i]=p;
}
else
{
while(q->right&&(q->right->col)<j)
q=q->right;
p->right=q->right;
q->right=p;
}
q=H->clink[j];
if(q==NULL||q->row>i)
{
p->down=q;
H->clink[j]=p;
}
else
{
while(q->down&&(q->down->row)<i)
q=q->down;
p->down=q->down;
q->down=p;
}
}
returnH;
}
Crosslink*Add_Crosslink(Crosslink*HA,Crosslink*HB)
/*十字链表相加函数1.先决条件:2.函数作用:将两个十字链表HA,HB相加到HC中,并返回HC*/
{
Crosslink*HC;
Mnode*pa,*pb,*pc;
Mnode*rl_rear[100],*cl_rear[100];//Mnode*rl_rear[m+1],*cl_rear[n+1];
inti,k;
if(HA->mu!=HB->mu||HA->nu!=HB->nu)
returnNULL;
HC=(Crosslink*)malloc(sizeof(Crosslink));
HC->mu=HA->mu;
HC->nu=HA->nu;
for(k=1;k<=HC->mu;k++)
HC->rlink[k]=NULL;
for(k=1;k<=HC->nu;k++)
HC->clink[k]=NULL;
for(k=1;k<=HC->mu;k++)
rl_rear[k]=HC->rlink[k];
for(k=1;k<=HC->nu;k++)
cl_rear[k]=HC->clink[k];
for(i=1;i<=HC->mu;i++)
{
pa=HA->rlink[i];
pb=HB->rlink[i];
while(pa||pb)
{
if(pa&&pb&&pa->col==pb->col&&pa->v+pb->v==0)
{
pa=pa->right;
pb=pb->right;
}
else
{
pc=(Mnode*)malloc(sizeof(Mnode));
pc->row=i;
pc->right=NULL;
pc->down=NULL;
if(pa->col<pb->col||pb==NULL)
{