稀疏矩阵的压缩存储以及快速转置

矫情吗；* 2022-06-16 04:55 268阅读 0赞

稀疏矩阵的压缩存储 压缩存储值存储极少数的有效数据。使用\{row,col,value\}三元组存储每一个有效 数据，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。  
矩阵的转置 将原矩阵的行、列对换，也就是将\[i\]\[j\]和\[j\]\[i\]位置上的数据对换。  
![这里写图片描述][SouthEast]  
在压缩存储的过程中要注意越界问题

SparseMatrix( T *arr , int m, int n, T invalid)
                   :_row( m)
                   ,_col( n)
                   , _invalid( invalid)
            {
                    for (int i = 0; i < _row; i++)
                   {
                            for (int j = 0; j < _col; j++)
                           {
                                   if (arr [i*_col + j] != invalid)
                                  {
                                           Trituple t(i, j, arr [i*_col + j]);
                                          sm.push_back(t);
                                  }
                           }
                   }
            }

还原矩阵

void Display1()
            {
                    size_t index = 0;
                    for (size_t i = 0; i < _row; i++)
                   {
                            for (size_t j = 0; j < _col; j++)
                           {
                                   if (index < sm.size()&&sm[index]._row == i&&sm[index]._col == j)
                                  {
                                          cout << sm[index]._value << " " ;
                                          index++;
                                  }
                                   else
                                  {
                                          cout << _invalid << " " ;
                                  }
                           }
                           cout << endl;
                   }
            }

矩阵的快速转置  
![这里写图片描述][SouthEast 1]  
可见单纯的交换行和列并不满足专制之后的矩阵  
因为转置之后的矩阵是按照行优先的顺序，因为最后还要方便与我们还原三元组  
那么第一种方式：

1、交换往行和列之后按照行优先的顺序再次进行排序  
\{0，1，3\}，\{0，4，8\}， \{1，0，1\} ，\{1，2，4\}，\{1，3，6\}， \{1，5，9\}，\{3，2，5\} ，\{3，3，7\}，\{4，0，2\}

2、交换之后再按照列排序  
\{0，1，3\}，\{0，4，8\}， \{1，0，1\}， \{1，2，4\}，\{1，3，6\}， \{1，5，9\}，\{3，2，5\} ，\{3，3，7\}，\{4，0，2\}

第一种方式的代码：

void Trans()
            {
                    int index = 0;
                   vector<Trituple>Tr;
                    for (int i = 0; i < sm.size(); i++)
                   {
                           Trituple temp(sm[i]._col, sm[i]._row, sm[i]._value);
                           Tr.push_back(temp);
                   }
                    for (int i = 0; i < sm.size() - 1; i++)
                   {
                            for (int j = 0; j < i; j++)
                           {
                                   if (Tr[j]._row>Tr[j + 1]._row)
                                  {
                                          swap(Tr[j], Tr[j + 1]);
                                  }
                                   else if (Tr[j]._row == Tr[j + 1]._row)
                                  {
                                           if (Tr[j]._col>Tr[j + 1]._col)
                                          {
                                                 swap(Tr[j], Tr[j + 1]);
                                          }
                                  }
                           }
                   }
                   sm = Tr;
            }

但是这种方式的快速转置时间复杂度=有效元素的个数+有效元素的个数\*有效元素的个数  
时间复杂度太高，因此我们需要降低时间复杂度采用这种方式

第二种方式：  
由于转置之前的列等于转置之后的行数，因此我们可以用一个数组用来保存转置之前每一列有效元素的个数  
并且每一列的有效元素的个数是不会发生改变的  
因此可以通过数组记录，每一列有效元素的个数  
除此之外还需要记录转制之前每一列有效元素的起始位置

![这里写图片描述][SouthEast 2]

template<class T>
    class Trans
    {
    
        public:
             typedef Trituple <T>  Trituple;
            Trans( SparseMatrix<T > &s)
            :_x( s._row)
            ,_y( s._col)
            ,_value( s._invalid)
       {
                    vector<size_t >count;
                   count.resize( s._col);
                    vector<size_t >cpot;
                   cpot.resize( s._col);
                    size_t Size = (s .sm).size();
                   Tr.resize(Size);
                    size_t TSize = Tr.size();
                    for (int i = 0; i < Size; i++)
                   {
                           count[( s.sm[i])._col]++;
                   } //统计每一列有效元素的个数
                   cpot[0] = 0;
                    for (int i = 1; i < s._col; i++)
                   {
                           cpot[i] = cpot[i - 1] + count[i - 1];
                   } //统计每一列有效元素的起始地址
                    for (int i = 0; i < TSize; i++)
                   {
                            size_t col = s .sm[i]._col;
                            size_t pos = cpot[col];
                           Tr[pos]._row = s.sm[i]._col;
                           Tr[pos]._col = s.sm[i]._row;
                           Tr[pos]._value = s.sm[i]._value;
                           ++cpot[col];
    
                   }
    
         }
                            void Display()
                           {
                                   size_t index = 0;
                                   for (size_t i = 0; i < _x; i++)
                                  {
                                           for (size_t j = 0; j < _y; j++)
                                          {
                                                  if (index < Tr.size() && Tr[index]._row == i&&Tr[index]._col == j)
                                                 {
                                                         cout << Tr[index]._value << " " ;
                                                         index++;
                                                 }
                                                  else
                                                 {
                                                         cout << _value << " " ;
                                                 }
                                          }
                                          cout << endl;
                                  }
                           }
    protected:
    vector<Trituple > Tr;
    size_t _x;
    size_t _y;
    size_t _value;
    };

[SouthEast]: /images/20220616/ffda1413aa66418f91cdf17c93543bce.png
[SouthEast 1]: /images/20220616/e5857fcdadf14cdcb5dcf5f275ffc0ba.png
[SouthEast 2]: /images/20220616/497841c64e854bb0852749a729e4a40e.png