#include#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -2typedef int ElemType;struct OLNode{ int i,j; //非零元所在行、列 ElemType e;//非零元值 OLNode *right,*down;};typedef OLNode *OLink;struct CrossList{ OLink *rhead,*chead;//行、列表头的头节点 int mu,nu,tu;//矩阵的行、列和非零元个数};int Create(CrossList &M){ int i,j,k,m,n,t; ElemType e; OLNode *p,*q; printf("请输入稀疏距阵的行数 列数 非零元的个数："); 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=0;k!=m;k++)//初始化行头指针M.rhead[k]=NULL; for(k=0;k!=n;k++)//初始化列头指针M.chead[k]=NULL; printf("请按任意次序输入%d个非零元的行 列 元素值:\n",M.tu); for(k=0;km||j>n){
printf("你输入的元素不在矩阵中 请检查重输:\n");
exit(OVERFLOW);}else{p=(OLNode*)malloc(sizeof(OLNode));if(!p) exit(OVERFLOW);p->i=i;p->j=j;p->e=e;if(M.rhead==NULL||M.rhead->j>j)//p插入该行第一节点处{ p->right=M.rhead; M.rhead=p;}else//寻找行表插入位置{ for(q=M.rhead;q->right&&q->right->jright); p->right=q->right;//完成行插入 q->right=p;}if(M.chead[j]==NULL||M.chead[j]->i>i)//p插入该列第一节点处{ p->down=M.chead[j]; M.chead[j]=p;}else//寻找列表插入位置{ for(q=M.chead[j];q->down&&q->down->idown); p->down=q->down;//完成列插入 q->down=p;}} } return OK;}int Print(CrossList M){ int i,j,k; OLink p; int array[100][100]; for(i=0;i!=M.mu;i++) {for(j=0;j!=M.nu;j++){ array[j]=0;//初始化数组所需部分} } for(k=0;k!=M.nu;k++) {
p=M.chead[k];
while(p)
{
array[p->i][p->j]=p->e;//将非零元存入数组中
p=p->down;
} } for(i=0;i!=M.mu;i++) {for(j=0;j!=M.nu;j++){ if(j==M.nu-1)
coutjj)//矩阵M当情前结点的列小于矩阵N当前结点的列 {
p=(OLink)malloc(sizeof(OLNode));//生成Q的结点
if(!p)
exit(OVERFLOW);
Q.tu++;//非零元个数＋1
p->i=i; //赋值
p->j=pm->j;
p->e=pm->e;
p->right=NULL;
pm=pm->right; //pm右移 } else if(pm->j>pn->j) {
p=(OLink)malloc(sizeof(OLNode));
if(!p)
exit(OVERFLOW);
Q.tu++;
p->i=i;
p->j=pn->j;
p->e=pn->e;
p->right=NULL;
pn=pn->right; } else if(pm->e+pn->e)//M,N当前结点的列相同并且两元素之和非零 {
p=(OLink)malloc(sizeof(OLNode));
if(!p)
exit(OVERFLOW);
Q.tu++;
p->i=i;
p->j=pn->j;
p->e=pm->e+pn->e;
p->right=NULL;
pm=pm->right;//pm右移
pn=pn->right;//pn右移 } else//两元素相加为零 {
pm=pm->right;
pn=pn->right;
continue; } if(Q.rhead==NULL)
Q.rhead=pq=p; else {
pq->right=p;//完成行插入
pq=pq->right; } if(Q.chead[p->j]==NULL)
Q.chead[p->j]=col[p->j]=p; else {
col[p->j]->down=p;//完成列插入
col[p->j]=col[p->j]->down; }}while(pm)//将矩阵M该行的剩余元素插入矩阵Q{ p=(OLink)malloc(sizeof(OLNode)); if(!p)
exit(OVERFLOW); Q.tu++; p->i=i; p->j=pm->j; p->e=pm->e; p->right=NULL; pm=pm->right;
if(Q.rhead==NULL)
Q.rhead=pq=p; else {
pq->right=p;
pq=pq->right; } if(Q.chead[p->j]==NULL)
Q.chead[p->j]=col[p->j]=p; else {
col[p->j]->down=p;
col[p->j]=col[p->j]->down; }}while(pn)//将矩阵N该行的剩余元素插入矩阵Q{ p=(OLink)malloc(sizeof(OLNode)); if(!p)
exit(OVERFLOW); Q.tu++; p->i=i; p->j=pn->j; p->e=pn->e; p->right=NULL; pn=pn->right;
if(Q.rhead==NULL)
Q.rhead=pq=p; else {
pq->right=p;
pq=pq->right; } if(Q.chead[p->j]==NULL)
Q.chead[p->j]=col[p->j]=p; else {
col[p->j]->down=p;
col[p->j]=col[p->j]->down; }}
} for(k=0;k!=Q.nu;k++)if(col[k]) col[k]->down=NULL;free(col);return OK;}CrossList Negative(CrossList M){ OLink p; for(int j=0;j!=M.mu;j++) {
p=M.rhead[j];
while(p)
{
p->e=-p->e;//将非零元的值反号
p=p->right;
} } return (M); }int Mult(CrossList M,CrossList N,CrossList &Q){ int i,j,e; OLink q,p0,q0,q1,q2; if(M.nu!=N.mu) {printf("你输入的两个距阵不能进行此操作\n");exit(OVERFLOW); }else { Q.mu=M.mu; Q.nu=N.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(i=0;i!=Q.mu;i++)//初始化行Q.rhead=NULL; for(i=0;i!=Q.nu;i++)//初始化列Q.chead=NULL; for(i=0;i!=Q.mu;i++)for(j=0;j!=Q.nu;j++){ p0=M.rhead; q0=N.chead[j]; e=0; while(p0&&q0) {
if(q0->ij)
q0=q0->down;//列后移
else if(q0->i>p0->j)
p0=p0->right;//行后移
else
{
e=e+p0->e*q0->e;//乘积累加
q0=q0->down;
p0=p0->right;//行列后移
} } if(e)//e不为零则插入Q {
Q.tu++;
q=(OLink)malloc(sizeof(OLNode));
if(!q)
exit(OVERFLOW);
q->i=i;
q->j=j;
q->e=e;
q->right=NULL;
q->down=NULL;
if(!Q.rhead)
Q.rhead=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;//声明三各矩阵 int Select; cout>Select; switch(Select) { case 1 ://稀疏矩阵相加{ Create(A); Create(B); cout<<"你输入的是"<<endl; Print(A); cout<<"加上"<<endl; Print(B); Add(A,B,C); cout<<"结果是"<<endl; Print(C); break;} case 2 ://稀疏矩阵相减{ Create(A); Create(B); cout<<"你输入的是"<<endl; Print(A); cout<<"减去"<<endl; Print(B); Negative(B); Add(A,B,C); cout<<"结果是"<<endl; Print(C); break;} case 3 ://稀疏矩阵相乘{
Create(A); Create(B); cout<<"你输入的是"<<endl; Print(A); cout<<"乘以"<<endl; Print(B); Mult(A,B,C); cout<<"结果是"<<endl; Print(C); break;} }}
|
