bo5-4.cpp

清华大学《数据结构》教材第二版对应的C++教学程序

 // bo5-4.cpp 稀疏矩阵的十字链表存储(存储结构由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)
               {
                 cout<<p->i<<"行"<<p->j<<"列值为"<<p->e<<endl;
                 p=p->right;
               }
             }
             break;
     case 2: for(j=1;j<=M.nu;j++)
             {
               p=M.chead[j];
               while(p)
               {
                 cout<<p->i<<"行"<<p->j<<"列值为"<<p->e<<endl;
                 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]所指结点之后
       {