bo5-4.c

清华数据结构配套的c语言程序,可以结合着学.

         col[p->j]->down=p; /* 完成列插入 */
         col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
       }
     }
     while(pn) /* 将矩阵N该行的剩余元素插入矩阵Q */
     {
       p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
       if(!p)
         exit(OVERFLOW);
       (*Q).tu++; /* 非零元素数加1 */
       p->i=i; /* 给结点赋值 */
       p->j=pn->j;
       p->e=pn->e;
       p->right=NULL;
       pn=pn->right; /* pm指针向右移 */
       if((*Q).rhead[i]==NULL) /* p为该行的第1个结点 */
         (*Q).rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
       else /* 插在pq所指结点之后 */
       {
         pq->right=p; /* 完成行插入 */
         pq=pq->right; /* pq指向该行的最后一个结点 */
       }
       if((*Q).chead[p->j]==NULL) /* p为该列的第1个结点 */
         (*Q).chead[p->j]=col[p->j]=p; /* p插在该列的表头且col[p->j]指向p */
       else /* 插在col[p->j]所指结点之后 */
       {
         col[p->j]->down=p; /* 完成列插入 */
         col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
       }
     }
   }
   for(k=1;k<=(*Q).nu;k++)
     if(col[k]) /* k列有结点 */
       col[k]->down=NULL; /*  令该列最后一个结点的down指针为空 */
   free(col);
   return OK;
 }

 Status SubtSMatrix(CrossList M,CrossList N,CrossList *Q)
 { /* 初始条件: 稀疏矩阵M与N的行数和列数对应相等。 */
   /* 操作结果: 求稀疏矩阵的差Q=M-N */
   int i,k;
   OLink p,pq,pm,pn;
   OLink *col;
   if(M.mu!=N.mu||M.nu!=N.nu)
   {
     printf("两个矩阵不是同类型的,不能相加\n");
     exit(OVERFLOW);
   }
   (*Q).mu=M.mu; /* 初始化Q矩阵 */
   (*Q).nu=M.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(k=1;k<=(*Q).mu;k++) /* 初始化Q的行头指针向量;各行链表为空链表 */
     (*Q).rhead[k]=NULL;
   for(k=1;k<=(*Q).nu;k++) /* 初始化Q的列头指针向量;各列链表为空链表 */
     (*Q).chead[k]=NULL;
   col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink)); /* 生成指向列的最后结点的数组 */
   if(!col)
     exit(OVERFLOW);
   for(k=1;k<=(*Q).nu;k++) /* 赋初值 */
     col[k]=NULL;
   for(i=1;i<=M.mu;i++) /* 按行的顺序相加 */
   {
     pm=M.rhead[i]; /* pm指向矩阵M的第i行的第1个结点 */
     pn=N.rhead[i]; /* pn指向矩阵N的第i行的第1个结点 */
     while(pm&&pn) /* pm和pn均不空 */
     {
       if(pm->j<pn->j) /* 矩阵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) /* 矩阵M当前结点的列大于矩阵N当前结点的列 */
       {
         p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
         if(!p)
           exit(OVERFLOW);
         (*Q).tu++; /* 非零元素数加1 */
         p->i=i; /* 给结点赋值 */
         p->j=pn->j;
         p->e=-pn->e;
         p->right=NULL;
         pn=pn->right; /* pn指针向右移 */
       }
       else if(pm->e-pn->e) /* 矩阵M、N当前结点的列相等且两元素之差不为0 */
       {
         p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
         if(!p)
           exit(OVERFLOW);
         (*Q).tu++; /* 非零元素数加1 */
         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 /* 矩阵M、N当前结点的列相等且两元素之差为0 */
       {
         pm=pm->right; /* pm指针向右移 */
         pn=pn->right; /* pn指针向右移 */
         continue;
       }
       if((*Q).rhead[i]==NULL) /* p为该行的第1个结点 */
         (*Q).rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
       else /* 插在pq所指结点之后 */
       {
         pq->right=p; /* 完成行插入 */
         pq=pq->right; /* pq指向该行的最后一个结点 */
       }
       if((*Q).chead[p->j]==NULL) /* p为该列的第1个结点 */
         (*Q).chead[p->j]=col[p->j]=p; /* p插在该列的表头且col[p->j]指向p */
       else /* 插在col[p->]所指结点之后 */
       {
         col[p->j]->down=p; /* 完成列插入 */
         col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
       }
     }
     while(pm) /* 将矩阵M该行的剩余元素插入矩阵Q */
     {
       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指针向右移 */
       if((*Q).rhead[i]==NULL) /* p为该行的第1个结点 */
         (*Q).rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
       else /* 插在pq所指结点之后 */
       {
         pq->right=p; /* 完成行插入 */
         pq=pq->right; /* pq指向该行的最后一个结点 */
       }
       if((*Q).chead[p->j]==NULL) /* p为该列的第1个结点 */
         (*Q).chead[p->j]=col[p->j]=p; /* p插在该列的表头且col[p->j]指向p */
       else /* 插在col[p->j]所指结点之后 */
       {
         col[p->j]->down=p; /* 完成列插入 */
         col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
       }
     }
     while(pn) /* 将矩阵N该行的剩余元素插入矩阵Q */
     {
       p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
       if(!p)
         exit(OVERFLOW);
       (*Q).tu++; /* 非零元素数加1 */
       p->i=i; /* 给结点赋值 */
       p->j=pn->j;
       p->e=-pn->e;
       p->right=NULL;
       pn=pn->right; /* pm指针向右移 */
       if((*Q).rhead[i]==NULL) /* p为该行的第1个结点 */
         (*Q).rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
       else /* 插在pq所指结点之后 */
       {
         pq->right=p; /* 完成行插入 */
         pq=pq->right; /* pq指向该行的最后一个结点 */
       }
       if((*Q).chead[p->j]==NULL) /* p为该列的第1个结点 */
         (*Q).chead[p->j]=col[p->j]=p; /* p插在该列的表头且col[p->j]指向p */
       else /* 插在col[p->j]所指结点之后 */
       {
         col[p->j]->down=p; /* 完成列插入 */
         col[p->j]=col[p->j]->down; /* col[p->j]指向该列的最后一个结点 */
       }
     }
   }
   for(k=1;k<=(*Q).nu;k++)
     if(col[k]) /* k列有结点 */
       col[k]->down=NULL; /* 令该列最后一个结点的down指针为空 */
   free(col);
   return OK;
 }

 Status MultSMatrix(CrossList M,CrossList N,CrossList *Q)
 { /* 初始条件: 稀疏矩阵M的列数等于N的行数。操作结果: 求稀疏矩阵乘积Q=M*N */
   int i,j,e;
   OLink q,p0,q0,q1,q2;
   InitSMatrix(Q);
   (*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=1;i<=(*Q).mu;i++) /* 初始化矩阵Q的行头指针向量;各行链表为空链表 */
     (*Q).rhead[i]=NULL;
   for(i=1;i<=(*Q).nu;i++) /* 初始化矩阵Q的列头指针向量;各列链表为空链表 */
     (*Q).chead[i]=NULL;
   for(i=1;i<=(*Q).mu;i++)
     for(j=1;j<=(*Q).nu;j++)
     {
       p0=M.rhead[i];
       q0=N.chead[j];
       e=0;
       while(p0&&q0)
       {
         if(q0->i<p0->j)
           q0=q0->down; /* 列指针后移 */
         else if(q0->i>p0->j)
           p0=p0->right; /* 行指针后移 */
         else /* q0->i==p0->j */
         {
           e+=p0->e*q0->e; /* 乘积累加 */
           q0=q0->down; /* 行列指针均后移 */
           p0=p0->right;
         }
       }
       if(e) /* 值不为0 */
       {
	 (*Q).tu++; /* 非零元素数加1 */
	 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[i]) /* 行表空时插在行表头 */
	   (*Q).rhead[i]=q1=q;
	 else /* 否则插在行表尾 */
	   q1=q1->right=q;
	 if(!(*Q).chead[j]) /* 列表空时插在列表头 */
	   (*Q).chead[j]=q;
	 else /* 否则插在列表尾 */
	 {
	   q2=(*Q).chead[j]; /* q2指向j行第1个结点 */
	   while(q2->down)
             q2=q2->down; /* q2指向j行最后1个结点 */
           q2->down=q;
         }
       }
     }
   return OK;
 }

 Status TransposeSMatrix(CrossList M,CrossList *T)
 { /* 初始条件: 稀疏矩阵M存在。操作结果: 求稀疏矩阵M的转置矩阵T */
   int u,i;
   OLink *head,p,q,r;
   if((*T).rhead)
     DestroySMatrix(T);
   CopySMatrix(M,T); /* T=M */
   u=(*T).mu; /* 交换(*T).mu和(*T).nu */
   (*T).mu=(*T).nu;
   (*T).nu=u;
   head=(*T).rhead; /* 交换(*T).rhead和(*T).chead */
   (*T).rhead=(*T).chead;
   (*T).chead=head;
   for(u=1;u<=(*T).mu;u++) /* 对T的每一行 */
   {
     p=(*T).rhead[u]; /* p为行表头 */
     while(p) /* 没到表尾,对T的每一结点 */
     {
       q=p->down; /* q指向下一个结点 */
       i=p->i; /* 交换.i和.j */
       p->i=p->j;
       p->j=i;
       r=p->down; /* 交换.down.和right */
       p->down=p->right;
       p->right=r;
       p=q; /* p指向下一个结点 */
     }
   }
   return OK;
 }