十字链表矩阵相乘
-
两个十字链表的矩阵相乘。
-
矩阵的输入
- 先需要输入矩阵的行数、列数、非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);printf("有用点个推荐呗！");system("pause");return 0;
}
感谢关注与支持
