十字链表矩阵运算,求指点错误!!!!!
#include<stdio.h>#include<stdlib.h>
#include<process.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int elemtype;
typedef struct OLnode
{
int i,j;
elemtype data;
struct OLnode *right,*down;
}OLnode,*OLink;
typedef struct Crosslist
{
OLink *rhead,*chead;
int mu,nu,tu;
}Crosslist;
int InitSMatrix(Crosslist *M)
{
M->rhead=M->chead=NULL;
M->mu=M->nu=M->tu=0;
return OK;
}
int DestroySMatrix(Crosslist *M)
{
int i;
OLnode *p,*q;
for(i=1;i<M->mu;i++)
{
p=*(M->rhead+i);
while(p)
{
q=p;
p=p->right;
free(q);
}
}
free(M->rhead);
free(M->chead);
M->rhead=M->chead=NULL;
M->mu=M->nu=M->tu=0;
return OK;
}
int CreateSMatrix(Crosslist *M)
{
int i,j,k,m,n,t;
elemtype e;
OLnode *p,*q;
if(M->rhead)
DestroySMatrix(M);
printf("\n请输入稀疏矩阵的行数、列数、非零元个数:");
scanf("%d%d%d",&m,&n,&t);
M->mu=m;M->nu=n;M->tu=t;
M->rhead=(OLink *)malloc((m+1)*sizeof(OLink));
if(!M->rhead)
exit(OVERFLOW);
M->chead=(OLink*)malloc((n+1)*sizeof(OLink));
if(!M->chead)
exit(OVERFLOW);
for(k=1;k<=m;k++)
M->rhead[k]=NULL;
for(k=1;k<=n;k++)
M->chead[k]=NULL;
printf("\n请按任意次序输入%d个非零元的行、列、元素值:\n",M->tu);
for(k=0;k<t;k++)
{
scanf("%d%d%d",&i,&j,&e);
p=(OLnode*)malloc(sizeof(OLnode));
if(!p)
exit(OVERFLOW);
p->j=j;
p->i=i;
p->data=e;
if(M->rhead[i]==NULL || M->rhead[i]->j>j)
{
p->right=M->rhead[i];
M->rhead[i]=p;
}
else
{
for(q=M->rhead[i];q->right && q->right->j<j;q=q->right);
p->right=q->right;
q->right=p;
}
if(M->chead[j]==NULL || M->chead[j]->i>i)
{
p->down=M->chead[j];
M->chead[j]=p;
}
else
{
for(q=M->chead[j];q->down && q->down->i<i;q=q->down);
p->down=q->down;
q->down=p;
}
}
return OK;
}
int PrintSMatrix(Crosslist M)
{
int i,j;
OLink p;
printf("\n%d行%d列%d个非零元素\n",M.mu,M.nu,M.tu);
printf("请输入选择(1.按行输出 2.按列输出):");
scanf("%d",&i);
switch(i)
{
case 1:printf("行列值\n");
for(j=1;j<=M.mu;j++)
{
p=M.rhead[j];
while(p)
{
printf("%6d%6d%6d\n",p->i,p->j,p->data);
p=p->right;
}
}
break;
case 2:printf("列行值:\n");
for(j=1;j<=M.nu;j++)
{
p=M.chead[j];
while(p)
{
printf("%6d%6d%6d\n",p->i,p->j,p->data);
p=p->down;
}
}
}
return OK;
}
int AddSMatrix(Crosslist M,Crosslist N,Crosslist *Q)
{
int i,k;
OLink p,pq,pm,pn;
OLink *col;
if(M.mu!=N.mu || M.nu!=N.nu)
{
printf("两个矩阵是不同类型,不能相加\n");
exit(OVERFLOW);
}
Q->mu=M.mu;
Q->nu=M.nu;
Q->tu=0;
Q->rhead=(OLink *)malloc((Q->mu+1)*sizeof(OLink));
if(!Q->rhead)
exit(OVERFLOW);
Q->chead=(OLink *)malloc((Q->nu+1)*sizeof(OLink));
if(!Q->chead)
exit(OVERFLOW);
for(k=1;k<=Q->mu;k++)
Q->rhead[k]=NULL;
for(k=1;k<=Q->nu;k++)
Q->chead[k]=NULL;
col=(OLink*)malloc((Q->nu+1)*sizeof(OLink));
if(!col)
exit(OVERFLOW);
for(k=1;k<=Q->nu;k++)
col[k]=NULL;
for(i=1;i<=M.mu;i++)
{
pm=M.rhead[i];
pn=N.rhead[i];
while(pm && pn)
{
if(pm->j<pn->j)
{
p=(OLink)malloc(sizeof(OLnode));
if(!p)
exit(OVERFLOW);
Q->tu++;
p->j=pm->j;
p->i=i;
p->data=pm->data;
p->right=NULL;
pm=pm->right;
}
else if(pm->j>pn->j)
{
p=(OLink)malloc(sizeof(OLnode));
if(!p)
exit(OVERFLOW);
p->i=i;
p->j=pn->j;
p->data=pn->data;
p->right=NULL;
pn=pn->right;
Q->tu++;
}
else if(pm->data+pn->data)
{
p=(OLink)malloc(sizeof(OLnode));
if(!p)
exit(OVERFLOW);
Q->tu++;
p->i=i;
p->j=pn->j;
p->data=pm->data+pn->data;
p->right=NULL;
pm=pm->right;
pn=pn->right;
}
else
{
pm=pm->right;
pn=pn->right;
continue;
}
if(Q->rhead[i]==NULL)
Q->rhead[i]=pq=p;
else
{
pq->right=p;
pq=p;
}
if(Q->chead[p->j]==NULL)
Q->chead[p->j]=col[p->j]=p;
else
{
col[p->j]->down=p;
col[p->j]=p;
}
}
while(pm);
{
p=(OLink)malloc(sizeof(OLnode));
if(!p)
exit(OVERFLOW);
p->i=i;
p->j=pm->j;
p->data=pm->data;
Q->tu++;
p->right=NULL;
pm=pm->right;
if(Q->rhead[i]==NULL)
Q->rhead[i]=pq=p;
else
{
pq->right=p;
pq=p;
}
if(Q->chead[p->j]==NULL)
Q->chead[p->j]=col[p->j]=p;
else
{
col[p->j]->down=p;
col[p->j]=p;
}
}
while(pn)
{
p=(OLink)malloc(sizeof(OLnode));
if(!p)
exit(OVERFLOW);
p->i=i;
p->j=pn->j;
p->data=pn->data;
Q->tu++;
p->right=NULL;
pn=pn->right;
if(Q->rhead[i]==NULL)
Q->rhead[i]=pq=p;
else
{
pq->right=p;
pq=p;
}
if(Q->chead[p->j]==NULL)
Q->chead[p->j]=col[p->j]=p;
else
{
col[p->j]->down=p;
col[p->j]=p;
}
}
}
for(k=1;k<=Q->nu;k++)
if(col[k])
col[k]=NULL;
free(col);
return OK;
}
int MultSMatrix(Crosslist M,Crosslist N,Crosslist *Q)
{
int i,j,e;
OLink q,p0,q0,q1,q2;
InitSMatrix(Q);
Q->mu=M.mu;
Q->nu=N.nu;
Q->tu=0;
Q->rhead=(OLink *)malloc((Q->mu+1)*sizeof(OLnode));
if(!Q->chead)
exit(OVERFLOW);
Q->chead=(OLink *)malloc((Q->nu+1)*sizeof(OLnode));
if(!Q->chead)
exit(OVERFLOW);
for(i=1;i<=Q->mu;i++)
Q->rhead[i]=NULL;
for(i=1;i<=Q->nu;i++)
Q->chead[i]=NULL;
for(i=1;i<=Q->mu;i++)
for(j=1;j<=Q->nu;j++)
{
p0=M.rhead[i];
q0=N.chead[j];
e=0;
while(p0 && q0)
{
if(q0->i<p0->j)
q0=q0->down;
else if(q0->i>p0->j)
p0=p0->right;
else
{
e+=q0->data*p0->data;
q0=q0->down;
p0=p0->right;
}
}
if(e)
{
Q->tu++;
q=(OLink)malloc(sizeof(OLnode));
if(!q)
exit(OVERFLOW);
q->i=i;
q->j=j;
q->data=e;
q->down=NULL;
q->right=NULL;
if(!Q->rhead[i])
Q->rhead[i]=q1=q;
else
q1=q1->right=q;
if(!Q->chead[j])
Q->chead[j]=q;
else
{
q2=Q->chead[j];
while(q2->down)
q2=q2->down;
q2->down=q;
}
}
}
return OK;
}
void main()
{
Crosslist A,B,C;
InitSMatrix(&A);
InitSMatrix(&B);
InitSMatrix(&C);
printf("创建矩阵A:\n");
CreateSMatrix(&A);
PrintSMatrix(A);
printf("\n创建矩阵B1,准备进行A+B1计算!:\n");
printf("B1应与A的行列数相同,A的行=%d,列=%d\n",A.mu,A.nu);
CreateSMatrix(&B);
PrintSMatrix(B);
printf("\n矩阵C=A+B1:\n");
AddSMatrix(A,B,&C);
PrintSMatrix(C);
DestroySMatrix(&C);
DestroySMatrix(&B);
printf("\n创建矩阵B2,准备进行A*B2运算!:\n");
printf("B2的行数应该与A的列数=%d相同\n",A.nu);
CreateSMatrix(&B);
PrintSMatrix(B);
printf("\nC2=A*B2:\n");
MultSMatrix(A,B,&C);
printf("C2->mu,nu,tu=%d,%d,%d\n",C.mu,C.nu,C.tu);
//PrintSMatrix(C);
DestroySMatrix(&A);
DestroySMatrix(&B);
DestroySMatrix(&C);
}
[ 本帖最后由 ts16969 于 2014-3-13 20:27 编辑 ]