bo5-4.c

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

 /* bo5-4.c 稀疏矩阵的十字链表存储(存储结构由c5-4.h定义)的基本操作(9个) */
 Status InitSMatrix(CrossList *M) /* 加 */
 { /* 初始化M(CrossList类型的变量必须初始化,否则创建、复制矩阵将出错) */
   (*M).rhead=(*M).chead=NULL;
   (*M).mu=(*M).nu=(*M).tu=0;
   return OK;
 }

 Status DestroySMatrix(CrossList *M)
 { /* 初始条件: 稀疏矩阵M存在。操作结果: 销毁稀疏矩阵M */
   int i;
   OLNode *p,*q;
   for(i=1;i<=(*M).mu;i++) /* 按行释放结点 */
   {
     p=*((*M).rhead+i);
     while(p)
     {
       q=p;
       p=p->right;
       free(q);
     }
   }
   free((*M).rhead);
   free((*M).chead);
   (*M).rhead=(*M).chead=NULL;
   (*M).mu=(*M).nu=(*M).tu=0;
   return OK;
 }

 Status CreateSMatrix(CrossList *M)
 { /* 创建稀疏矩阵M,采用十字链表存储表示。算法5.4 */
   int i,j,k,m,n,t;
   ElemType e;
   OLNode *p,*q;
   if((*M).rhead)
     DestroySMatrix(M);
   printf("请输入稀疏矩阵的行数 列数 非零元个数: ");
   scanf("%d%d%d",&m,&n,&t);
   (*M).mu=m;
   (*M).nu=n;
   (*M).tu=t;
   (*M).rhead=(OLink*)malloc((m+1)*sizeof(OLink));
   if(!(*M).rhead)
     exit(OVERFLOW);
   (*M).chead=(OLink*)malloc((n+1)*sizeof(OLink));
   if(!(*M).chead)
     exit(OVERFLOW);
   for(k=1;k<=m;k++) /* 初始化行头指针向量;各行链表为空链表 */
     (*M).rhead[k]=NULL;
   for(k=1;k<=n;k++) /* 初始化列头指针向量;各列链表为空链表 */
     (*M).chead[k]=NULL;
   printf("请按任意次序输入%d个非零元的行 列 元素值:\n",(*M).tu);
   for(k=0;k<t;k++)
   {
     scanf("%d%d%d",&i,&j,&e);
     p=(OLNode*)malloc(sizeof(OLNode));
     if(!p)
       exit(OVERFLOW);
     p->i=i; /* 生成结点 */
     p->j=j;
     p->e=e;
     if((*M).rhead[i]==NULL||(*M).rhead[i]->j>j) /* p插在该行的第一个结点处 */
     {
       p->right=(*M).rhead[i];
       (*M).rhead[i]=p;
     }
     else /* 寻查在行表中的插入位置 */
     {
       for(q=(*M).rhead[i];q->right&&q->right->j<j;q=q->right);
       p->right=q->right; /* 完成行插入 */
       q->right=p;
     }
     if((*M).chead[j]==NULL||(*M).chead[j]->i>i) /* p插在该列的第一个结点处 */
     {
       p->down=(*M).chead[j];
       (*M).chead[j]=p;
     }
     else /* 寻查在列表中的插入位置 */
     {
       for(q=(*M).chead[j];q->down&&q->down->i<i;q=q->down);
       p->down=q->down; /* 完成列插入 */
       q->down=p;
     }
   }
   return OK;
 }

 Status PrintSMatrix(CrossList M)
 { /* 初始条件: 稀疏矩阵M存在。操作结果: 按行或按列输出稀疏矩阵M */
   int i,j;
   OLink p;
   printf("%d行%d列%d个非零元素\n",M.mu,M.nu,M.tu);
   printf("请输入选择(1.按行输出 2.按列输出): ");
   scanf("%d",&i);
   switch(i)
   {
     case 1: for(j=1;j<=M.mu;j++)
             {
               p=M.rhead[j];
               while(p)
               {
                 printf("%d行%d列值为%d\n",p->i,p->j,p->e);
                 p=p->right;
               }
             }
             break;
     case 2: for(j=1;j<=M.nu;j++)
             {
               p=M.chead[j];
               while(p)
               {
                 printf("%d行%d列值为%d\n",p->i,p->j,p->e);
                 p=p->down;
               }
             }
   }
   return OK;
 }

 Status CopySMatrix(CrossList M,CrossList *T)
 { /* 初始条件: 稀疏矩阵M存在。操作结果: 由稀疏矩阵M复制得到T */
   int i;
   OLink p,q,q1,q2;
   if((*T).rhead)
     DestroySMatrix(T);
   (*T).mu=M.mu;
   (*T).nu=M.nu;
   (*T).tu=M.tu;
   (*T).rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink));
   if(!(*T).rhead)
     exit(OVERFLOW);
   (*T).chead=(OLink*)malloc((M.nu+1)*sizeof(OLink));
   if(!(*T).chead)
     exit(OVERFLOW);
   for(i=1;i<=M.mu;i++) /* 初始化矩阵T的行头指针向量;各行链表为空链表 */
     (*T).rhead[i]=NULL;
   for(i=1;i<=M.nu;i++) /* 初始化矩阵T的列头指针向量;各列链表为空链表 */
     (*T).chead[i]=NULL;
   for(i=1;i<=M.mu;i++) /* 按行复制 */
   {
     p=M.rhead[i];
     while(p) /* 没到行尾 */
     {
       q=(OLNode*)malloc(sizeof(OLNode)); /* 生成结点 */
       if(!q)
         exit(OVERFLOW);
       q->i=p->i; /* 给结点赋值 */
       q->j=p->j;
       q->e=p->e;
       if(!(*T).rhead[i]) /* 插在行表头 */
         (*T).rhead[i]=q1=q;
       else /* 插在行表尾 */
         q1=q1->right=q;
       if(!(*T).chead[q->j]) /* 插在列表头 */
       {
         (*T).chead[q->j]=q;
         q->down=NULL;
       }
       else /* 插在列表尾 */
       {
         q2=(*T).chead[q->j];
         while(q2->down)
           q2=q2->down;
         q2->down=q;
         q->down=NULL;
       }
       p=p->right;
     }
     q->right=NULL;
   }
   return OK;
 }

 Status AddSMatrix(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]所指结点之后 */
       {