稀疏矩阵的简单描述

冷不防 2022-06-09 07:14 282阅读 0赞

稀疏矩阵

设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），则称A为稀疏矩阵

由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，必须同时记下它所在的行和列的位置（i,j)。所以，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。

一、三元组顺序表

假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元顺序表。

\#define MAXSIZE 10000

typedef int datatype;

struct triple\{

int   i,j;

datatype v;

\} ;

struct tripletable\{

triple  data\[MAXSIZE\];

int  m,n,t;

\}tripletable;

![Center][]

Tripletable  M；

![Center 1][]

![Center 2][]

有关算法：

（1）矩阵的转置

一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a\[i\]\[j\]=b\[j\]\[i\]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。

对三元组M进行转置换，得到三元组T

![Center 3][]

1)   转置运算算法TransposeSMatrix(M, T)

基本思想

对 M.data从头至尾扫描：

第一次扫描时，将M.data中列号为1的三元组赋值到T.data中，

第二次扫描时，将M.data中列号为2的三元组赋值到T.data中，

依此类推，直至将M.data所有三元组赋值到T.data中

TransposeSMatrix(M, T)  {
       T.mu=M.nu;  T.nu=M.mu;  T.tu=M.tu;
       if (T.tu)  {
         q=0； // q为当前三元组在T.data[ ]存储位置(下标)
         for (col=1; col<=M.nu;  ++col)
          for (p=0;  p<=M.tu-1;  ++p) //p为扫描M.data[ ]的“指示器”
            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;}
        }
    }//  TransposeSMtrix

分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n\*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：

for(col=0;col<=n-1;++col)

for(row=0;row<=m;++row)

t\[col\]\[row\]=m\[row\]\[col\];

其时间复杂度为O(n\*m)。当非零元素的个数t和m\*n同数量级时，算法transmatrix的时间复杂度为O(n\*n2)。

三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于t<<m\*n的情况。

下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。

辅助向量num\[ \] 、pos\[ \]

为先求得M各列第一个非零元三元组在T.data中的位置。引入两个辅助向量num\[ \] 、pos\[ \]：

num\[col\]：存储第col列非零元个数

pos\[col\]：存储第col列第一个非零元三元组在T.data中的位置

pos\[col\]的计算：

pos\[0\]=1

pos\[col\]=pos\[col-1\]+num\[col-1\]   2<=col<=n

![Center 4][] ![Center 5][]

2)快速转置算法主要步骤：

a)   求M中各列非零元个数num\[ \]

b)   求M中各列第一个非零元在T.data中的下标pos\[ \];

c)  对M.data进行一次扫描， 遇到col列的第一个非零元三元组时，按pos\[col\]的位置，将其放至T.data中，当再次遇到col列的非零元三元组时，只须顺序放到col列元素的后面;

FastTransposeSMatrix(M, T) {
     T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
      if (T.tu){
       for (col=0; col<M.nu; ++col) num[col]=0;
       for (t=0; t<M.tu; ++t) ++num[M.data[t].j-1]; 
       pos[0]=0;
       for(col=1; col<M.tu;  ++col)  pos[col]=pos[col-1]+num[col-1];
        for(p=0; p<M.tu;++p) { 
             col=M.data[p].j; q=pos[col]-1; 
             T.data[q].i=M.data[p].j;  T.data[q].j=M.data[p].i; 
             T.data[q].e=M.data[p].e;   
             ++pos[col];  }//for
         }//if 
    }//FastTransposeSMatrix

[Center]: /images/20220609/e2f18611803841b8a823b2bf00119a76.png
[Center 1]: /images/20220609/ccc3d3d7dcf9404db7157c6c89facfc1.png
[Center 2]: /images/20220609/ae8544e506ab47aebeeb19325c4c34d4.png
[Center 3]: /images/20220609/92b578e1baf04ecaa04602166b43d7b0.png
[Center 4]: https://img-blog.csdn.net/20170830203053715?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZ29vZG1hbl9scWlmZWk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: /images/20220609/332de37581cd40d98b908b288ded28fa.png