用十字链表存储 稀疏矩阵乘法

//稀疏矩阵乘法 用十字链表存储 C=A*B 输出C； Z1240 还出现超时
#include<stdio.h>
#include<stdlib.h>

typedef struct mnode
{
int row,col,v;
struct mnode *down,*right;
}MNode;

typedef struct
{
int mu,nu,tu;
MNode *rlink[10001],*clink[10001];
}CrossLink;

CrossLink *CreatCrossLink2( CrossLink *H,int i,int j,int v)//创建十字链表存储的稀疏矩阵 第2步
{
MNode *p,*q;
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为第一个节点
{
p->right=q;
H->rlink[i]=p;
}
else// 寻找p在第i行的位置
{
while(q->right&&(q->right->col)<j)
q=q->right;
p->right=q->right;
q->right=p; //完成p在行链上的插入
}

//以下是将 p插入到列链表中去，且按行号有序
q=H->clink[j];
if(q==NULL||q->row>i)//插入 *p为第一个节点
{
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; //完成p在列链上的插入
}
return H;
}

CrossLink *CreatCrossLink1(CrossLink *H)//创建十字链表存储的稀疏矩阵 第1步
{
int i,j,k,v;
H=(CrossLink *)malloc(sizeof(CrossLink));
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;

for(k=1;k<=H->tu;k++)
{
scanf("%d%d%d",&i,&j,&v);//非零元素的录入 行、列、非零元素的大小
CreatCrossLink2( H,i,j,v);
}
return H;
}

int main()
{ // freopen("1.txt","r",stdin);
CrossLink *A,*B,*C;
MNode *aq,*bq,*q;
int i,k,temp;

C=(CrossLink *)malloc(sizeof(CrossLink));
A=(CrossLink *)malloc(sizeof(CrossLink));
B=(CrossLink *)malloc(sizeof(CrossLink));

A=CreatCrossLink1(A);
B=CreatCrossLink1(B);

C->mu=A->mu;
C->nu=B->nu;

if(A->nu!=B->mu)
return 0;

else if(A->tu*B->tu==0)
{
printf("%d %d 0\n",C->mu,C->nu);
return 0;
}
else
{
for( k=1;k<=C->mu;k++)
C->rlink[k]=NULL;
for(k=1;k<=C->nu;k++)
C->clink[k]=NULL;

C->tu=0;

for( i=1;i<=(A->mu);i++)
{
q=A->rlink[i];// A矩阵中第i行的第一个元素
if(q)
{
for(int j=1;j<=B->nu;j++)
{
temp=0;
aq=q;
bq=B->clink[j]; // B矩阵中第j列的第一个元素
while(aq&&bq)
{
// printf("a.....i==%d j==%d v==%d\n",aq->row,aq->col,aq->v);
// printf("b1.....i==%d j==%d v==%d\n\n",bq->row,bq->col,bq->v);
if(aq->col==bq->row)// A矩阵元素aq所在的列与B矩阵元素bq所在的行相等
{
temp=temp+(aq->v)*(bq->v);
aq=aq->right; // 取A矩阵aq元素所在行的下一个元素
bq=bq->down; // 取B矩阵bq元素所在列的下一个元素
}
else if(aq->col<bq->row) // 取A矩阵aq元素所在行的下一个元素
aq=aq->right;
else // 取B矩阵bq元素所在列的下一个元素
bq=bq->down;
}//while

if(temp!=0)
{
(C->tu)++;
CreatCrossLink2( C,i,j,temp);
// printf("i==%d j==%d temp==%d\n",i,j,temp);
}
}//for j

}//if
}//for
if((C->tu)==0)
printf("%d %d 0\n",C->mu,C->nu);

else
{
printf("%d %d %d\n",C->mu,C->nu,C->tu);
for(i=1;i<=C->mu;i++)
{
q=C->rlink[i];
while(q)
{
printf("%d %d %d\n",q->row,q->col,q->v);
q=q->right;
}
}
}
}
return 0;
}