稀疏矩阵相加的C程序

编写两个稀疏矩阵相加(A=A+B)的算法，要求稀疏矩阵用十字链表表示。

#include <stdio.h>
#include <malloc.h>

#define MAX 100

struct matnode      //十字链表结点的定义
{
 int row,col;
 struct matnode *right,*down;
 union  {
  int val;//表结点使用V域
  struct matnode *next;//表头结点使用next域
 }tag;
};
struct matnode *createmat(struct matnode *hmone[MAX])
{
 int m,n,t,s,i,r,c,v;
// struct matnode *l,*p,*q;
 struct matnode *h[100],*l,*p,*q;  //h[]是十字链表每行的表头指针数组
 printf("行数m,列数n,非零元素个数t:");
 //scanf("%d,%d,%d",&m,&n,&t); //输入行、列数，非零元素个数
 scanf("%d,%d,%d",&m,&n,&t);//输入行、列数，非零元素个数
 l=(struct matnode *)malloc(sizeof(struct matnode));
 h[0]=l;//h[]是指针数组，分别指向头节点和行、列表头结点
 l->row=m; //建立十字链表头结点*l
 l->col=n;
 s=m>n ? m:n; //确定表头节点个数 s=max(m,n)
 for(i=1;i<=s;i++)//建立头节点循环链表
 {
  p=(struct matnode *)malloc(sizeof(struct matnode));
  p->row=p->col=0;
  p->down=p->right=p;
  h[i]=p;
  h[i-1]->tag.next=p;  
 }

 //最后一个行、列表头结点指向十字链表头节点
 h[s]->tag.next=h[0];

 for(i=1;i<=t;i++)       //t为非零元素个数
 {
  printf("\t 第%d个元素(行号m,列号n,值v):",i);
  scanf("%d,%d,%d",&r,&c,&v);
  p=(struct matnode *)malloc(sizeof(struct matnode));
  //生成一个非零表结点*p
  p->row=r;
  p->col=c;
  p->tag.val=v;

        //以下是将*p结点插入第r行链表中
  q=h[r]; //取第r行表头结点
  while(q->right!=h[r]&&q->right->col<c)
   q=q->right;//在第r行中找第一个列号大于c的结点*(q->right)
  //找不到时，*q是该行表上的尾结点
  p->right=q->right;
  q->right=p;//*p插在*q之后

  //以下是将结点插入第c列链表中
  q=h[c];//取第c列表头结点
  while(q->down!=h[c]&&q->down->row<r)
   q=q->down;//在第c列中找第一个列号大于c的结点*(q->down)
  //找不到时，*q是该列表上的尾结点
  p->down=q->down;
  q->down=p;//*p插在*q之后
 }
 return(h[0]);
}
void prmat(struct matnode *hm)
{
 struct matnode *p,*q;
 printf("\n 按行表输出矩阵元素:\n");
 printf("row=%d col=%d\n",hm->row,hm->col);
 p=hm->tag.next;
 while(p!=hm)
 {
  q=p->right;
  while(p!=q)
  {
   printf("\t %d,%d,%d\n",q->row,q->col,q->tag.val);
   q=q->right;
  }
  p=p->tag.next;
 }
}

struct matnode *colpred(int i,int j, struct matnode *h[])
//根据i（行号）和j(列号)找出矩阵第i行第j列的非零元素在十字链表中的前驱结点
{
 struct matnode *d;
 d=h[j];
 while(d->down->col!=0 && d->down->row<i)
  d=d->down;
 return (d);
}

//求矩阵相加的算法
struct matnode *addmat(struct matnode *ha,struct matnode *hb,struct matnode *h[])
{
 struct matnode *p,*q,*ca,*cb,*pa,*pb,*qa;
  if(ha->row!=hb->row||ha->col!=hb->col)
  {
   printf("两个矩阵不是同类型的，不能相加！\n");
   return (0);
  }
  else
  {
   ca=ha->tag.next;
   cb=hb->tag.next;
   do
   {
    pa=ca->right;
    pb=cb->right;
    qa=ca;
    while(pb->col!=0)
     if(pa->col<pb->col&&pa->col!=0)
     {
      qa=pa;
      pa=pa->right;
     }
     else
      if(pa->col>pb->col||pa->col==0)
      {
       p=(struct matnode*)malloc(sizeof(struct matnode));
       *p=*pb;
       p->right=pa;
       qa->right=p;
       qa=p;
       q=colpred(p->row,p->col,h);
       p->down=q->down;
       q->down=pa;
       pb=pb->right;
      }
      else
      {
       pa->tag.val+=pb->tag.val;
       if(pa->tag.val==0)
       {
        qa->right=pa->right;
        q=colpred(pa->row,pa->col,h);
        q->down=pa->down;
        free(pa);
       }
       else qa=pa;
       pa=pa->right;
       pb=cb->right;
      }
      ca=ca->tag.next;
      cb=cb->tag.next;
   }while(ca->row==0);
  }
  return (h[0]);
}

void main(void)
{
 struct matnode *hm,*hm1,*hm2;
 struct matnode *h[MAX],*h1[MAX];
 printf("第一个矩阵：\n");
  hm1=createmat(h);
 printf("第二个矩阵：\n");
  hm2=createmat(h1);
 hm=addmat(hm1,hm2,h);
 prmat(hm);
} 

责任编辑 webmaster

相关链接

C语言编程易犯毛病集合

C语言常用排序全解

C语言难点分析整理

C语言高效编程秘籍

C语言-预处理程序

C语言位域精解

C语言中的结构和联合详解

k-均值聚类算法C语言源码