只怪 博主智商无下限，花了一个周末终于把系数矩阵的压缩存储及其转置给弄明白了，所以今天就和大家分享一下我的学习过程啦！！！

稀疏矩阵是指矩阵中大多数元素为零的矩阵，从直观上讲，非零元素的个数低于总元素的30%时，这样的矩阵称为稀疏矩阵。

1.稀疏矩阵的三元组组表示法

对于稀疏矩阵的压缩存储，采取只存储非零元素的方法，由于稀疏矩阵中非零元素的分布没有规律，所以呢？？？在存储非零元素的时候必须给每个元素做个标记（非零元素在矩阵中所处的行号和列号）。

//稀疏矩阵三元组表类型的定义struct Triple{T _value;size_t _row;size_t _col;Triple(size_t row=0,size_t col=0,const T& value=T()):_value(value),_row(row),_col(col){}};

（1）Triple是包含三个域的结构体类型，其元素是为了存储非零元的三元组

2.稀疏矩阵的压缩存储

就上图给出的矩阵而言，运用三元组压缩存储的方法存储后的结果是酱紫滴

源代码是酱紫滴：

//用三元组表示实现稀疏矩阵的压缩存储	SpareMatrix(T* a,size_t m,size_t n,const T& invalid)		:_rowsize(m)		,_colsize(n)		,_invalid(invalid)	{		for(size_t i=0;i
     
      (i,j,a[i*n+j]));				}			}		}		}
     

3.稀疏矩阵的列序递增转置法

采用被转置矩阵按照列序递增的的顺序进行转置，并依此将将其送入转置后的三元组表中，这样子的话转置后的三元组表恰好是以行序号为主的哦 。

具体做法：

（1）找出转置后的第一行元素：第一遍从头至尾扫描三元组表，找出所有_col为1的三元组，转置后按顺序放到开辟好新的三元组表中

（2）找出转置后的第二行元素：第一遍从头至尾扫描三元组表，找出所有_col为2的三元组，转置后按顺序放到开辟好新的三元组表中

 源代码是酱紫滴：//稀疏矩阵的转置SpareMatrix
     
       Transport(){      SpareMatrix
      
        tmp;  tmp._rowsize = _colsize;  tmp._colsize = _rowsize;  tmp._invalid=_invalid;  //给构建好的匿名对象开辟空间,但是不改变size的大小，开辟后初始化的值为原来的。  tmp._a.reserve(_a.size());  for(size_t i=0;i<_colsize;i++)  {  size_t index=0;  for(index=0;index<_a.size();index++)  {   if(_a[index]._col==i)   {   Triple 
       
         tp;   tp._row=_a[index]._col;   tp._col=_a[index]._row;   tp._value=_a[index]._value;   tmp._a.push_back(tp);   }  }  }  return tmp;  }
       
      
     

注释：虽然构建了一个 SpareMatrix<T> tmp类型的对象但是并没有给它开辟和_a一样大小的空间，所以要调用reserve或者resize两个函数中任意一个即可，否则当你在运行程序的时候会奔溃哦，智商无下线的博主昨天就是犯了这个错误，程序跑起来的时候，老是弹出这样的框框：

最后调试了好久才发现问题所在气死宝宝啦，

算法分析：

算法主要耗费在双重循环中，其时间复杂度为o(_colsize*_a.size());

4.稀疏矩阵的一次定位快速转置算法

 

算法思想：

（1）计算待转置矩阵三元组表中每一列非零元素的个数，即转置后矩阵三元组表每一行中非零元素的个数。

（2）计算待转置矩阵每一列中第一个非零元素三元组表中的具体位置。

源代码是酱紫滴：

/稀疏矩阵的快速转置SpareMatrix
     
       FastTransport(){  SpareMatrix
      
        tmp;  tmp._rowsize = _colsize;  tmp._colsize = _rowsize;  tmp._invalid=_invalid;  int* rowcounts=new int[tmp._rowsize];  int* rowstart=new int[tmp._rowsize];  memset(rowcounts,0,sizeof((int*)_colsize));  memset(rowstart,0,sizeof((int*)_colsize));  size_t index=0;   //计算待转置矩阵每一列非零元素的个数  while(index<_a.size())  {  rowcounts[_a[index]._col]++;  index++;  }//计算待转置矩阵每一列第一个非零元素在三元组表中的位置rowstart[0]=0;for(size_t i=1;i<_colsize;i++){rowstart[i]=rowstart[i-1]+rowcounts[i-1];}index=0;//给_a的匿名对象开辟_a大小的空间    tmp._a.resize(_a.size());while(index<_a.size()){/*size_t rowindex=_a[index]._col;*/int& start=rowstart[_a[index]._col];Triple
       
         tp;tp._value=_a[index]._value;tp._row=_a[index]._col;tp._col=_a[index]._row;tmp._a[start++]=tp;index++;}return tmp;}
       
      
     

算法分析：

一次定位快速转置算法时间主要耗费在三个并列的循环中，因而时间复杂度为o(_a.size+_colsize).

 

完整的源代码：

 

//稀疏矩阵的压缩存储#include
     
      #include
      
       using namespace std;template
       
        //稀疏矩阵三元组表类型的定义struct Triple{T _value;size_t _row;size_t _col;Triple(size_t row=0,size_t col=0,const T& value=T()):_value(value),_row(row),_col(col){}};template
        
         //稀疏矩阵class SpareMatrix{public:SpareMatrix():_rowsize(0),_colsize(0),_invalid(0){}//用三元组表示实现稀疏矩阵的压缩存储SpareMatrix(T* a,size_t m,size_t n,const T& invalid):_rowsize(m),_colsize(n),_invalid(invalid){for(size_t i=0;i
         
          
           
            (i,j,a[i*n+j]));}}}}//稀疏矩阵的转置SpareMatrix
            
              Transport(){      SpareMatrix
             
               tmp;  tmp._rowsize = _colsize;  tmp._colsize = _rowsize;  tmp._invalid=_invalid;  //给构建好的匿名对象开辟空间,但是不改变size的大小，开辟后初始化的值为原来的。  tmp._a.reserve(_a.size());  for(size_t i=0;i<_colsize;i++)  {  size_t index=0;  for(index=0;index<_a.size();index++)  {   if(_a[index]._col==i)   {   Triple 
              
                tp;   tp._row=_a[index]._col;   tp._col=_a[index]._row;   tp._value=_a[index]._value;   tmp._a.push_back(tp);   }  }  }  return tmp;  }//稀疏矩阵的快速转置SpareMatrix
               
                 FastTransport(){  SpareMatrix
                
                  tmp;  tmp._rowsize = _colsize;  tmp._colsize = _rowsize;  tmp._invalid=_invalid;  int* rowcounts=new int[tmp._rowsize];  int* rowstart=new int[tmp._rowsize];  memset(rowcounts,0,sizeof((int*)_colsize));  memset(rowstart,0,sizeof((int*)_colsize));  size_t index=0;   //计算待转置矩阵每一列非零元素的个数  while(index<_a.size())  {  rowcounts[_a[index]._col]++;  index++;  }//计算待转置矩阵每一列第一个非零元素在三元组表中的位置rowstart[0]=0;for(size_t i=1;i<_colsize;i++){rowstart[i]=rowstart[i-1]+rowcounts[i-1];}index=0;//给_a的匿名对象开辟_a大小的空间    tmp._a.resize(_a.size());while(index<=_a.size()){/*size_t rowindex=_a[index]._col;*/int& start=rowstart[_a[index]._col];Triple
                 
                   tp;tp._value=_a[index]._value;tp._row=_a[index]._col;tp._col=_a[index]._row;tmp._a[start++]=tp;index++;}return tmp;}void display(){   size_t index=0;for(size_t i=0;i<_rowsize;i++){for(size_t j=0;j<_colsize;j++){   if(index<_a.size() && _a[index]._row==i && _a[index]._col==j)   {        cout<<_a[index++]._value<<" ";   }   else   {   cout<<_invalid<<" ";   }}cout<
                  
                   <
                   
                    
                     
                       > _a;size_t _rowsize;size_t _colsize;T _invalid;};void test(){    int a[4][4]={ {1,0,0,0},                 {2,2,0,0},                 {0,1,3,0},                 {1,0,0,4}};SpareMatrix
                      
                       sm1((int*)a,4,4,0);sm1.display();SpareMatrix
                       
                         sm2=sm1.Transport();sm1.display();SpareMatrix
                        
                          sm3=sm1.FastTransport();sm1.display();}int main(){test();getchar();return 0;}