aaa.cpp

稀疏矩阵十字链表相乘

#include<iostream.h>
#define maxsize 10
typedef struct linknode 
{   
int row, col;
    struct linknode *right, *down;
    union 
    {
         int val;
         struct linknode *next;
    }tag;
}mytype;

mytype *crosslink()    //建立十字链表
{
    int m,n,t,s,i,r,c,v;
    mytype *h[maxsize], *p,*q;
    cout<<"行数m,列数n,非零元素个数t:"<<endl;
    cin>>m>>n>>t;
    p=new mytype;
    p->row=m; p->col=n;
    h[0]=p;
    s=m>n?m:n;
    for(i=1;i<=s;i++)
    {  p=new mytype;
       h[i]=p;
       h[i-1]->tag.next=p;
       p->row=p->col=0;
       p->right=p->down=p;
    }
    h[s]->tag.next=h[0];
    for(i=1;i<=t;i++)
    {
        cout<<"第"<<i<<"个元素（行号r,列号c,值v):"<<endl;
        cin>>r>>c>>v;
        p=new mytype;
        p->row=r;
        p->col=c;
        p->tag.val=v;
        q=h[r];
        while(q->right!=h[r]&&q->right->col<c)
            q=q->right;
        p->right=q->right;
        q->right=p;
        q=h[c];
        while(q->down!=h[c]&&q->down->row<r)
            q=q->down;
        p->down=q->down;
        q->down=p;
    }
    return(h[0]);
}

void dispcrosslink(mytype *hm)    //显示十字链表
{
    mytype *p,*q;
    cout<<"\n按行表输出矩阵元素:\n";
    cout<<"row="<<hm->row;
    cout<<"     col="<<hm->col<<endl;
    p=hm->tag.next;
    while(p!=hm)
    {
        q=p->right;
        while(p!=q)
        {
            cout<<"    "<<q->row<<"    "<<q->col<<"    "<<q->tag.val<<endl;
            q=q->right;
        }
        p=p->tag.next;
    }
}

mytype *multiply(mytype *hm1,mytype *hm2) //矩阵相乘的函数

{
    int sum,i,j,flag,s,k,t;
    mytype *p1,*p2,*p,*q1,*q2,*q,*h[maxsize];
    s=hm1->row>hm2->col?hm1->row:hm2->col;
    t=hm1->row<=hm2->col?hm1->row:hm2->col;
    p=new mytype;
    h[0]=p;
    p->row=t;
    p->col=s;
    for(i=1;i<=s;i++)
    {  p=new mytype;
       h[i]=p;
       h[i-1]->tag.next=p;
       p->row=p->col=0;
       p->right=p->down=p;
     }
     h[s]->tag.next=h[0];
    p1=hm1->tag.next;
    ;
    for(i=1;i<=hm1->row;i++)
    {  p2=hm2->tag.next;
      for(j=1;j<=hm2->col;j++)
      {    
          sum=0;
          q1=p1->right;
          q2=p2->down;
         
          
    for(k=flag=1;k<=hm2->row;k++,flag++)       //flag为指针移动的标志
    {       if(q1==p1||q2==p2)  break;
            if(q1->col==q2->row)   
            sum+=q1->tag.val*q2->tag.val;
       if(q1->col==flag){ if(q1==p1) break;
                              q1=q1->right;}   
       

            if(q2->row==flag) { if(q2==p2)  break;
                                q2=q2->down;}
         }
    if(sum!=0)//若乘积不为0，插入到十字链表中
    {
        p=new mytype;
        p->row=i;
        p->col=j;
        p->tag.val=sum;
        q=h[i];
    while(q->right!=h[i]&&q->right->col<j)
        q=q->right; 
        p->right=q->right;
        q->right=p;
        q=h[j];
        while(q->down!=h[j]&&q->down->row<i)
            q=q->down;
        p->down=q->down;
        q->down=p;
        
    }
    p2=p2->tag.next;//行切换
      }
    p1=p1->tag.next;//列切换
    }
    return(h[0]);
}

void main()   //主函数
{ 
    mytype *hm1,*hm2,*hm3;
    hm1=crosslink();
    dispcrosslink(hm1);
    hm2=crosslink();
    dispcrosslink(hm2);
    if(hm1->col!=hm2->row)
    cout<<"此时两矩阵不能相乘"<<endl;
    else 
    {  hm3=multiply(hm1,hm2);
       cout<<"相乘后的矩阵为:"<<endl;
       dispcrosslink(hm3);
    }
}