稀疏矩阵乘法运算

稀疏矩阵的乘法运算

程序代码：

#include #include #include #include #include #include #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->jright);//寻找在

行表中的插入位置 }

//在十字链表M.chead[col]中插入一个结点t void insert_col(Crosslist &M,OLnode *t,int col) {

OLnode *p;

int row=t->i;

t->right=p->right; p->right=t;

}

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->idown);//寻找在列表

中的插入位置 }

//创建十字链表并存入数据 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);

t->down=p->down; p->down=t;

}

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<<\请输入矩阵\ 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;