稀疏矩阵的乘法运算
程序代码：
#include<iostream.h>
#include<fstream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define Ture 1
#define Overflow -1
typedef struct OLnode
{
int i,j;
int e;
struct OLnode *right,*down;
}OLnode,*Olink;
typedef struct
{
Olink *rhead,*chead;
int mu,nu,tu;
}Crosslist;
//在十字链表M.rhead[row]中插入一个t结点
void insert_row(Crosslist &M,OLnode *t,int row)
{
OLnode *p;
int col=t->j;
if(M.rhead[row]==NULL||M.rhead[row]->j>col)
{
t->right=M.rhead[row];
M.rhead[row]=t;
}
else
{
for(p=M.rhead[row];p->right&&p->right->j<col;p=p->right);//寻找在行表中的插入位置
t->right=p->right;
p->right=t;
}
}
//在十字链表M.chead[col]中插入一个结点t
void insert_col(Crosslist &M,OLnode *t,int col)
{
OLnode *p;
int row=t->i;
if(M.chead[col]==NULL||M.chead[col]->i>row)
{
t->down=M.chead[col];
M.chead[col]=t;
}
else
{
for(p=M.chead[col];p->down&&p->down->i<row;p=p->down);//寻找在列表中的插入位置
t->down=p->down;
p->down=t;
}
}
//创建十字链表并存入数据
void input(Crosslist &M)
{
int m,n,t;
cout<<"请输入矩阵的行和列的个数及非零元个数";
cin>>m>>n>>t;
if(t>m*n) exit(Overflow);
M.mu=m;
M.nu=n;
M.tu=t;
int row,col,e;
OLnode *q;
M.rhead=(Olink *)malloc((m+1)*sizeof(Olink));
M.chead=(Olink *)malloc((n+1)*sizeof(Olink));
if(!M.rhead) exit(Overflow);
if(!M.chead) exit(Overflow);
for(int i=0;i<=m+1;i++)
M.rhead[i]=NULL;
for(int j=0;j<=n;j++)
M.chead[j]=NULL;
cout<<"请输入矩阵"<<endl;
int k=1;
for(cin>>row>>col>>e;row!=0&&k<=t;cin>>row>>col>>e,k++) {
q=(OLnode *) malloc(sizeof(OLnode));
if(!t) exit(Overflow);
q->e=e; //生成结点
q->i=row;
q->j=col;
insert_row(M,q,row); //完成行插入
insert_col(M,q,col); //完成列插入
}
}
//矩阵M与矩阵N的乘法运算
void chengfa(Crosslist M,Crosslist N,Crosslist &Q)
{
if(M.nu!=N.mu) exit(Overflow);
Q.mu=M.mu;
Q.nu=N.nu;
Q.tu=0;
OLnode *p,*q,*t;
Olink temp;
int e,col;
Q.rhead=(Olink *)malloc((Q.mu+1)*sizeof(Olink));
Q.chead=(Olink *)malloc((Q.nu+1)*sizeof(Olink));
if(!Q.rhead) exit(Overflow);
if(!Q.chead) exit(Overflow);
temp=(Olink)malloc((Q.nu+1)*sizeof(OLnode));
for(int i=0;i<=Q.mu+1;i++)
Q.rhead[i]=NULL;
for(int j=0;j<=Q.nu;j++)
Q.chead[j]=NULL;
for(int row=1;row<=Q.mu;row++)
{
for(int k=1;k<=Q.nu;k++)
temp[k].e=0;
for(p=M.rhead[row];p!=NULL;p=p->right)
{
int row2=p->j;
for(q=N.rhead[row2];q;q=q->right)//将每一行的各列乘积存入temp中 {
col=q->j;
temp[col].e+=p->e*q->e;
temp[col].i=row;
temp[col].j=col;
}
}
for(col=1;col<=Q.nu;col++)//将temp中的数据赋值给t，将t插入Q中 {
if(temp[col].e!=0)
{
t=(Olink)malloc(sizeof(OLnode));
t->e=temp[col].e;
t->i=temp[col].i;
t->j=temp[col].j;
insert_row(Q,t,row);
insert_col(Q,t,col);
}
}
}
}
void output(Crosslist M) //输出矩阵M
{
OLnode *pp;
for(int i=1;i<=M.mu;i++)
{
pp=M.rhead[i];
for(int j=1;j<=M.nu;j++)
{
if(pp&&pp->j==j)
{
int e=pp->e;
cout<<pp->e<<" ";
pp=pp->right;
}
else
cout<<0<<" ";
}
cout<<endl;
}
}
void main()
{
Crosslist M,N,Q;
input(M);
input(N);
cout<<"矩阵M:"<<endl;
output(M);
cout<<"矩阵N:"<<endl;
output(N);
chengfa(M,N,Q);
cout<<"矩阵M、N的乘积为："<<endl; output(Q);
}
运行结果：。