#include<iostream> #include<vector> #include<assert.h> using namespace std;  template<class T> class SparseMatrix {   //三元組   template<class T>   struct Trituple   {     Trituple()//給一個(gè)默認(rèn)構(gòu)造函數(shù)     {}     Trituple(size_t row, size_t col, const T& data)       :_row(row)       ,_col(col)       ,_data(data)     {}     size_t _row;     size_t _col;     T _data;   }; public:   //稀疏矩陣的壓縮存儲(chǔ)   SparseMatrix()   {}   SparseMatrix(int* arr, size_t row, size_t col, const T& invalid)     :_row(row)     ,_col(col)     ,_invalid(invalid)   {     for(int i = 0; i < row; i++)     {       for(int j = 0; j < col; ++j)       {         if(arr[i*col+j] != invalid)//將有效值存儲(chǔ)在一個(gè)一維數(shù)組中         _sm.push_back(Trituple<T>(i,j,arr[i*col+j]));//將三元組的無(wú)名對(duì)象push進(jìn)去       }     }     }   //訪(fǎng)問(wèn)稀疏矩陣中row行col中的元素   T& Acess(int row, int col)   {     //1、     /*for(int idx = 0; idx < _sm.size(); idx++)//遍歷一遍     {       if(_sm[idx]._row == row && _sm[idx]._col == col)//當(dāng)前行列與我們要訪(fǎng)問(wèn)那個(gè)元素行列相同時(shí)返回這個(gè)有效值         return _sm[idx]._data;     }     return _invalid;*/ //否則返回?zé)o效值     //2、     vector<Trituple<T>>::iterator it = _sm.begin();//定義一個(gè)迭代器,指向起始位置     while(it != _sm.end())//未到最后一個(gè)元素時(shí)     {       if(it->_row == row && it->_col == col)//行列相等輸出值         return it->_data;       ++it;//迭代器向后移動(dòng)     }     return _invalid;   }   //還原稀疏矩陣   template<typename T>   friend ostream& operator<<(ostream& _cout, SparseMatrix<T>& s)//重載<<   {     size_t idex = 0;     for(size_t i = 0; i < s._row; i++)     {       for(size_t j = 0; j < s._col; j++)       {         if(idex < s._sm.size()/*防止數(shù)組越界*/ && s._sm[idex]._row == i && s._sm[idex]._col == j)         {           _cout<<s._sm[idex]._data<<" ";           ++idex;         }         else           _cout<<s._invalid<<" ";                }       _cout<<endl;     }     return _cout;   }   //實(shí)現(xiàn)稀疏矩陣的逆置 時(shí)間復(fù)雜度O(M*N)(M為元素個(gè)數(shù)N為矩陣列數(shù))   SparseMatrix<T> Transport()   {     SparseMatrix<T> sm;     sm._row = _col;     sm._col = _row;     sm._invalid = _invalid;     for(size_t i = 0; i < _col; i++)     {       vector<Trituple<T>>::iterator it = _sm.begin();       while(it != _sm.end())       {         if(it->_col == i)//從原矩陣第0列開(kāi)始，將每列中的有效值依次放入新的稀疏矩陣           sm._sm.push_back(Trituple<T> (i, it->_row, it->_data));         ++it;       }     }     return sm;   }   //實(shí)現(xiàn)稀疏矩陣的快速轉(zhuǎn)置 時(shí)間復(fù)雜度O(N)+O(M)   SparseMatrix<T> FastTransport()   {     SparseMatrix<T> sm;     sm._col = _row;     sm._row = _col;     sm._invalid = _invalid;     sm._sm.resize(_sm.size());//開(kāi)辟空間     //1、統(tǒng)計(jì)原矩陣中每一列有多少個(gè)有效元素     int* pCount = new int[_col];//開(kāi)辟原矩陣中列個(gè)數(shù)的空間     memset(pCount, 0, _col*sizeof(pCount[0]));     for(int i = 0; i < _sm.size(); i++)       pCount[_sm[i]._col]++;     //2、原矩陣每一列在新矩陣中的起始位值     int* pAddr = new int[_col];     memset(pAddr, 0, _col*sizeof(pAddr[0]));     for(int i = 1/*從1開(kāi)始，第一個(gè)位置起始為0已經(jīng)放入*/; i < _sm.size(); i++)     {       pAddr[i] = pAddr[i - 1] + pCount[i - 1];//前一個(gè)起始位值+前一列有效元素個(gè)數(shù)     }     //3、放置元素到新空間     for(int i = 0; i < _sm.size(); i++)     {       int& addr = pAddr[_sm[i]._col];       sm._sm[addr] = Trituple<T>(_sm[i]._col,_sm[i]._row,_sm[i]._data);       addr++;     }     return sm;   }   //實(shí)現(xiàn)稀疏矩陣的加法操作1   /*SparseMatrix<T> operator+(const SparseMatrix<T>& sp)   {     int i = 0, j = 0, k = 0;     T v;     SparseMatrix<T> s;     if(this->_col != sp._col || this->_row != sp._row)       exit(1);     s._row = sp._row;     s._col = sp._col;     s._invalid = sp._invalid;     while(i < this->_sm.size() && j < sp._sm.size())     {       if(this->_sm[i]._row == sp._sm[j]._row)       {         if(this->_sm[i]._col < sp._sm[j]._col)         {           s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));           i++;           k++;         }         else if(this->_sm[i]._col > sp._sm[j]._col)         {           s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));           j++;           k++;         }         else         {           v = this->_sm[i]._data + sp._sm[j]._data;           if(v)           {             s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, v));             k++;           }           i++;           j++;         }       }       else if(this->_sm[i]._row < sp._sm[j]._row)       {         s._sm.push_back(Trituple<T>(this->_sm[i]._row, this->_sm[i]._col, this->_sm[i]._data));         i++;         k++;       }       else       {         s._sm.push_back(Trituple<T>(sp._sm[j]._row, sp._sm[j]._col, sp._sm[j]._data));         j++;         k++;       }     }     return s;   }*/   //實(shí)現(xiàn)稀疏矩陣的加法操作2   SparseMatrix<T> operator+(const SparseMatrix<T>& sp)   {     assert(_row == sp._row && _col == sp._col);//檢測(cè)兩個(gè)相加的矩陣行列是否相等     SparseMatrix<T> ret;     ret._row = _row;     ret._col = _col;     ret._invalid = _invalid;     int iLidx = 0, iRidx = 0;//定義兩個(gè)索引          while(iLidx < _sm.size() && iRidx < sp._sm.size())     {       size_t AddrLeft = _sm[iLidx]._row*_col+_sm[iLidx]._col;//左邊矩陣的起始位值       size_t AddrRight = sp._sm[iRidx]._row*sp._col+sp._sm[iRidx]._col;//右邊矩陣起始位值       if(AddrLeft < AddrRight)//左<右，將左邊有效值放入和矩陣中，左邊的索引加加       {         ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));         iLidx++;       }       else if(AddrLeft > AddrRight)       {         ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));         iRidx++;       }       else//當(dāng)左邊等于右邊判斷相加后和是否為0，不為0放入       {         Trituple<T> temp(_sm[iLidx]);         temp._data += sp._sm[iRidx]._data;         if(temp._data)         {           ret._sm.push_back(temp);           iLidx++;           iRidx++;         }       }     }     while(iLidx < _sm.size())//左邊還有剩余則放入剩余元素     {       ret._sm.push_back(Trituple<T>(_sm[iLidx]._row, _sm[iLidx]._col, _sm[iLidx]._data));       iLidx++;     }     while(iRidx < sp._sm.size())     {       ret._sm.push_back(Trituple<T>(sp._sm[iRidx]._row, sp._sm[iRidx]._col, sp._sm[iRidx]._data));       iRidx++;     }     return ret;   } private:   size_t _row;   size_t _col;   vector<Trituple<T>> _sm;   T _invalid;//無(wú)效值 };  int main() {   int arr[6][5] = {     {1,0,3,0,5},     {0,0,0,0,0},     {0,0,0,0,0},     {1,0,3,0,5},     {0,0,0,0,0},     {0,0,0,0,0}};   int arr1[6][5] = {     {1,0,3,0,5},     {0,0,0,0,0},     {0,0,2,4,0},     {1,0,3,0,5},     {0,0,0,1,0},     {0,0,0,0,1}};   SparseMatrix<int> s((int*)arr,6,5,0);   SparseMatrix<int> s1((int*)arr1,6,5,0);   cout<<"訪(fǎng)問(wèn)三行四列元素"<<endl;   cout<<s.Acess(3,4)<<endl;   cout<<s<<endl;   cout<<"快速轉(zhuǎn)置"<<endl;   cout<<s.FastTransport();   cout<<endl;   cout<<"矩陣s："<<endl;   cout<<s<<endl;   cout<<"矩陣s1："<<endl;   cout<<s1<<endl;   cout<<"s+s1求和："<<endl;   cout<<s1+s<<endl;   system("pause");   return 0; }