十字链表矩阵相乘
-
两个十字链表的矩阵相乘。
-
矩阵的输入
- 先需要输入矩阵的行数、列数、非0个数
- 在输入非零数的坐标和数值
第一个矩阵:矩阵的显示比较粗糙,自己有需求自己改一下吧。
第二个矩阵:
结果:
- 结果输出不是矩阵,自己需要可以自己改一下结果显示形式,我就这样显示了。
这个代码实在dev C++上实现的,这个看一下自己的环境,一般都没什么问题。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#define ok 1
#define overflow 0
#define error -1
typedef int ElemType;
typedef int Status;
typedef struct OLNode
{
int i,j;
ElemType e;
struct OLNode *right,*down;
}OLNode, *OLink;
typedef struct{
OLink *rhead,*chead;
int mu,nu,tu;
}CrossList;
Status CreateSMatrix_OL(CrossList &M)
{
int m,n,t,c=0;
int i,j,e;
int count;
OLink p,q;
printf("稀疏矩阵的行数、列数、非零元个数:\n");
scanf("%d%d%d", &m, &n, &t);
M.mu=m;
M.nu=n;
M.tu=t;
if(m<1||n<1||t>m*n) {
printf("该对象不符合矩阵要求");}
else{
if(!(M.rhead=(OLink *)malloc((m+1)*sizeof(OLink)))) exit(overflow);
if(!(M.chead=(OLink *)malloc((n+1)*sizeof(OLink)))) exit(overflow);
for(i=0;i<=m;i++) M.rhead[i]=NULL;
for(j=0;j<=n;j++) M.chead[j]=NULL;
printf("请依次输入元素行数、列数、权值:\n");
for(count=0; count<t;count++)
{ c=count+1;
printf("请输入第%d元素的关键信息:",c);
scanf("%d%d%d", &i, &j, &e);
if(!(p=(OLNode *)malloc(sizeof(OLNode)))) exit(overflow);
p->i=i; p->j=j; p->e=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; //rhead是列数组
}
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; //chead是行数组
}
}
}
return ok;
}
Status Initalization_OL(OLink &l)
{
if(!(l=(OLNode *)malloc(sizeof(OLNode)))) exit(overflow);
}
Status Initalization_S(CrossList A,CrossList B,CrossList &M)//初始化矩阵c
{ int m,n;
int i,j;
M.mu=A.mu;
m=A.mu;
M.nu=B.nu;
n=B.nu;
if(!(M.rhead=(OLink *)malloc((m+1)*sizeof(OLink)))) exit(overflow);
if(!(M.chead=(OLink *)malloc((n+1)*sizeof(OLink)))) exit(overflow);
for(i=0;i<=m;i++) M.rhead[i]=NULL;
for(i=0;i<=n;i++) M.chead[i]=NULL;
return ok;
}
Status CreateSMatrix(CrossList &M,OLink &l)
{
int i,j,e;
OLink p,q;
i=l->i;
j=l->j;
e=l->e;
if(!(p=(OLNode *)malloc(sizeof(OLNode)))) exit(overflow);
p->i=i; p->j=j; p->e=e;p->down=NULL;p->right=NULL;
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; //rhead是列数组
}
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; //chead是行数组
}
return ok;
}
int PrintSMatrix(CrossList M)
{
int i,j;
OLink p;
if(M.mu<1||M.nu<1){printf("矩阵为空矩阵或者是非正常矩阵\n");
}
else{
for(j=1;j<=M.mu;j++)
{
p=M.rhead[j];
while(p)
{
printf("第%d行%d列值为:%d\n",p->i,p->j,p->e);
p=p->right;
}
}
}
return ok;
}
int MulA_B(CrossList A,CrossList B,CrossList &C)
{
OLNode *q=NULL,*L=NULL;
OLink S;
int i,j,num;
Initalization_OL(S);
S->down=NULL;
S->right=NULL;
if(A.nu==B.mu){
Initalization_S(A,B,C);
for(i=1;i<=C.mu;i++)
for(j=1;j<=C.nu;j++)
{num=0;
q=A.rhead[i];
L=B.chead[j];
while((q!=NULL)&&(L!=NULL))
{if(q->j==L->i){num+=q->e*L->e;
q=q->right;L=L->down;
}
else if(q->j>L->i)
{
for(;L!=NULL;L=L->down)
{
if(q->j<=L->i) break;}}
else
{for(;q!=NULL;q=q->right)
{
if(q->j>=L->i) break;
}}
} printf("%d ",num);
if(num!=0)
{
S->i=i;
S->j=j;
S->e=num;
CreateSMatrix(C,S);
}
else ;}
}
else{
printf("\n矩阵无法相乘\n");
}
}
int main()
{
CrossList A,B,C;
OLink p,q,l;
int data;
printf("请依次输入第一个\n");
CreateSMatrix_OL(A);
printf("\n该矩阵是%d*%d的矩阵\n",A.mu,A.nu);
PrintSMatrix(A);
printf("\n请依次输入第二个\n");
CreateSMatrix_OL(B);
printf("\n该矩阵是%d*%d的矩阵\n",B.mu,B.nu);
PrintSMatrix(B);
printf("\n矩阵相乘的结果:");
MulA_B(A,B,C);
printf("\n该矩阵是%d*%d的矩阵\n",C.mu,C.nu);
PrintSMatrix(C);
system("pause");
return 0;
}