数据结构(严蔚敏C语言版)——稀疏矩阵

编程Cookbook 2020-03-19

点击上方蓝字关注我！

如果有错误或者理解不到位的地方还请各位指正！
数据结构的相关问题，可以参考笔者写的系列数据结构文章，或者加我交流！

声明：以下内容是对清华大学出版社出版，由严蔚敏和吴伟民编著的图书《数据结构》(C语言版)的代码实现。
图书PDF版本可移步公众号【李歘歘】回复电子书领取。

《数据结构》（C语言版）是各大高校计算机有关专业的指定教材，还是计算机考研的统考专业课数据结构指定的参考书籍，数据结构作为408专业课的重中之重，值得大家重视。

上次说到了数组，今天我们来说一下稀疏矩阵，在矩阵的压缩存储中，将矩阵分为了特殊矩阵和稀疏矩阵。

在特殊矩阵（对称矩阵、三角矩阵和对角矩阵等）中，非零元的分布都有一个明显的规律，从而我们都可以将其压缩存储到一维数组中，并找到每个非零元在一位数组中的对应关系。

一般我们将非零元比零元少，且分布没有一定的规律的矩阵称之为稀疏矩阵，这类矩阵的压缩就要比特殊矩阵复杂，下面就是讨论这一矩阵的基本操作，当然，特殊矩阵的四则运算也可以参考下面的代码。

书中位置：P97-P103

函数定义及说明：

Status CreateSMatrix(TSMatrix &M)  //创建稀疏矩阵
Status PrintfSMatrix(TSMatrix M)  //输出稀疏矩阵--个人认为将稀疏矩阵转换为普通矩阵输出时最合理的方法 
Status CopySMatrix(TSMatrix M,TSMatrix &T)  //复制稀疏矩阵
Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)  //稀疏矩阵相加 
Status SubSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)  //稀疏矩阵相减 
Status TransposeSMatrix(TSMatrix M, TSMatrix &T)  //矩阵转置————普通转置 
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)  //矩阵转置————快速转置 
Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q)
Status RLCreateSMatrix(RLSMatrix &M)  //创建稀疏矩阵（行逻辑连接的顺序表） 
Status RLPrintfSMatrix(RLSMatrix M)  //输出稀疏矩阵（ 行逻辑连接的顺序表） 
Status DestroySMatrix(TSMatrix &M)  //销毁矩阵

程序代码：

#include<cstdio>
#include<cstring>
#define ElemType int 
#define Status int 
//稀疏矩阵的三元组顺序表存储表示 
#define MAXSIZE 12500    //非零元的最大个数
#define MAXRC 100    //非零元的最大个数
typedef struct{
    int i, j;        //该非零元的行下标和列下标
    ElemType e;
}Triple;  //三元组类型 
typedef struct{
    Triple data[MAXSIZE+1];    //非零元三元组表，data[0]未用
    int mu, nu, tu;            //矩阵的行数、列数和非零元个数
}TSMatrix;    //稀疏矩阵类型
typedef struct{
    Triple data[MAXSIZE+1];
    int rpos[MAXRC+1];    //各行第一个非零元的位置表
    int mu, nu, tu;
}RLSMatrix;


//创建稀疏矩阵
Status CreateSMatrix(TSMatrix &M){
  printf("请输入矩阵的行数、列数、非零元素个数"); 
  scanf("%d%d%d",&M.mu,&M.nu,&M.tu); 
  for(int l=1;l<=M.tu;l++){
    printf("请输入元素（行下表、列下标、元素值）:\n");
    scanf("%d%d%d",&M.data[l].i,&M.data[l].j,&M.data[l].e);
  }
  printf("创建成功\n");
} 


//输出稀疏矩阵--个人认为将稀疏矩阵转换为普通矩阵输出时最合理的方法 
Status PrintfSMatrix(TSMatrix M){
  int MM[M.mu+1][M.nu+1];
  memset(MM,0,sizeof(MM));
  for(int l=1;l<=M.tu;l++){
    MM[M.data[l].i][M.data[l].j] = M.data[l].e;
  }
  for(int i=1;i<=M.mu;i++){
    for(int j=1;j<=M.nu;j++){
      printf("%3d",MM[i][j]); 
    }
    printf("\n");
  }
  printf("输出成功\n");
  return 0;
} 


//复制稀疏矩阵
Status CopySMatrix(TSMatrix M,TSMatrix &T){
  T=M;
  return 0; 
} 


//稀疏矩阵相加
Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q){
  if(M.mu!=N.mu||M.nu!=N.nu){
    printf("M和N行列不等\n"); 
    return 0; 
  }   
    Q.mu=M.mu,Q.nu=M.nu;
    int x,y,k=0;
  for(x=1,y=1;x<=M.tu && y<=N.tu;){
        if(M.data[x].i==N.data[y].i && M.data[x].j==N.data[y].j){
            Q.data[++k]=M.data[x++];
            Q.data[k].e+=N.data[y++].e;
            if(!Q.data[k].e)k--;
        }else if(M.data[x].i==N.data[y].i){
            if(M.data[x].j<N.data[y].j)
                Q.data[++k]=M.data[x++];
            else Q.data[++k]=N.data[y++];
            if(!Q.data[k].e)k--;
        }
        else {
            if(M.data[x].i<N.data[y].i)
                Q.data[++k]=M.data[x++];
            else Q.data[++k]=N.data[y++];
            if(!Q.data[k].e)k--;
        }
    }
    for(;x<=M.tu;x++)Q.data[++k]=M.data[x];
    for(;y<=N.tu;y++)Q.data[++k]=N.data[y];
  Q.tu = k ;  
    printf("相加成功\n"); 
    return 0;
}
//稀疏矩阵相减 
Status SubSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q){
  //相见等于加上相反数
  for(int i=1;i<=N.tu;i++){
    N.data[i].e*=-1;  
  } 
  AddSMatrix(M,N,Q);
    printf("相减成功\n"); 
  return 0; 
} 


//矩阵转置————方法一 
Status TransposeSMatrix(TSMatrix M, TSMatrix &T){
    T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
    if(T.tu){
        int q=1;
        for(int col=1; col<=M.nu; ++col)
            for(int p=1; p<=M.tu; ++p)
                if(M.data[p].j==col){
                    T.data[q].i=M.data[p].j;
                    T.data[q].j=M.data[p].i;
                    T.data[q].e=M.data[p].e;
                    ++q;
        }
    }
}




//矩阵转置————方法二 
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
  int num[M.nu+1];
  int cpot[M.nu+1];
    T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
    if(T.tu){
        for(int col=1; col<=M.nu; ++col) 
      num[col]=0;
        for(int t=1; t<=M.tu; ++t) 
      ++num[M.data[t].j];    //求M中每一列的非零元个数
        cpot[1]=1;
        //求第col列中第一个非零元在b.data中的序号
        for(int col=2; col<=M.nu; ++col) 
      cpot[col]=cpot[col-1]+num[col-1];
        for(int p=1; p<=M.tu; ++p){
            int col=M.data[p].j; 
      int q=cpot[col];
            T.data[q].i=M.data[p].j; 
            T.data[q].j=M.data[p].i;
            T.data[q].e=M.data[p].e;
            ++cpot[col];
        }
    }
  printf("\n");
    return 0;
}


Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q){
    if(M.nu!=N.mu){ 
    printf("%d!=%d错误\n",M.nu,N.mu);
    return 0;
    } 
    Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;
    if(M.tu*N.tu!=0){
        for(int arow=1; arow<=M.mu; ++arow){
            int tp;
      int ctemp[M.nu];    //当前行各元素累加器清零
      memset(ctemp,0,sizeof(ctemp));
            Q.rpos[arow]=Q.tu+1;
            if(arow<M.mu) tp=M.rpos[arow+1]-1;    //计算当前行最后一个非零元的位置
            else tp=M.tu;
            for(int p=M.rpos[arow]; p<=tp; ++p){  //对当前行中的每一个非零元
                int t;
        int brow=M.data[p].j;            //找到对应元在N中的行号
                if(brow<N.mu) t=N.rpos[brow+1]-1;  //计算N中j行最后一个非零元的位置
                else t=N.tu;
                for(int q=N.rpos[brow]; q<=t; ++q){
                    int ccol=N.data[q].j;
                    ctemp[ccol]+=M.data[p].e*N.data[q].e;
                }
            }
            for(int ccol=1; ccol<=Q.nu; ++ccol)
                if(ctemp[ccol]){
                    if(++Q.tu>MAXSIZE) return 0;
                    Q.data[Q.tu].i = arow;
          Q.data[Q.tu].j = ccol;
          Q.data[Q.tu].e = ctemp[ccol];
                }
        }
    }
    printf("相乘成功\n");
    return 0;
}


//创建稀疏矩阵（行逻辑连接的顺序表） 
Status RLCreateSMatrix(RLSMatrix &M){
  printf("请输入矩阵的行数、列数、非零元素个数"); 
  scanf("%d%d%d",&M.mu,&M.nu,&M.tu); 
  for(int l=1;l<=M.tu;l++){
    printf("请输入元素（行下表、列下标、元素值）:\n");
    scanf("%d%d%d",&M.data[l].i,&M.data[l].j,&M.data[l].e);
  }
  int num[M.mu+1];
    for(int row=1; row<=M.mu; ++row) 
    num[row]=0;
    for(int t=1; t<=M.tu; ++t) 
    ++num[M.data[t].i];    //求M中每一列的非零元个数
    M.rpos[1]=1;
    //求第row行中第一个非零元在b.data中的序号
    for(int row=2; row<=M.mu; ++row) {
      M.rpos[row]=M.rpos[row-1]+num[row-1];
      printf("%d   ",M.rpos[row]);
  }
  printf("创建成功\n");
} 


//输出稀疏矩阵（ 行逻辑连接的顺序表） 
Status RLPrintfSMatrix(RLSMatrix M){
  int MM[M.mu+1][M.nu+1];
  memset(MM,0,sizeof(MM));
  for(int l=1;l<=M.tu;l++){
    MM[M.data[l].i][M.data[l].j] = M.data[l].e;
  }
  for(int i=1;i<=M.mu;i++){
    for(int j=1;j<=M.nu;j++){
      printf("%3d",MM[i][j]); 
    }
    printf("\n");
  }
  printf("输出成功\n");
  return 0;
} 


//销毁矩阵 
Status DestroySMatrix(TSMatrix &M){//销毁稀疏矩阵M
  M.mu=0;
  M.nu=0;
  M.tu=0;
  printf("销毁矩阵成功\n");
  return 0; 
}


int main(){
  TSMatrix M,T,Q;
  CreateSMatrix(M);
  PrintfSMatrix(M); 
  TransposeSMatrix(M,T);
  PrintfSMatrix(T); 
  FastTransposeSMatrix(M,T);
  PrintfSMatrix(T);
  CopySMatrix(M,T);
  PrintfSMatrix(T);
  AddSMatrix(M,T,Q);
  PrintfSMatrix(Q);
  SubSMatrix(M,T,Q);
  PrintfSMatrix(Q);
  DestroySMatrix(M);
  RLSMatrix R,S,W;
  RLCreateSMatrix(R);
  RLPrintfSMatrix(R);
  RLCreateSMatrix(S);
  RLPrintfSMatrix(S);
  MultSMatrix(R,S,W);
  RLPrintfSMatrix(W); 
  return 0;
}

‍

运行过程需要两次输入，如下：

(1)（执行创造、普通转置、快速转置、复制、矩阵相加、矩阵相减、打印矩阵、销毁矩阵）输入以下内容：

输出结果：

(2)执行矩阵的相乘操作，输入以下内容（书中101页矩阵M和N）：

运行结果：

「往 • 期 • 精 • 选」

数据结构(严蔚敏C语言版)——数组（顺序数组）

数据结构(严蔚敏C语言版)——队列（循环队列）

数据结构(严蔚敏C语言版)——队列（顺序队列）

数据结构(严蔚敏C语言版)——队列（链队列）

数据结构(严蔚敏C语言版)——栈（链栈）

数据结构(严蔚敏C语言版)——栈（顺序栈）
数据结构(严蔚敏C语言版)——线性表(静态链表)

数据结构(严蔚敏C语言版)——线性表(普通链表)

在看点这里

文章转载自编程Cookbook，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构(严蔚敏C语言版)——稀疏矩阵

‍

评论